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. Can we design a private variant of "Google searc |
 |
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 |
|
|
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 |
 |
Nathan Klein: A (Slightly) Improved Approximation Algorithm for Metric TSP Tuesday, October 27, 2020 - 4:00pm to 5:15pm |
 |
James Aspnes: Population Protocols Tuesday, October 20, 2020 - 4:00pm to 5:00pm Abstract: |
 |
Alexandr Andoni: Approximating Edit Distance in Near-Linear Time Tuesday, October 13, 2020 - 4:00pm to 5:00pm Abstract: |
 |
Adi Shamir, Weizmann Institute of Tech: A Simple Explanation for the Mysterious Existence of Adversarial Examples with Small Hamming Distance Tuesday, February 18, 2020 - 4:00pm to 5:00pm Abstract:
|
 |
Rediet Abebe: Subsidy Allocations in the Presence of Income Shocks Tuesday, October 22, 2019 - 4:00pm to 5:00pm Abstract: |
 |
Anindya De: Junta correlation is testable. Tuesday, November 5, 2019 - 4:00pm to 5:00pm Abstract: A Boolean function f on the n-dimensional hypercube is said |
 |
László Végh: A Strongly Polynomial Algorithm for Linear Exchange Markets Tuesday, September 24, 2019 - 4:00pm to 5:00pm Abstract: |
 |
Arkadev Chattopadhyay: The Log-Approximate-Rank Conjecture is False Tuesday, March 12, 2019 - 4:00pm to 5:00pm Abstract: |
 |
Elette Boyle: Compression Vector OLE and More Tuesday, January 15, 2019 - 10:30am to 12:00pm Abstract:
We will speak about a CCS'18 result and the bigger picture of a new line of work in compressing different types of pseudorandom correlations.
|
 |
Michael Saks: Approximating the edit distance to within a constant factor in truly subquadratic time Tuesday, December 4, 2018 - 4:00pm to 5:00pm Abstract: Edit distance is a widely used measure of similarity of two strings based on |
Pages
