Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Tom Gur:

TR18-083 | 25th April 2018
Tom Gur, Ron D. Rothblum, Yang P. Liu

An Exponential Separation Between MA and AM Proofs of Proximity

Revisions: 2

Non-interactive proofs of proximity allow a sublinear-time verifier to check that
a given input is close to the language, given access to a short proof. Two natural
variants of such proof systems are MA-proofs of Proximity (MAP), in which the proof
is a function of the input only, and AM-proofs ... more >>>

TR18-050 | 15th March 2018
Irit Dinur, Oded Goldreich, Tom Gur

Every set in P is strongly testable under a suitable encoding

We show that every set in $\cal P$ is strongly testable under a suitable encoding. By ``strongly testable'' we mean having a (proximity oblivious) tester that makes a constant number of queries and rejects with probability that is proportional to the distance of the tested object from the property. By ... more >>>

TR18-044 | 5th March 2018
Alessandro Chiesa, Michael Forbes, Tom Gur, Nicholas Spooner

Spatial Isolation Implies Zero Knowledge Even in a Quantum World

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

TR18-008 | 10th January 2018
Tom Gur, Igor Shinkar

An Entropy Lower Bound for Non-Malleable Extractors

A (k,\eps)-non-malleable extractor is a function nmExt : {0,1}^n x {0,1}^d -> {0,1} that takes two inputs, a weak source X~{0,1}^n of min-entropy k and an independent uniform seed s in {0,1}^d, and outputs a bit nmExt(X, s) that is \eps-close to uniform, even given the seed s and the ... more >>>

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

Proofs of Proximity for Distribution Testing

Revisions: 1

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-143 | 26th September 2017
Tom Gur, Govind Ramnarayan, Ron Rothblum

Relaxed Locally Correctable Codes

Revisions: 1

Locally decodable codes (LDCs) and locally correctable codes (LCCs) are error-correcting codes in which individual bits of the message and codeword, respectively, can be recovered by querying only few bits from a noisy codeword. These codes have found numerous applications both in theory and in practice.

A natural relaxation of ... more >>>

TR17-029 | 18th February 2017
Clement Canonne, Tom Gur

An Adaptivity Hierarchy Theorem for Property Testing

Revisions: 1

Adaptivity is known to play a crucial role in property testing. In particular, there exist properties for which there is an exponential gap between the power of \emph{adaptive} testing algorithms, wherein each query may be determined by the answers received to prior queries, and their \emph{non-adaptive} counterparts, in which all ... more >>>

TR16-192 | 25th November 2016
Oded Goldreich, Tom Gur

Universal Locally Verifiable Codes and 3-Round Interactive Proofs of Proximity for CSP

Revisions: 2 , Comments: 1

Universal locally testable codes (Universal-LTCs), recently introduced in our companion paper [GG16], are codes that admit local tests for membership in numerous possible subcodes, allowing for testing properties of the encoded message. In this work, we initiate the study of the NP analogue of these codes, wherein the testing procedures ... more >>>

TR16-168 | 2nd November 2016
Eric Blais, Clement Canonne, Tom Gur

Alice and Bob Show Distribution Testing Lower Bounds (They don't talk to each other anymore.)

Revisions: 1

We present a new methodology for proving distribution testing lower bounds, establishing a connection between distribution testing and the simultaneous message passing (SMP) communication model. Extending the framework of Blais, Brody, and Matulef [BBM12], we show a simple way to reduce (private-coin) SMP problems to distribution testing problems. This method ... more >>>

TR16-042 | 19th March 2016
Oded Goldreich, Tom Gur

Universal Locally Testable Codes

Revisions: 2

We initiate a study of ``universal locally testable codes" (universal-LTCs). These codes admit local tests for membership in numerous possible subcodes, allowing for testing properties of the encoded message. More precisely, a universal-LTC $C:\{0,1\}^k \to \{0,1\}^n$ for a family of functions $\mathcal{F} = \{ f_i : \{0,1\}^k \to \{0,1\} \}_{i ... more >>>

TR15-024 | 16th February 2015
Oded Goldreich, Tom Gur, Ron Rothblum

Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs

Proofs of proximity are probabilistic proof systems in which the verifier only queries a sub-linear number of input bits, and soundness only means that, with high probability, the input is close to an accepting input. In their minimal form, called Merlin-Arthur proofs of proximity (MAP), the verifier receives, in addition ... more >>>

TR14-025 | 25th February 2014
Oded Goldreich, Tom Gur, Ilan Komargodski

Strong Locally Testable Codes with Relaxed Local Decoders

Locally testable codes (LTCs) are error-correcting codes
that admit very efficient codeword tests. An LTC is said to
be strong if it has a proximity-oblivious tester;
that is, a tester that makes only a constant number of queries
and reject non-codewords with probability that depends solely
on their distance from ... more >>>

TR13-078 | 28th May 2013
Tom Gur, Ron Rothblum

Non-Interactive Proofs of Proximity

Revisions: 1

We initiate a study of non-interactive proofs of proximity. These proof-systems consist of a verifier that wishes to ascertain the validity of a given statement, using a short (sublinear length) explicitly given proof, and a sublinear number of queries to its input. Since the verifier cannot even read the entire ... more >>>

TR13-020 | 2nd February 2013
Tom Gur, Ran Raz

Arthur-Merlin Streaming Complexity

We study the power of Arthur-Merlin probabilistic proof systems in the data stream model. We show a canonical $\mathcal{AM}$ streaming algorithm for a wide class of data stream problems. The algorithm offers a tradeoff between the length of the proof and the space complexity that is needed to verify it.

... more >>>

TR12-031 | 4th April 2012
Tom Gur, Omer Tamuz

Testing Booleanity and the Uncertainty Principle

Revisions: 1

Let $f:\{-1,1\}^n \to \mathbb{R}$ be a real function on the hypercube, given
by its discrete Fourier expansion, or, equivalently, represented as
a multilinear polynomial. We say that it is Boolean if its image is
in $\{-1,1\}$.

We show that every function on the hypercube with a ... more >>>

ISSN 1433-8092 | Imprint