Theory of Computation (TOC) Seminar

Merav Parter: New Diameter Reducing Shortcuts: Breaking the $O(\sqrt{n})$ Barrier
Tuesday, December 7, 2021 - 4:00pm to 5:00pm
Subhash Khot: On Approximability of CSPs on Satisfiable Instances
Tuesday, November 30, 2021 - 4:00pm to 5:00pm

ABSTRACT: 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 learning
Tuesday, November 23, 2021 - 4:00pm to 5:00pm

The need for int

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.

Pages

Subscribe to Theory of Computation (TOC) Seminar