63 citations · 124 across the 20 of their papers we have counts for
12 papers · 1 filter
On the works of Avi Wigderson
Boaz Barak, Yael Kalai, Ran Raz +2
This is an overview of some of the works of Avi Wigderson, 2021 Abel prize laureate. Wigderson's contributions span many fields of computer science and mathematics. In this survey…
Certified Hardness vs. Randomness for Log-Space
Edward Pyne, Ran Raz, Wei Zhan
Let be a language that can be decided in linear space and let be any constant. Let be the exponential hardness assumption that for every , memb…
Polynomial Bounds On Parallel Repetition For All 3-Player Games With Binary Inputs
Uma Girish, Kunal Mittal, Ran Raz +1
We prove that for every 3-player (3-prover) game with value less than one, whose query distribution has the support of ham…
Parallel Repetition For All 3-Player Games Over Binary Alphabet
Uma Girish, Justin Holmgren, Kunal Mittal +2
We prove that for every 3-player game with binary questions and answers and value , the value of the -fold parallel repetition of the game decays polynomially fast to 0. Tha…
Parallel Repetition for the GHZ Game: A Simpler Proof
Uma Girish, Justin Holmgren, Kunal Mittal +2
We give a new proof of the fact that the parallel repetition of the (3-player) GHZ game reduces the value of the game to zero polynomially quickly. That is, we show that the value…
Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing Machines
Kunal Mittal, Ran Raz
We prove that a sufficiently strong parallel repetition theorem for a special case of multiplayer (multiprover) games implies super-linear lower bounds for multi-tape Turing machin…