All reports by Author Tom Gur:

__
TR22-177
| 7th December 2022
__

Vahid Reza Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian#### Quantum Worst-Case to Average-Case Reductions for All Linear Problems

__
TR22-020
| 18th February 2022
__

Vahid Reza Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar#### Worst-Case to Average-Case Reductions via Additive Combinatorics

__
TR21-174
| 29th November 2021
__

Tom Gur, Min-Hsiu Hsieh, Sathyawageeswar Subramanian#### Sublinear quantum algorithms for estimating von Neumann entropy

__
TR21-168
| 17th November 2021
__

Tom Gur, Noam Lifshitz, Siqi Liu#### Hypercontractivity on High Dimensional Expanders: Approximate Efron-Stein Decompositions for $\epsilon$-Product Spaces

Revisions: 2

__
TR21-068
| 8th May 2021
__

Marcel Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler#### Quantum Proofs of Proximity

__
TR20-185
| 1st December 2020
__

Srinivasan Arunachalam, Alex Grilo, Tom Gur, Igor Oliveira, Aarthi Sundaram#### Quantum learning algorithms imply circuit lower bounds

Revisions: 1

__
TR20-154
| 10th October 2020
__

Marcel Dall'Agnol, Tom Gur, Oded Lachish#### A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy

__
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-056
| 11th April 2019
__

Tom Gur, Oded Lachish#### A Lower Bound for Relaxed Locally Decodable Codes

Revisions: 1

__
TR18-083
| 25th April 2018
__

Tom Gur, Yang P. Liu, Ron D. Rothblum#### An Exponential Separation Between MA and AM Proofs of Proximity

Revisions: 2

__
TR18-050
| 15th March 2018
__

Irit Dinur, Oded Goldreich, Tom Gur#### Every set in P is strongly testable under a suitable encoding

__
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

__
TR18-008
| 10th January 2018
__

Tom Gur, Igor Shinkar#### An Entropy Lower Bound for Non-Malleable Extractors

__
TR17-155
| 13th October 2017
__

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

Revisions: 1

__
TR17-143
| 26th September 2017
__

Tom Gur, Govind Ramnarayan, Ron Rothblum#### Relaxed Locally Correctable Codes

Revisions: 1

__
TR17-029
| 18th February 2017
__

Clement Canonne, Tom Gur#### An Adaptivity Hierarchy Theorem for Property Testing

Revisions: 1

__
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

__
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

__
TR16-042
| 19th March 2016
__

Oded Goldreich, Tom Gur#### Universal Locally Testable Codes

Revisions: 2

__
TR15-024
| 16th February 2015
__

Oded Goldreich, Tom Gur, Ron Rothblum#### Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs

__
TR14-025
| 25th February 2014
__

Oded Goldreich, Tom Gur, Ilan Komargodski#### Strong Locally Testable Codes with Relaxed Local Decoders

__
TR13-078
| 28th May 2013
__

Tom Gur, Ron Rothblum#### Non-Interactive Proofs of Proximity

Revisions: 1

__
TR13-020
| 2nd February 2013
__

Tom Gur, Ran Raz#### Arthur-Merlin Streaming Complexity

__
TR12-031
| 4th April 2012
__

Tom Gur, Omer Tamuz#### Testing Booleanity and the Uncertainty Principle

Revisions: 1

Vahid Reza Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian

We study the problem of designing worst-case to average-case reductions for quantum algorithms. For all linear problems, we provide an explicit and efficient transformation of quantum algorithms that are only correct on a small (even sub-constant) fraction of their inputs into ones that are correct on all inputs. This stands ... more >>>

Vahid Reza Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar

We present a new framework for designing worst-case to average-case reductions. For a large class of problems, it provides an explicit transformation of algorithms running in time $T$ that are only correct on a small (subconstant) fraction of their inputs into algorithms running in time $\widetilde{O}(T)$ that are correct on ... more >>>

Tom Gur, Min-Hsiu Hsieh, Sathyawageeswar Subramanian

Entropy is a fundamental property of both classical and quantum systems, spanning myriad theoretical and practical applications in physics and computer science. We study the problem of obtaining estimates to within a multiplicative factor $\gamma>1$ of the Shannon entropy of probability distributions and the von Neumann entropy of mixed quantum ... more >>>

Tom Gur, Noam Lifshitz, Siqi Liu

We prove hypercontractive inequalities on high dimensional expanders. As in the settings of the p-biased hypercube, the symmetric group, and the Grassmann scheme, our inequalities are effective for global functions, which are functions that are not significantly affected by a restriction of a small set of coordinates. As applications, we ... more >>>

Marcel Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler

We initiate the systematic study of QMA algorithms in the setting of property testing, to which we refer as QMA proofs of proximity (QMAPs). These are quantum query algorithms that receive explicit access to a sublinear-size untrusted proof and are required to accept inputs having a property $\Pi$ and reject ... more >>>

Srinivasan Arunachalam, Alex Grilo, Tom Gur, Igor Oliveira, Aarthi Sundaram

We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Specifically, let $\mathrm{C}$ be a class of polynomial-size concepts, and suppose that $\mathrm{C}$ can be PAC-learned with membership queries under the uniform distribution with error $1/2 - \gamma$ by a time $T$ quantum algorithm. ... more >>>

Marcel Dall'Agnol, Tom Gur, Oded Lachish

We prove a general structural theorem for a wide family of local algorithms, which includes property testers, local decoders, and PCPs of proximity. Namely, we show that the structure of every algorithm that makes $q$ adaptive queries and satisfies a natural robustness condition admits a sample-based algorithm with $n^{1- 1/O(q^2 ... more >>>

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

Tom Gur, Oded Lachish

A locally decodable code (LDC) C:{0,1}^k -> {0,1}^n is an error correcting code wherein individual bits of the message can be recovered by only querying a few bits of a noisy codeword. LDCs found a myriad of applications both in theory and in practice, ranging from probabilistically checkable proofs to ... more >>>

Tom Gur, Yang P. Liu, Ron D. Rothblum

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

Irit Dinur, Oded Goldreich, Tom Gur

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

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

Tom Gur, Igor Shinkar

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

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

Tom Gur, Govind Ramnarayan, Ron Rothblum

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

Clement Canonne, Tom Gur

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

Oded Goldreich, Tom Gur

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

Eric Blais, Clement Canonne, Tom Gur

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

Oded Goldreich, Tom Gur

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

Oded Goldreich, Tom Gur, Ron Rothblum

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

Oded Goldreich, Tom Gur, Ilan Komargodski

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

Tom Gur, Ron Rothblum

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

Tom Gur, Ran Raz

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 >>>Tom Gur, Omer Tamuz

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