Theory Dish

The theory group at Stanford invites applications for the Motwani postdoctoral fellowship in theoretical computer science. Information and application instructions below. [...]

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

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

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

Guest post by the 2023 Program Committee Chairs: Nicole Megow (APPROX) and  Adam Smith (RANDOM) The 27th International Workshop on Randomization and Computation (RANDOM [...]

The theory group at Stanford invites applications for the Motwani postdoctoral fellowship in theoretical computer science. Information and application instructions below. [...]

The 9th TOCA-SV day is Coming on Friday 11/18/22, in the Google campus in Mountain View. It is free but you need to register here, where you can also see an up-to-date list [...]

From the orgenizers: =============== You are cordially invited to the TCS Women Spotlight Workshop! The workshop will be held on Monday, June 20, 2022, in Rome, Italy, as [...]