8 citations · 8 across the 3 of their papers we have counts for
5 papers
Improved lower bounds for decomposable randomized encoding
Justin Holmgren, Kewen Wu
A decomposable randomized encoding (DRE) for a function allows parties, using shared randomness, to encode their individual inputs locally so that the collection of encodin…
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…
A Parallel Repetition Theorem for the GHZ Game
Justin Holmgren, Ran Raz
We prove that parallel repetition of the (3-player) GHZ game reduces the value of the game polynomially fast to 0. That is, the value of the GHZ game repeated in parallel times…
Counterexamples to the Low-Degree Conjecture
Justin Holmgren, Alexander S. Wein
A conjecture of Hopkins (2018) posits that for certain high-dimensional hypothesis testing problems, no polynomial-time algorithm can outperform so-called "simple statistics", whic…