Quantum Speedups Require Structure or Depth
By Guy Blanc, Jordan Docter, Carmen Strassle, and Li-Yang Tan This is the first in a series of blog posts about our paper, Quantum Speedups Require Structure or Depth, which [...]
Condorcet Quintets — A Proof from the Book
Here’s my favorite problem in voting theory. Suppose we have an election in which voters provide ranked preferences over the candidates. For what kk can we always [...]
STOC 2026 Student Travel Grants
Hi all! An announcement on behalf of the STOC/TheoryFest organizers: ACM SIGACT is pleased to provide funds to support student attendance at STOC 2026. These travel awards [...]
STOC 2026 Call for Workshops
TheoryFest 2026 will hold workshops during the STOC 2026 conference week, June 22–26, 2026, in Salt Lake City, Utah, USA. We invite groups of interested researchers to [...]
Quickly approximating Shapley Games
In this blog post, we will talk about some recent advances in algorithms for approximately solving Shapley Games. What is a Shapley Game? At an intuitive level, Shapley games [...]
Choosing the best ring … for MPC!
In this post, we’ll discuss how Galois rings (a recent algebraic structure) improve the communication complexity of dishonest multiparty computation (MPC) [...]
FOCS 2025 CfP is Out
The 66th Annual Symposium on Foundations of Computer Science (FOCS 2025), sponsored by the IEEE Computer Society Technical Committee on Mathematical Foundations of Computing, [...]
Four Views of Data Deletion
Where’s the theory on datasets? The canonical model of splitting a dataset into train and test data allows statistical validity for the evaluation of model performance. [...]
FORC 2026 – CFP
The 6th annual Symposium on Foundations of Responsible Computing (FORC) will be held on June 4-6, 2025 at Stanford University, CA, USA. Call for papers is out. There are [...]
ITC 2024 at Stanford! Early-Bird Registration Deadline August 1
The conference Information-Theoretic Cryptography (ITC) is happening at Stanford, August 14-16, conveniently just before CRYPTO in Santa Barbara! [...]
