Theory Dish

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

Introduction. For nearly a century, error-correcting codes (ECCs) have been used for allowing communication even when the used communication channel is corrupted by noise. [...]

After discussing postdoc opportunities with me and the opportunities as part of the Simons Collaboration on the Theory of Algorithmic Fairness, let me conclude with postdoc [...]

As promised, more postdoctoral positions now available for 2021 The Simons Collaboration on the Theory of Algorithmic Fairness seek highly qualified candidates (within five [...]