Algebraic Techniques in Computational Complexity
Videos from BIRS Workshop
Ryan O'Donnell, Carnegie Mellon University
Monday Jul 8, 2019 09:10 - 10:06
Explicit near-Ramanujan graphs of every degree
Dana Moshkovitz, University of Texas - Austin
Monday Jul 8, 2019 10:07 - 11:00
Nearly Optimal Pseudorandomness From Hardness
Eshan Chattopadhyay, Cornell University and IAS
Monday Jul 8, 2019 11:17 - 11:56
Pseudorandomness from the Fourier Spectrum
William Hoza, UT Austin
Monday Jul 8, 2019 13:31 - 14:19
Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas
Shubhangi Saraf, Rutgers University
Tuesday Jul 9, 2019 09:58 - 10:53
Factors of sparse polynomials: structural results and some algorithms
Amir Shpilka, Tel Aviv U
Tuesday Jul 9, 2019 11:17 - 12:09
Sylvester-Gallai Type Theorems for Quadratic Polynomials
Josh Alman, MIT
Tuesday Jul 9, 2019 13:32 - 14:23
Efficient Construction of Rigid Matrices Using an NP Oracle
Sajin Koroth, Simon Fraser University
Wednesday Jul 10, 2019 11:18 - 12:11
Query-to-Communication lifting using low-discrepancy gadgets
Arkadev Chattopadhyay, Tata Institute of Fundamental Research
Thursday Jul 11, 2019 09:04 - 09:56
The Log-Approximate-Rank Conjecture is False
Shachar Lovett, University of California San Diego
Thursday Jul 11, 2019 10:01 - 10:57
The sunflower conjecture and connections to TCS
Mark Bun, Boston University
Thursday Jul 11, 2019 13:34 - 14:31
Private hypothesis selection
Benjamin Rossman, University of Toronto
Friday Jul 12, 2019 09:05 - 09:52
Criticality and decision-tree size of regular AC^0 functions
Neeraj Kayal, MSR India
Friday Jul 12, 2019 09:52 - 10:48
Reconstructing arithmetic formulas using lower bound proof techniques
Joshua Grochow, University of Colorado at Boulder
Friday Jul 12, 2019 11:02 - 11:55
Tensor Isomorphism: completeness, graph-theoretic methods, and consequences for Group Isomorphism
