Theory Dish

ITCS 2022 Call for Papers is out. Submission deadline is pretty soon: All papers should be pre-registered with title, authors, and abstract, by September 5, 7:59PM EDT [...]

Call for Participation: APPROX/RANDOM 2021 The 25th International Workshop on Randomization and Computation (RANDOM 2021) and the 24th International Workshop on Approximation [...]

Continuing our previous discussion, I will show another application of the new recipe described in the previous post (i.e., constructing a “good” polynomial for a [...]

In the previous post, we did two examples of proving average-case fine-grained hardness via worst-case to average-case reductions. In this post, I want to continue the [...]

I recently finished my qualifying exam for which I surveyed worst-case to average-case reductions for problems in NP. As part of my survey, I reviewed recent results on [...]

Suppose that is an unknown binary string of length . We are asked to recover from its traces, and each trace is a random subsequence obtained by deleting the bits of [...]

As part of my Ph.D. qualifying exam, I gave a survey talk on some of the recent progress in practical multi-party computation (MPC). After the talk, Omer Reingold asked me [...]

The sunflower lemma describes an interesting combinatorial property of set families: any large family of small sets must contain a large sunflower—a sub-family [...]

Editorial note: this post has been written in celebration of 25 years for “TOC: a Scientific Perspective (1996),” by Oded Goldreich and Avi Wigderson. In the process, I [...]

In our previous post, we discussed the automation of error correcting codes and how formal methods are quite helpful toward this goal. In this post, we will discuss machine [...]