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 [...]
Uncategorized
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! [...]
FORC 2024 – CFP
The 5th annual Symposium on Foundations of Responsible Computing (FORC) will be held on June 12-14, 2024, at Harvard University in Cambridge, MA. Call for papers is out. [...]
2024 Motwani Postdoc Announced
The theory group at Stanford invites applications for the Motwani postdoctoral fellowship in theoretical computer science. Information and application instructions below. [...]
Optimal Metric Distortion for Voting — A Proof from the Book
In this post, we’ll revisit the (deterministic) metric distortion conjecture in voting theory, which was recently proved by Gkatzelis, Halpern, and Shah [GHS20], and [...]
DNF Minimization, Part II
In the last post, I discussed the complexity of DNF minimization given a dataset. Specifically, given a dataset of input/output pairs, how hard is it to compute the smallest [...]
Theory Dish 