Theory Dish

Please join us for a one-day workshop, “Recent advances in Regularity Lemmas (with and without calibration)”, taking place on Tuesday, November 17 at Stanford [...]

The world of mathematics, including theoretical computer science, is in turmoil. Even the Millennium Prize Problems, and, worse still, our beloved FOCS/STOC open problems, [...]

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 [...]

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 [...]

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 [...]

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 [...]

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 [...]

In this post, we’ll discuss how Galois rings (a recent algebraic structure) improve the communication complexity of dishonest multiparty computation (MPC) [...]

The 66th Annual Symposium on Foundations of Computer Science (FOCS 2025), sponsored by the IEEE Computer Society Technical Committee on Mathematical Foundations of Computing, [...]