Theory of Computation (ToC) Seminar 2022


Yael Kalai, MIT and Microsoft
Efficient Verification of Computation on Untrusted Platforms
Speaker(s): Yael Kalai
Date: Tuesday, March 08, 2022
Time: 4:00 PM to 5:15 PM
Location: 32-G449 (Kiva)
Contact: Nathan Higgins, nhiggins@csail.mit.edu

Manuel Blum,
The Conscious Turing Machine (CTM): A Theoretical CS Approach to the Hard Problem
Speaker(s): Manuel Blum
Date: Tuesday, March 15, 2022
Time: 4:15 PM to 5:15 PM
Location: 32-123
Contact: Nathan Higgins, nhiggins@csail.mit.edu

Anurag Anshu, Berkeley
Complexity of Local Hamiltonians via Polynomial Approximations to AND Function
Speaker(s): Anurag Anshu
Date: Tuesday, March 29, 2022
Time: 4:00 PM to 5:00 PM
Location: 32-G449 (Kiva)
Contact: Nathan Higgins, nhiggins@csail.mit.edu

Roei Tell, Institute for Advanced Study
New Directions in Derandomization: Non-Black-Box Techniques, Superfast Algorithms
Speaker(s): Roei Tell
Date: Tuesday, April 12, 2022
Time: 4:00 PM to 5:00 PM
Location: 32-G449 (Kiva)
Contact: Nathan Higgins, nhiggins@csail.mit.edu

Tselil Schramm, Stanford University
Testing Thresholds for High-Dimensional Random Geometric Graphs
Speaker(s): Tselil Schramm
Date: Tuesday, April 19, 2022
Time: 4:00 PM to 5:00 PM
Location: 32-G449 (Kiva)
Contact: Nathan Higgins, nhiggins@csail.mit.edu

Pravesh Kothari , Carnegie Mellon University (CMU)
Refuting Smoothed k-SAT Formulas and a Proof of Feige's Conjecture
Speaker(s): Pravesh Kothari
Date: Tuesday, April 26, 2022
Time: 4:00 PM to 5:00 PM
Location: 32-G449 (Kiva)
Contact: Nathan Higgins, nhiggins@csail.mit.edu

Anand Natarajan, CSAIL MIT
Quantum Search-to-Decision Reductions and the State Synthesis Problem
Speaker(s): Anand Natarajan
Date: Tuesday, May 03, 2022
Time: 4:00 PM to 5:00 PM
Location: 32-124
Contact: Nathan Higgins, nhiggins@csail.mit.edu

Jerry Li, Microsoft Research Redmond
Clustering Mixtures with Almost Optimal Separation in Polynomial Time
Speaker(s): Jerry Li
Date: Tuesday, May 10, 2022
Time: 4:00 PM to 5:00 PM
Location: 32-G449 (Kiva)
Contact: Nathan Higgins, nhiggins@csail.mit.edu