Theory of Computation (TOC) Seminar

Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation
Tuesday, December 13, 2022 - 4:00pm to 5:15pm

Abstract. TBA

NP-Hardness of Learning Programs and Partial MCSP
Tuesday, December 6, 2022 - 4:00pm to 5:15pm

Abstract. In his seminal paper on the theory of NP-complet

Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
Tuesday, November 29, 2022 - 4:00pm to 5:15pm

Abstract. We give an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with $m$ edges and polynomially bounded integral demands, costs, and capacities in $m^{1+o(1)}$ time.

Algorithms Should Have Bullshit Detectors! (or Polynomial Time Byzantine Agreement with Optimal Resilience)
Tuesday, November 22, 2022 - 4:00pm to 5:15pm

Abstract. One thing that distinguishes (theoretical) compu

Almost Chor-Goldreich Sources and Adversarial Random Walks
Tuesday, October 25, 2022 - 4:15pm to 5:15pm
The Conscious Turing Machine (CTM): A Theoretical CS Approach to the Hard Problem
Tuesday, March 15, 2022 - 4:15pm to 5:15pm

Efficient Verification of Computation on Untrusted Platforms
Tuesday, March 8, 2022 - 4:00pm to 5:15pm

Efficient verification of computation is fundamental to computer science, and is at the heart of t

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


Subscribe to Theory of Computation (TOC) Seminar