Theory Dish

The chain rule is a fundamental result in calculus. Roughly speaking, it states that if a variable is a differentiable function of intermediate variables , and each [...]

From Sofya Raskhodnikova *** Submission Deadline Change***: You are invited to submit your papers to the 17th INTERNATIONAL COMPUTER SCIENCE SYMPOSIUM IN RUSSIA (CSR 2022). [...]

ITCS 2022 Call for Papers has been updated with the registration and submission deadlines slightly extended. Deadlines are still very soon (especially registration). All [...]

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