Theory of Computation (TOC) Seminar
 |
Noga Alon: PAC Learnability of partial concept classes Tuesday, November 16, 2021 - 4:00pm to 5:00pm We extend the cl |
|
|
Shachar Lovett: The log-rank conjecture - where do we stand? Tuesday, November 9, 2021 - 4:00pm to 5:00pm The log-rank con |
 |
Greg Valiant: Sequential Prediction: Calibration and Selective Prediction Tuesday, October 26, 2021 - 4:00pm to 5:00pm ABSTRACT: I'll |
 |
Li-yang Tan: Properly learning decision trees in almost polynomial time Tuesday, October 19, 2021 - 4:00pm to 5:00pm Abstract |
 |
Nutan Limaye: Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits Tuesday, October 12, 2021 - 4:00pm to 5:00pm ABSTRACT: 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 Independence Tuesday, September 28, 2021 - 4:00pm to 5:00pm
|
 |
Nike Sun: Phase transitions in random constraint satisfaction problems Tuesday, December 8, 2020 - 4:00pm to 5:00pm Abstract: I will survey recent progress in determination of asymptotic behavior for random constraint satisfaction problems, including phase transitions and some understanding of solution geometry. |
 |
Toniann Pitassi: Lifting with Sunflowers Tuesday, December 1, 2020 - 4:00pm to 5:30pm Abstract: In this talk I will first motivate lifting theorems where lower bounds on communication complexity for composed functions are obtained by a general simulation theorem, essentially showing that no protoco |
 |
Huijia (Rachel) Lin: Indistinguishability Obfuscation from Well-Founded Assumptions Tuesday, November 17, 2020 - 4:00pm to 5:00pm
|
 |
Ashish Goel: Beyond Voting: Mechanisms and Platforms for Societal Decision Making Tuesday, November 10, 2020 - 4:00pm to 5:00pm Abstract: YouTube competes with Hollywood as an entertainment channel, and also supplements Hollywood by acting as a distribution mechanism. Twitter has a similar relationship to news media, and Coursera to |
Pages
