Playlist: 26 videos

The Classification Program of Counting Complexity

Mar. 28 – Apr. 1, 2016

Recent years have seen dramatic progress in counting complexity. In exact computation, we now have a complete classification of counting CSPs into those that are polynomial-time solvable and those that are hard for the...

0:46:35

Geometric Perspectives on Problems in Complexity Theory

J.M. Landsberg, Texas A&M University
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/jm-landsberg-2016-03-31
Visit talk page
0:44:25

Categories, Representations, and Counting Complexity

Jason Morton, Pennsylvania State University
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/jason-morton-2016-03-31
Visit talk page
0:38:35

Hilbert's Nullstellensatz Certificates of Infeasibility for Combinatorial Problems

Susan Marguiles, United States Naval Academy
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/susan-margulies-2016-03-31
Visit talk page
0:45:12

Finding a Large Submatrix of a Random Matrix, and the Overlap Gap Property

Davin Gamarnik, Massachusetts Institute of Technology
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/david-gamarnik-2016-04-01
Visit talk page
0:40:48

LP Relaxations for Valued CSPs

Stanislav Zivny, University of Oxford
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/stamislav-zivny-2016-04-01
Visit talk page
0:40:38

Counting with Bounded Treewidth

Yitong Yin, Nanjing University
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/yitong-yin-2016-04-01
Visit talk page