Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Justin Holmgren:

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)

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 >>>

TR20-120 | 12th August 2020
Justin Holmgren, Ran Raz

A Parallel Repetition Theorem for the GHZ Game

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 >>>

TR20-038 | 15th March 2020
Ofer Grossman, Justin Holmgren

Error Correcting Codes for Uncompressed Messages

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 >>>

TR20-035 | 23rd February 2020
Justin Holmgren

No-Signaling MIPs and Faster-Than-Light Communication, Revisited

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 >>>

TR18-161 | 13th September 2018
Justin Holmgren, Ron Rothblum

Delegating Computations with (almost) Minimal Time and Space Overhead

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 >>>

TR18-121 | 20th June 2018
Justin Holmgren, Lisa Yang

Characterizing Parallel Repetition of Non-Signaling Games: Counterexamples and a Dichotomy Theorem

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 >>>

TR17-178 | 24th November 2017
Justin Holmgren, Lisa Yang

(A Counterexample to) Parallel Repetition for Non-Signaling Multi-Player Games

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 >>>

TR16-077 | 12th May 2016
Zvika Brakerski, Justin Holmgren, Yael Tauman Kalai

Non-Interactive RAM and Batch NP Delegation from any PIR

Revisions: 1

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 >>>

ISSN 1433-8092 | Imprint