How Machine Learning Improves Algorithms with Ellen Vitercik

A version of this video with audio description track is available here:    • How Machine Learning Improves Algorithms w...   Hard optimization problems often look impossible through worst-case analysis, but real-world problems can contain structure that helps algorithms work faster. Ellen Vitercik, Ph.D., of Stanford University explains how machine learning can improve algorithm design for NP-hard optimization problems while preserving the formal guarantees that make solvers useful. She discusses beyond worst-case analysis, problem-specific heuristics, and the gap between tools that perform well in practice and methods that prove optimality. Vitercik also describes research on LLM reasoning using data structure tasks, where answers can be checked programmatically and failures reveal when models rely on pattern matching rather than true generalization. Her work helps clarify how AI may support stronger algorithms, more useful benchmarks, and more reliable reasoning systems. [Show ID: 41179] 0:00 Machine Learning and Algorithm Design 1:30 What Beyond Worst-Case Analysis Means 6:22 Why NP-Hard Problems Differ in Practice 8:26 Problem-Specific Heuristics and Solvers 10:23 Using Machine Learning Without Losing Guarantees 12:26 Testing LLM Reasoning With Algorithms 14:31 When Pattern Matching Breaks Down 18:42 From Math and Music to Computer Science Donate to UCTV to support informative & inspiring programming: https://www.uctv.tv/donate More videos from: Data Science Channel (https://www.uctv.tv/data-science) Explore More Science & Technology on UCTV (https://www.uctv.tv/science) Science and technology continue to change our lives. University of California scientists are tackling the important questions like climate change, evolution, oceanography, neuroscience and the potential of stem cells. UCTV is the broadcast and online media platform of the University of California, featuring programming from its ten campuses, three national labs and affiliated research institutions. UCTV explores a broad spectrum of subjects for a general audience, including science, health and medicine, public affairs, humanities, arts and music, business, education, and agriculture. Launched in January 2000, UCTV embraces the core missions of the University of California -- teaching, research, and public service – by providing quality, in-depth television far beyond the campus borders to inquisitive viewers around the world. (https://www.uctv.tv) FAQ Q: What is beyond worst-case analysis? A: Beyond worst-case analysis looks at hard problems in a more practical way than standard worst-case analysis. Vitercik explains that many real-world optimization problems are NP-hard, but they may share useful structure that algorithms can learn and use to solve them faster. Q: How can machine learning improve algorithm design? A: Machine learning can help identify patterns or choose heuristics that make hard optimization problems easier to solve in practice. Vitercik emphasizes that a central challenge is using these tools while preserving the formal optimality guarantees that make optimization solvers valuable. Q: How do researchers test whether LLMs are reasoning or pattern matching? A: Vitercik describes using algorithmic and data structure tasks because the correct answers can be checked programmatically. When models succeed on familiar-looking examples but fail on unusual or non-uniform cases, it suggests they may be relying on pattern matching rather than general reasoning.