CSE Colloquium: Complexity Beyond the Worst Case: From Hard Problems to Hard Instances

Zoom Information 

Join from PC, Mac, Linux, iOS or Android: https://psu.zoom.us/j/843165278 

Or iPhone one-tap (US Toll): +13126266799,843165278# or +16468769923,843165278# 

or Telephone: 

Dial: 

+1 312 626 6799 (US Toll) 

+1 646 876 9923 (US Toll) 

+1 346 248 7799 (US Toll) 

+1 669 900 6833 (US Toll) 

+1 253 215 8782 (US Toll) 

+1 301 715 8592 (US Toll) 

Meeting ID: 843 165 278 

International numbers available: https://psu.zoom.us/u/adBsnTPXaN 

Abstract: The theory of NP-completeness has been very successful in describing which computational problems are hard to efficiently solve in the worst case. On the other hand, problems that are hard in the worst case may turn out to be much easier in practice. For example, modern SAT solvers can solve industrial instances of the satisfiability problem with millions of variables. This apparent discrepancy arises because the classical theory leaves the following basic questions unanswered: Which instances are hard? What are the structural properties of hard instances? Can hard instances be efficiently generated (e.g. for cryptographic applications)? 

In this talk, I will describe two complementary approaches I have taken to answering such questions. In the first, I consider a fundamental class of problems (constraint satisfaction problems) and identify structural properties of hard instances. In the second, I consider a fundamental class of algorithms (linear and semi-definite programs) and identify a natural distribution of random instances that these algorithms cannot efficiently solve. 

Biography: Jonah Brown-Cohen received a BS in Mathematics in 2011 and an MS in Computer Science in 2012 from Stanford University. He completed his PhD in Computer Science at the University of California, Berkeley in 2018, advised by Prasad Raghavendra. He received a Siebel Scholarship and an Honorable Mention for the National Science Foundation Fellowship in 2012. He was also awarded the UC Berkeley Outstanding Graduate Student Instructor Award in 2018-2019. Currently he is a Postdoctoral Researcher in the Division of Theoretical Computer Science at KTH Royal Institute of Technology, working with Johan Håstad. His research interests lie in computational complexity theory, focusing on the complexity of constraint satisfaction problems, the limitations of linear and semi-definite programming relaxations, and hardness of approximation. He has also worked on, and remains interested in, the limitations of cryptocurrency protocols. 

Website: https://www.kth.se/profile/jonahbc