All reports by Author Alessandro Chiesa:

__
TR20-113
| 27th July 2020
__

Alessandro Chiesa, Tom Gur, Igor Shinkar#### Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity

__
TR19-070
| 14th May 2019
__

Alessandro Chiesa, Peter Manohar, Igor Shinkar#### On Local Testability in the Non-Signaling Setting

Revisions: 1

__
TR18-123
| 3rd July 2018
__

Alessandro Chiesa, Peter Manohar, Igor Shinkar#### Probabilistic Checking against Non-Signaling Strategies from Linearity Testing

Revisions: 1

__
TR18-067
| 9th April 2018
__

Alessandro Chiesa, Peter Manohar, Igor Shinkar#### Testing Linearity against Non-Signaling Strategies

Revisions: 1

__
TR18-044
| 5th March 2018
__

Alessandro Chiesa, Michael Forbes, Tom Gur, Nicholas Spooner#### Spatial Isolation Implies Zero Knowledge Even in a Quantum World

Revisions: 1

__
TR17-155
| 13th October 2017
__

Alessandro Chiesa, Tom Gur#### Proofs of Proximity for Distribution Testing

Revisions: 1

__
TR17-110
| 22nd June 2017
__

Alessandro Chiesa, Peter Manohar, Igor Shinkar#### On Axis-Parallel Tests for Tensor Product Codes

__
TR17-057
| 7th April 2017
__

Alessandro Chiesa, Michael Forbes, Nicholas Spooner#### A Zero Knowledge Sumcheck and its Applications

__
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

__
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

__
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

__
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

__
TR11-110
| 10th August 2011
__

Alessandro Chiesa, Michael Forbes#### Improved Soundness for QMA with Multiple Provers

Revisions: 1

Alessandro Chiesa, Tom Gur, Igor Shinkar

Locally correctable codes (LCCs) are error correcting codes C : \Sigma^k \to \Sigma^n which admit local algorithms that correct any individual symbol of a corrupted codeword via a minuscule number of queries. This notion is stronger than that of locally decodable codes (LDCs), where the goal is to only recover ... more >>>

Alessandro Chiesa, Peter Manohar, Igor Shinkar

Non-signaling strategies are a generalization of quantum strategies that have been studied in physics for decades, and have recently found applications in theoretical computer science. These applications motivate the study of local-to-global phenomena for non-signaling functions.

We present general results about the local testability of linear codes in the non-signaling ... more >>>

Alessandro Chiesa, Peter Manohar, Igor Shinkar

Non-signaling strategies are a generalization of quantum strategies that have been studied in physics over the past three decades. Recently, they have found applications in theoretical computer science, including to proving inapproximability results for linear programming and to constructing protocols for delegating computation. A central tool for these applications is ... more >>>

Alessandro Chiesa, Peter Manohar, Igor Shinkar

Non-signaling strategies are collections of distributions with certain non-local correlations. They have been studied in Physics as a strict generalization of quantum strategies to understand the power and limitations of Nature's apparent non-locality. Recently, they have received attention in Theoretical Computer Science due to connections to Complexity and Cryptography.

We ... more >>>

Alessandro Chiesa, Michael Forbes, Tom Gur, Nicholas Spooner

Zero knowledge plays a central role in cryptography and complexity. The seminal work of Ben-Or et al. (STOC 1988) shows that zero knowledge can be achieved unconditionally for any language in NEXP, as long as one is willing to make a suitable physical assumption: if the provers are spatially isolated, ... more >>>

Alessandro Chiesa, Tom Gur

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

Alessandro Chiesa, Peter Manohar, Igor Shinkar

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

Alessandro Chiesa, Michael Forbes, Nicholas Spooner

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

Eli Ben-Sasson, Alessandro Chiesa, Michael Forbes, Ariel Gabizon, Michael Riabzev, Nicholas Spooner

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

Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, Nicholas Spooner

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

Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Madars Virza

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

Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer

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

Alessandro Chiesa, Michael Forbes

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