# Theory of Computation (TOC) Seminar

 Merav Parter: New Diameter Reducing Shortcuts: Breaking the $O(\sqrt{n})$ BarrierTuesday, December 7, 2021 - 4:00pm to 5:00pm Subhash Khot: On Approximability of CSPs on Satisfiable InstancesTuesday, November 30, 2021 - 4:00pm to 5:00pmABSTRACT: Constraint Satisfaction Problems (CSPs) are among the most well-studied problems in Computer Science, 3SAT being a prominent example. Sanjoy Dasgupta: Some excursions into interpretable machine learningTuesday, November 23, 2021 - 4:00pm to 5:00pmThe need for int Noga Alon: PAC Learnability of partial concept classesTuesday, November 16, 2021 - 4:00pm to 5:00pmWe extend the cl Shachar Lovett: The log-rank conjecture - where do we stand?Tuesday, November 9, 2021 - 4:00pm to 5:00pmThe log-rank con Greg Valiant: Sequential Prediction: Calibration and Selective PredictionTuesday, October 26, 2021 - 4:00pm to 5:00pmABSTRACT: I'll Li-yang Tan: Properly learning decision trees in almost polynomial timeTuesday, October 19, 2021 - 4:00pm to 5:00pmAbstract Nutan Limaye: Superpolynomial Lower Bounds Against Low-Depth Algebraic CircuitsTuesday, October 12, 2021 - 4:00pm to 5:00pmABSTRACT: Every multivariate polynomial P(X) can be written as a sum of monomials, i.e. a sum of products of variables and field constants. Kuikui Liu: Markov Chain Analysis via Spectral IndependenceTuesday, September 28, 2021 - 4:00pm to 5:00pm Nike Sun: Phase transitions in random constraint satisfaction problemsTuesday, December 8, 2020 - 4:00pm to 5:00pmAbstract: I will survey recent progress in determination of asymptotic behavior for random constraint satisfaction problems, including phase transitions and some understanding of solution geometry.