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

NPHardness of Learning Programs and Partial MCSP Tuesday, December 6, 2022  4:00pm to 5:15pm Abstract. In his seminal paper on the theory of NPcomplet 

Maximum Flow and MinimumCost Flow in AlmostLinear Time Tuesday, November 29, 2022  4:00pm to 5:15pm Abstract. We give an algorithm that computes exact maximum flows and minimumcost 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 ChorGoldreich 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 wellstudied 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 