All reports by Author Justin Holmgren:

__
TR23-113
| 8th August 2023
__

Justin Holmgren, Ron Rothblum#### Linear-Size Boolean Circuits for Multiselection

__
TR22-039
| 14th March 2022
__

Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan#### Parallel Repetition For All 3-Player Games Over Binary Alphabet

__
TR21-101
| 13th July 2021
__

Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan#### A Parallel Repetition Theorem for the GHZ Game: A Simpler Proof

Revisions: 1

__
TR21-032
| 5th March 2021
__

Justin Holmgren, Alex Lombardi, Ron Rothblum#### Fiat-Shamir via List-Recoverable Codes (or: Parallel Repetition of GMW is not Zero-Knowledge)

__
TR20-120
| 12th August 2020
__

Justin Holmgren, Ran Raz#### A Parallel Repetition Theorem for the GHZ Game

__
TR20-038
| 15th March 2020
__

Ofer Grossman, Justin Holmgren#### Error Correcting Codes for Uncompressed Messages

__
TR20-035
| 23rd February 2020
__

Justin Holmgren#### No-Signaling MIPs and Faster-Than-Light Communication, Revisited

__
TR18-161
| 13th September 2018
__

Justin Holmgren, Ron Rothblum#### Delegating Computations with (almost) Minimal Time and Space Overhead

__
TR18-121
| 20th June 2018
__

Justin Holmgren, Lisa Yang#### Characterizing Parallel Repetition of Non-Signaling Games: Counterexamples and a Dichotomy Theorem

__
TR17-178
| 24th November 2017
__

Justin Holmgren, Lisa Yang#### (A Counterexample to) Parallel Repetition for Non-Signaling Multi-Player Games

__
TR16-077
| 12th May 2016
__

Zvika Brakerski, Justin Holmgren, Yael Tauman Kalai#### Non-Interactive RAM and Batch NP Delegation from any PIR

Revisions: 1

Justin Holmgren, Ron Rothblum

We study the circuit complexity of the multiselection problem: given an input string $x \in \{0,1\}^n$ along with indices $i_1,\dots,i_q \in [n]$, output $(x_{i_1},\dots,x_{i_q})$. A trivial lower bound for the circuit size is the input length $n + q \cdot \log(n)$, but the straightforward construction has size $\Theta(q \cdot n)$.

... more >>>Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan

We prove that for every 3-player (3-prover) game, with binary questions and answers and value less than $1$, the value of the $n$-fold parallel repetition of the game decays polynomially fast to $0$. That is, for every such game, there exists a constant $c>0$, such that the value of the ... more >>>

Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan

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 of the $n$-fold GHZ game is at most $n^{-\Omega(1)}$. This was first established by Holmgren and ... more >>>

Justin Holmgren, Alex Lombardi, Ron Rothblum

Shortly after the introduction of zero-knowledge proofs, Goldreich, Micali and Wigderson (CRYPTO '86) demonstrated their wide applicability by constructing zero-knowledge proofs for the NP-complete problem of graph 3-coloring. A long-standing open question has been whether parallel repetition of their protocol preserves zero knowledge. In this work, we answer this question ... more >>>

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 $t$ times is at most $t^{-\Omega(1)}$. Previously, only a bound of $\approx \frac{1}{\alpha(t)}$, where $\alpha$ is the inverse Ackermann ... more >>>

Ofer Grossman, Justin Holmgren

Most types of messages we transmit (e.g., video, audio, images, text) are not fully compressed, since they do not have known efficient and information theoretically optimal compression algorithms. When transmitting such messages, standard error correcting codes fail to take advantage of the fact that messages are not fully compressed.

We ... more >>>

Justin Holmgren

We revisit one original motivation for the study of no-signaling multi-prover

interactive proofs (NS-MIPs): specifically, that two spatially separated

provers are guaranteed to be no-signaling by the physical principle that

information cannot travel from one point to another faster than light.

We observe that with ... more >>>

Justin Holmgren, Ron Rothblum

The problem of verifiable delegation of computation considers a setting in which a client wishes to outsource an expensive computation to a powerful, but untrusted, server. Since the client does not trust the server, we would like the server to certify the correctness of the result. Delegation has emerged as ... more >>>

Justin Holmgren, Lisa Yang

Non-signaling games are an important object of study in the theory of computation, for their role both in quantum information and in (classical) cryptography. In this work, we study the behavior of these games under parallel repetition.

We show that, unlike the situation both for classical games and for two-player ... more >>>

Justin Holmgren, Lisa Yang

We give a three-player game whose non-signaling value is constant (2/3) under any number of parallel repetitions. This is the first known setting where parallel repetition completely fails to reduce the maximum winning probability of computationally unbounded players.

We also show that the best known results on non-signaling ...
more >>>

Zvika Brakerski, Justin Holmgren, Yael Tauman Kalai

We present an adaptive and non-interactive protocol for verifying arbitrary efficient computations in fixed polynomial time. Our protocol is computationally sound and can be based on any computational PIR scheme, which in turn can be based on standard polynomial-time cryptographic assumptions (e.g. the worst case hardness of polynomial-factor approximation of ... more >>>