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 [...]
DNF Minimization, Part I
Given a dataset consisting of input/output pairs, how do you find a small DNF consistent with the data? This problem is known as DNF minimization and has appeared in various [...]
RANDOM & APPROX 2023
Guest post by the 2023 Program Committee Chairs: Nicole Megow (APPROX) and Adam Smith (RANDOM) The 27th International Workshop on Randomization and Computation (RANDOM [...]
2023 Motwani Postdoc Announced
The theory group at Stanford invites applications for the Motwani postdoctoral fellowship in theoretical computer science. Information and application instructions below. [...]
