Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Alessandro Chiesa:

TR17-155 | 13th October 2017
Alessandro Chiesa, Tom Gur

Proofs of Proximity for Distribution Testing

Distribution testing is an area of property testing that studies algorithms that receive few samples from a probability distribution D and decide whether D has a certain property or is far (in total variation distance) from all distributions with that property. Most natural properties of distributions, however, require a large ... more >>>

TR17-110 | 22nd June 2017
Alessandro Chiesa, Peter Manohar, Igor Shinkar

On Axis-Parallel Tests for Tensor Product Codes

Many low-degree tests examine the input function via its restrictions to random hyperplanes of a certain dimension. Examples include the line-vs-line (Arora, Sudan 2003), plane-vs-plane (Raz, Safra 1997), and cube-vs-cube (Bhangale, Dinur, Livni 2017) tests.

In this paper we study a test introduced by Ben-Sasson and Sudan in 2006 that ... more >>>

TR17-057 | 7th April 2017
Alessandro Chiesa, Michael Forbes, Nicholas Spooner

A Zero Knowledge Sumcheck and its Applications

Many seminal results in Interactive Proofs (IPs) use algebraic techniques based on low-degree polynomials, the study of which is pervasive in theoretical computer science. Unfortunately, known methods for endowing such proofs with zero knowledge guarantees do not retain this rich algebraic structure.

In this work, we develop algebraic techniques for ... more >>>

TR16-156 | 12th October 2016
Eli Ben-Sasson, Alessandro Chiesa, Michael Forbes, Ariel Gabizon, Michael Riabzev, Nicholas Spooner

On Probabilistic Checking in Perfect Zero Knowledge

Revisions: 1

We present the first constructions of *single*-prover proof systems that achieve *perfect* zero knowledge (PZK) for languages beyond NP, under no intractability assumptions:

1. The complexity class #P has PZK proofs in the model of Interactive PCPs (IPCPs) [KR08], where the verifier first receives from the prover a PCP and ... more >>>

TR16-046 | 23rd March 2016
Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, Nicholas Spooner

Short Interactive Oracle Proofs with Constant Query Complexity, via Composition and Sumcheck

Revisions: 2

We study *interactive oracle proofs* (IOPs) (Ben-Sasson, Chiesa, Spooner '16), which combine aspects of probabilistically checkable proofs (PCPs) and interactive proofs (IPs). We present IOP constructions and general techniques that enable us to obtain tradeoffs in proof length versus query complexity that are not known to be achievable via PCPs ... more >>>

TR16-001 | 9th January 2016
Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Madars Virza

Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs

Revisions: 1

The seminal result that every language having an interactive proof also has a zero-knowledge interactive proof assumes the existence of one-way functions. Ostrovsky and Wigderson (ISTCS 1993) proved that this assumption is necessary: if one-way functions do not exist, then only languages in BPP have zero-knowledge interactive proofs.

Ben-Or et ... more >>>

TR12-045 | 22nd April 2012
Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer

On the Concrete-Efficiency Threshold of Probabilistically-Checkable Proofs

Revisions: 3

Probabilistically-Checkable Proofs (PCPs) form the algorithmic core that enables succinct verification of long proofs/computations in many cryptographic constructions, such as succinct arguments and proof-carrying data.

Despite the wonderful asymptotic savings they bring, PCPs are also the infamous computational bottleneck preventing these cryptographic constructions from being used in practice. This reflects ... more >>>

TR11-110 | 10th August 2011
Alessandro Chiesa, Michael Forbes

Improved Soundness for QMA with Multiple Provers

Revisions: 1

We present three contributions to the understanding of QMA with multiple provers:

1) We give a tight soundness analysis of the protocol of [Blier and Tapp, ICQNM '09], yielding a soundness gap $\Omega(N^{-2})$, which is the best-known soundness gap for two-prover QMA protocols with logarithmic proof size. Maybe ... more >>>

ISSN 1433-8092 | Imprint