Theory of Computation (TOC) Seminars
 |
Vizing’s Theorem in Near-Linear Time Tuesday, November 19, 2024 - 4:15pm to 5:15pm In his classic result, Vizing (1964) proved that any graph of maximum degree ∆ can be edge colored using at most ∆+1 different colors. |
 |
Learning to Defer in Content Moderation: The Human-AI Interplay Tuesday, October 8, 2024 - 4:15pm to 5:15pm Ensuring successful content moderation is vital for a healthy online social platform where it is necessary to responsively remove harmful posts without j |
 |
Near Optimal Alphabet-Soundness Tradeoff PCPs Tuesday, September 24, 2024 - 4:15pm to 5:15pm We show a nearly optimal |
 |
Learning in Strategic Environments: from Calibrated Agents to General Information Asymmetry Tuesday, September 17, 2024 - 4:15pm to 5:15pm In this talk I will discuss learning in principal-agent games where there is information asymmetry between what the principal and what the agent know about each other’s chosen actions. |
 |
Estimating the Longest Increasing and Longest Common Subsequences Tuesday, November 15, 2022 - 4:15pm to 5:15pm |
 |
Swastik Kopparty: Fast algorithms for polynomials over all finite fields via the Elliptic Curve Fast Fourier Transform (ECFFT) Tuesday, October 5, 2021 - 4:00pm to 5:00pm |
 |
Surbhi Goel: Computational Complexity of Learning Neural Networks over Gaussian Marginals Tuesday, December 15, 2020 - 4:00pm to 5:00pm Abstract: |
 |
Scott Aaronson: Gentle Measurement of Quantum States and Differential Privacy Tuesday, November 20, 2018 - 4:00pm to 5:00pm We prove a surprising connection between gentle measurement (where one |
 |
Jelani Nelson: Heavy Hitters via Cluster-Preserving Clustering Tuesday, November 15, 2016 - 4:00pm to 5:00pm Abstract: In the "heavy hitters" or "frequent items" problem, one must process a stream of items and report those items that occur frequently. For example, a telecommunications company may wish to find popular destination IP addresses in a packet stream across one of their links, |
 |
Raghu Meka: Pseudorandomness- old problems, new methods, and current challanges Thursday, March 3, 2016 - 2:45pm to 3:45pm Abstract: In this talk I will survey recent results on two classical questions in complexity theory: derandomizing small-space algorithms and lower bounds for constant-depth circuits. |
 |
Gillat Kol: Interactive Information Theory Thursday, December 3, 2015 - 4:00pm to 5:00pm Abstract: In a profoundly influential 1948 paper, Claude Shannon introduced information theory and used it to study one-way data transmission problems over different channels, both noisy and noiseless. That paper initiated the |
 |
Omri Weinstein: Interactive Information Complexity and Applications Monday, November 16, 2015 - 4:00pm to 5:00pm Abstract: Over the past three decades, communication complexity has been extensively used to capture the fundamental limitations in diverse areas of theoretical computer science and modern computing systems. |
 |
Robin Kothari: Separations in Query Complexity Using Cheat Sheets Tuesday, November 17, 2015 - 4:00pm to 5:00pm Abstract: 2015 has been an exciting year for query complexity. I'll survey some of the breakthroughs made this year and then talk about some very recent work with my collaborators Scott Aaronson and Shalev Ben-David. |
 |
Virginia Vassilevska Williams: Fine-Grained Algorithms and Complexity Tuesday, November 10, 2015 - 4:00pm to 5:00pm Abstract: |
 |
Benjamin Rossman: The Average Sensitivity Bounded-Depth Formulas Tuesday, October 13, 2015 - 4:15pm to 5:15pm Abstract: Hastad (1986) proved an exp( n^{1/d} ) lower bound on the size of depth d+1 (unbounded fan-in) boolean *circuits* computing the PARITY function. |
 |
Mika Göös: Communication Complexity vs. Partition Numbers Tuesday, October 6, 2015 - 4:15pm to 5:15pm ABSTRACT: |
 |
Oded Regev: Faster algorithms for the Shortest Vector Problem Thursday, April 23, 2015 - 4:15pm to 5:15pm Abstract: We give a randomized ~2^n-time algorithm for solving the Shortest Vector Problem (SVP) on n-dimensional lattices, improving on the previous best running time of 4^n by Micciancio and Voulgaris (STOC 2010). Despite being the fastest, the algorithm is arguably also the simplest in this |
 |
Exponential Separation of Information and Communication Tuesday, December 2, 2014 - 4:15pm to 5:15pm Abstract: In profoundly influential works, Shannon and Huffman show that if Alice wants to send a message X to Bob, it's sufficient for her to send roughly H(X) bits (in expectation), where H denotes Shannon's entropy function. |
 |
Tilting at Windmills: The Economic Efficiency of Large Games Tuesday, November 18, 2014 - 4:15pm to 5:15pm Abstract:
|
 |
3SUM is Subquadratic Tuesday, November 4, 2014 - 4:15pm to 5:15pm Abstract: The 3SUM problem is to decide, given a set of N real numbers, whether any three of them sum to zero. A simple algorithm solves 3SUM in O(N^2) time and it has long been conjectured that this is the best possible. |
 |
Computing Elementary Statistics: Time-Space Tradeoffs and Sliding Windows Tuesday, October 28, 2014 - 4:15pm to 5:15pm Abstract: We consider the complexity of computing element distinctness, frequency moments, and order statistics with limited space, as well as computing these statistics over "sliding windows" in a single longer data sequence, a natural requirement for time-series data. |
 |
Zeev Dvir, Private Information Retrieval with 2-Servers and sub-polynomial communication Tuesday, October 7, 2014 - 4:15pm to 5:15pm |
Pages
