All reports by Author Oded Goldreich:

__
TR23-064
| 3rd May 2023
__

Oded Goldreich#### On the Lower Bound on the Length of Relaxed Locally Decodable Codes

__
TR23-034
| 24th March 2023
__

Oded Goldreich#### On teaching the approximation method for circuit lower bounds

Revisions: 1

__
TR22-184
| 28th December 2022
__

Oded Goldreich, Laliv Tauber#### Testing in the bounded-degree graph model with degree bound two

__
TR22-124
| 9th September 2022
__

Oded Goldreich, Guy Rothblum, Tal Skverer#### On Interactive Proofs of Proximity with Proof-Oblivious Queries

Revisions: 3

__
TR22-013
| 5th February 2022
__

Nader Bshouty, Oded Goldreich#### On properties that are non-trivial to test

__
TR21-181
| 30th December 2021
__

Oded Goldreich#### The KW Games as a Teaser

__
TR21-175
| 6th December 2021
__

Oded Goldreich#### On the Locally Testable Code of Dinur et al. (2021)

Revisions: 1

__
TR21-133
| 12th September 2021
__

Oded Goldreich, Dana Ron#### Testing Distributions of Huge Objects

Revisions: 3

__
TR21-129
| 6th September 2021
__

Oded Goldreich, Dana Ron#### A Lower Bound on the Complexity of Testing Grained Distributions

__
TR21-088
| 23rd June 2021
__

Oded Goldreich#### Open Problems in Property Testing of Graphs

Revisions: 1

__
TR21-034
| 9th March 2021
__

Oded Goldreich#### Robust Self-Ordering versus Local Self-Ordering

Revisions: 1

__
TR20-192
| 27th December 2020
__

Oded Goldreich, Avi Wigderson#### Constructing Large Families of Pairwise Far Permutations: Good Permutation Codes Based on the Shuffle-Exchange Network

__
TR20-160
| 2nd November 2020
__

Oded Goldreich, Avi Wigderson#### Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model

Revisions: 3

__
TR20-149
| 29th September 2020
__

Oded Goldreich, Avi Wigderson#### Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing

Revisions: 2

__
TR20-118
| 5th August 2020
__

Oded Goldreich#### On Testing Asymmetry in the Bounded Degree Graph Model

Revisions: 4

__
TR20-109
| 19th July 2020
__

Oded Goldreich#### On Testing Hamiltonicity in the Bounded Degree Graph Model

Revisions: 2

__
TR20-104
| 12th July 2020
__

Oded Goldreich#### On Counting $t$-Cliques Mod 2

Revisions: 3

__
TR20-068
| 3rd May 2020
__

Oded Goldreich, Dana Ron#### One-Sided Error Testing of Monomials and Affine Subspaces

Revisions: 2

__
TR20-054
| 22nd April 2020
__

Marshall Ball, Oded Goldreich, Tal Malkin#### Communication Complexity with Defective Randomness

Revisions: 3

__
TR19-183
| 21st December 2019
__

Marshall Ball, Oded Goldreich, Tal Malkin#### Randomness Extraction from Somewhat Dependent Sources

Revisions: 1

__
TR19-171
| 27th November 2019
__

Oded Goldreich#### Improved bounds on the AN-complexity of multilinear functions

Revisions: 5

__
TR19-102
| 10th August 2019
__

Oded Goldreich#### Testing Isomorphism in the Bounded-Degree Graph Model

Revisions: 1

__
TR19-088
| 16th June 2019
__

Oded Goldreich#### On the Complexity of Estimating the Effective Support Size

Revisions: 1

__
TR19-078
| 1st June 2019
__

Itai Benjamini, Oded Goldreich#### Pseudo-Mixing Time of Random Walks

__
TR19-012
| 27th January 2019
__

Oded Goldreich#### Multi-pseudodeterministic algorithms

Revisions: 1

__
TR18-171
| 10th October 2018
__

Oded Goldreich#### Testing Graphs in Vertex-Distribution-Free Models

Revisions: 1

__
TR18-104
| 29th May 2018
__

Oded Goldreich#### Flexible models for testing graph properties

Revisions: 1

__
TR18-098
| 17th May 2018
__

Oded Goldreich#### Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity

Revisions: 1

__
TR18-069
| 14th April 2018
__

Oded Goldreich, Guy Rothblum#### Constant-round interactive proof systems for AC0[2] and NC1

Revisions: 1

__
TR18-050
| 15th March 2018
__

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

__
TR18-046
| 9th March 2018
__

Oded Goldreich, Guy Rothblum#### Counting $t$-cliques: Worst-case to average-case reductions and Direct interactive proof systems

Revisions: 2

__
TR18-045
| 6th March 2018
__

Oded Goldreich, Dana Ron#### The Subgraph Testing Model

Revisions: 2

__
TR17-193
| 31st December 2017
__

Oded Goldreich, Avishay Tal#### On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions

__
TR17-130
| 30th August 2017
__

Oded Goldreich, Guy Rothblum#### Worst-case to Average-case reductions for subclasses of P

Revisions: 4

__
TR17-102
| 9th June 2017
__

Oded Goldreich#### Overview of the doubly-efficient interactive proof systems of RRR

__
TR17-101
| 8th June 2017
__

Oded Goldreich#### On the doubly-efficient interactive proof systems of GKR

Revisions: 1

__
TR17-018
| 6th February 2017
__

Oded Goldreich, Guy Rothblum#### Simple doubly-efficient interactive proof systems for locally-characterizable sets

Revisions: 3

__
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-152
| 27th September 2016
__

Oded Goldreich#### Deconstructing 1-local expanders

Revisions: 1

__
TR16-080
| 18th May 2016
__

Oded Goldreich#### Reducing testing affine spaces to testing linearity

Revisions: 4

__
TR16-066
| 19th April 2016
__

Oded Goldreich, Maya Leshkowitz#### On Emulating Interactive Proofs with Public Coins

__
TR16-042
| 19th March 2016
__

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

Revisions: 2

__
TR16-015
| 4th February 2016
__

Oded Goldreich#### The uniform distribution is complete with respect to testing identity to a fixed distribution

Revisions: 3

__
TR15-079
| 7th May 2015
__

Oded Goldreich, Avishay Tal#### Matrix Rigidity of Random Toeplitz Matrices

__
TR15-024
| 16th February 2015
__

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

__
TR15-003
| 3rd January 2015
__

Oded Goldreich, Emanuele Viola, Avi Wigderson#### On Randomness Extraction in AC0

__
TR14-097
| 31st July 2014
__

Oded Goldreich, Liav Teichner#### Super-Perfect Zero-Knowledge Proofs

Revisions: 1

__
TR14-029
| 4th March 2014
__

Oded Goldreich, Dana Ron#### On Learning and Testing Dynamic Environments

Revisions: 3

__
TR14-025
| 25th February 2014
__

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

__
TR13-152
| 7th November 2013
__

Oded Goldreich, Avi Wigderson#### On Derandomizing Algorithms that Err Extremely Rarely

Revisions: 2

__
TR13-109
| 11th August 2013
__

Oded Goldreich, Dana Ron#### On Sample-Based Testers

Revisions: 1

__
TR13-073
| 14th May 2013
__

Oded Goldreich#### On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing

Revisions: 2

__
TR13-067
| 2nd May 2013
__

Oded Goldreich#### On Multiple Input Problems in Property Testing

Revisions: 1

__
TR13-043
| 25th March 2013
__

Oded Goldreich, Avi Wigderson#### On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions

Revisions: 1

__
TR12-101
| 10th August 2012
__

Oded Goldreich, Shafi Goldwasser, Dana Ron#### On the possibilities and limitations of pseudodeterministic algorithms

__
TR12-035
| 5th April 2012
__

Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler#### Finding Cycles and Trees in Sublinear Time

Revisions: 1
,
Comments: 1

__
TR12-021
| 14th March 2012
__

Oded Goldreich, Igor Shinkar#### Two-Sided Error Proximity Oblivious Testing

Revisions: 4

__
TR12-012
| 9th February 2012
__

Oded Goldreich#### On the Effect of the Proximity Parameter on Property Testers

__
TR11-159
| 27th November 2011
__

Oded Goldreich, Ron Rothblum#### Enhancements of Trapdoor Permutations

Revisions: 1
,
Comments: 1

__
TR11-121
| 12th September 2011
__

Oded Goldreich, Rani Izsak#### Monotone Circuits: One-Way Functions versus Pseudorandom Generators

__
TR11-047
| 8th April 2011
__

Oded Goldreich#### Two Comments on Targeted Canonical Derandomizers

__
TR11-023
| 16th February 2011
__

Oded Goldreich, Or Meir#### Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly

Revisions: 5
,
Comments: 2

__
TR11-004
| 10th January 2011
__

Oded Goldreich, Salil Vadhan#### On the complexity of computational problems regarding distributions (a survey)

Comments: 1

__
TR10-135
| 24th August 2010
__

Oded Goldreich#### In a World of P=BPP

Revisions: 2

__
TR10-082
| 11th May 2010
__

Oded Goldreich#### Introduction to Testing Graph Properties

__
TR10-061
| 10th April 2010
__

Oded Goldreich#### On Testing Computability by Small Width OBDDs

Revisions: 2

__
TR10-058
| 7th April 2010
__

Oded Goldreich, Tali Kaufman#### Proximity Oblivious Testing and the Role of Invariances

Revisions: 1

__
TR09-075
| 17th September 2009
__

Oded Goldreich, Brendan Juba, Madhu Sudan#### A Theory of Goal-Oriented Communication

Revisions: 1
,
Comments: 1

__
TR09-031
| 6th April 2009
__

Zvika Brakerski, Oded Goldreich#### From absolute distinguishability to positive distinguishability

__
TR09-028
| 2nd April 2009
__

Oded Goldreich#### A Candidate Counterexample to the Easy Cylinders Conjecture

__
TR08-097
| 14th November 2008
__

Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg#### Hierarchy Theorems for Property Testing

Revisions: 1

__
TR08-041
| 10th April 2008
__

Oded Goldreich, Dana Ron#### On Proximity Oblivious Testing

__
TR08-039
| 7th April 2008
__

Oded Goldreich, Dana Ron#### Algorithmic Aspects of Property Testing in the Dense Graphs Model

__
TR07-062
| 15th July 2007
__

Oded Goldreich, Or Meir#### The Tensor Product of Two Good Codes Is Not Necessarily Robustly Testable

Revisions: 2

__
TR07-057
| 11th July 2007
__

Oded Goldreich#### On the Average-Case Complexity of Property Testing

Revisions: 1

__
TR07-015
| 1st March 2007
__

Oded Goldreich, Or Sheffet#### On the randomness complexity of property testing

__
TR06-136
| 22nd October 2006
__

Mihir Bellare, Oded Goldreich#### On Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge

__
TR06-099
| 17th August 2006
__

Oded Goldreich#### On Expected Probabilistic Polynomial-Time Adversaries -- A suggestion for restricted definitions and their benefits

Revisions: 1

__
TR05-098
| 4th September 2005
__

Oded Goldreich#### Bravely, Moderately: A Common Theme in Four Recent Results

__
TR05-073
| 14th July 2005
__

Oded Goldreich, Dana Ron#### Approximating Average Parameters of Graphs.

__
TR05-018
| 6th February 2005
__

Oded Goldreich#### On Promise Problems (a survey in memory of Shimon Even [1935-2004])

__
TR05-014
| 30th January 2005
__

Oded Goldreich#### Short Locally Testable Codes and Proofs (Survey)

__
TR04-093
| 9th November 2004
__

Oded Goldreich, Madhu Sudan, Luca Trevisan#### From logarithmic advice to single-bit advice

__
TR04-021
| 23rd March 2004
__

Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan#### Robust PCPs of Proximity, Shorter PCPs and Applications to Coding

__
TR04-013
| 10th February 2004
__

Oded Goldreich, Dana Ron#### On Estimating the Average Degree of a Graph.

__
TR03-045
| 8th June 2003
__

Oded Goldreich, Asaf Nussboim#### On the Implementation of Huge Random Objects

Revisions: 1

__
TR03-019
| 3rd April 2003
__

Eli Ben-Sasson, Oded Goldreich, Madhu Sudan#### Bounds on 2-Query Codeword Testing.

Revisions: 1

__
TR02-063
| 3rd December 2002
__

Oded Goldreich#### Zero-Knowledge twenty years after its invention

__
TR02-050
| 5th August 2002
__

Oded Goldreich, Madhu Sudan#### Locally Testable Codes and PCPs of Almost-Linear Length

__
TR02-049
| 4th August 2002
__

Oded Goldreich, Vered Rosen#### On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators

__
TR02-048
| 31st July 2002
__

Noga Alon, Oded Goldreich, Yishay Mansour#### Almost $k$-wise independence versus $k$-wise independence

__
TR02-047
| 3rd August 2002
__

Oded Goldreich#### The GGM Construction does NOT yield Correlation Intractable Function Ensembles.

__
TR02-039
| 30th June 2002
__

Oded Goldreich, Avi Wigderson#### Derandomization that is rarely wrong from short advice that is typically good

Comments: 1

__
TR01-102
| 18th December 2001
__

Oded Goldreich#### Using the FGLSS-reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs.

__
TR01-093
| 2nd December 2001
__

Boaz Barak, Oded Goldreich#### Universal Arguments and their Applications

__
TR01-091
| 27th November 2001
__

Oded Goldreich#### Concurrent Zero-Knowledge With Timing, Revisited

__
TR01-080
| 14th November 2001
__

Oded Goldreich, Howard Karloff, Leonard Schulman, Luca Trevisan#### Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval

Revisions: 3

__
TR01-057
| 15th August 2001
__

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, Ke Yang#### On the (Im)possibility of Obfuscating Programs

__
TR01-046
| 2nd July 2001
__

Oded Goldreich, Salil Vadhan, Avi Wigderson#### On Interactive Proofs with a Laconic Prover

__
TR01-010
| 25th January 2001
__

Oded Goldreich, Luca Trevisan#### Three Theorems regarding Testing Graph Properties.

Revisions: 1

__
TR00-090
| 3rd December 2000
__

Oded Goldreich#### Candidate One-Way Functions Based on Expander Graphs

__
TR00-056
| 20th July 2000
__

Oded Goldreich, Avi Wigderson#### On Pseudorandomness with respect to Deterministic Observers.

__
TR00-020
| 27th March 2000
__

Oded Goldreich, Dana Ron#### On Testing Expansion in Bounded-Degree Graphs

__
TR00-004
| 14th January 2000
__

Oded Goldreich, Salil Vadhan, Avi Wigderson#### Simplified derandomization of BPP using a hitting set generator.

__
TR99-042
| 24th October 1999
__

Ran Canetti, Oded Goldreich, Silvio Micali.#### Resettable Zero-Knowledge.

Revisions: 1

__
TR99-024
| 25th June 1999
__

Oded Goldreich, Silvio Micali.#### Interleaved Zero-Knowledge in the Public-Key Model.

Revisions: 1
,
Comments: 1

__
TR99-017
| 4th June 1999
__

Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky#### Improved Testing Algorithms for Monotonicity.

Revisions: 1

__
TR99-013
| 28th May 1999
__

Oded Goldreich, Amit Sahai, Salil Vadhan#### Can Statistical Zero Knowledge be made Non-Interactive? or On the Relationship of SZK and NISZK

__
TR99-002
| 22nd January 1999
__

Oded Goldreich, Daniele Micciancio, Shmuel Safra and Jean-Pierre Seifert.#### Approximating shortest lattice vectors is not harder than approximating closest lattice vectors.

__
TR98-072
| 14th December 1998
__

Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson#### Deterministic Amplification of Space Bounded Probabilistic Algorithms.

__
TR98-063
| 4th November 1998
__

Oded Goldreich, Salil Vadhan#### Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK

__
TR98-062
| 28th October 1998
__

Oded Goldreich, Dana Ron, Madhu Sudan#### Chinese Remaindering with Errors

Revisions: 4
,
Comments: 1

__
TR98-060
| 8th October 1998
__

Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan#### Learning polynomials with queries -- The highly noisy case.

__
TR98-032
| 10th June 1998
__

Mihir Bellare, Oded Goldreich, Erez Petrank#### Uniform Generation of NP-witnesses using an NP-oracle.

__
TR98-017
| 29th March 1998
__

Oded Goldreich, Madhu Sudan#### Computational Indistinguishability: A Sample Hierarchy.

__
TR98-006
| 27th January 1998
__

Alfredo De Santis, Giovanni Di Crescenzo, Oded Goldreich, Giuseppe Persiano#### The Graph Clustering Problem has a Perfect Zero-Knowledge Proof

__
TR97-058
| 2nd December 1997
__

Oded Goldreich#### Notes on Levin's Theory of Average-Case Complexity.

__
TR97-056
| 1st December 1997
__

Oded Goldreich#### Combinatorial Property Testing (a survey).

Comments: 1

__
TR97-045
| 29th September 1997
__

Oded Goldreich, David Zuckerman#### Another proof that BPP subseteq PH (and more).

Comments: 1

__
TR97-031
| 9th September 1997
__

Oded Goldreich#### On the Limits of Non-Approximability of Lattice Problems

Revisions: 2

__
TR97-028
| 12th July 1997
__

Scott E. Decatur, Oded Goldreich, Dana Ron#### Computational Sample Complexity

__
TR97-020
| 15th May 1997
__

Oded Goldreich#### A Sample of Samplers -- A Computational Perspective on Sampling (survey).

__
TR97-018
| 8th May 1997
__

Oded Goldreich, Shai Halevi#### Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem.

__
TR96-067
| 20th December 1996
__

Oded Goldreich, Bernd Meyer#### Computational Indistinguishability -- Algorithms vs. Circuits.

__
TR96-057
| 18th November 1996
__

Oded Goldreich, Dana Ron#### Property Testing and its connection to Learning and Approximation

__
TR96-056
| 12th November 1996
__

Oded Goldreich, Shai Halevi#### Public-Key Cryptosystems from Lattice Reduction Problems

__
TR96-054
| 2nd November 1996
__

Oded Goldreich#### The Graph Clustering Problem has a Perfect Zero-Knowledge Proof

Comments: 1

__
TR96-047
| 2nd September 1996
__

Oded Goldreich, Muli Safra#### A Combinatorial Consistency Lemma with application to the PCP Theorem

Revisions: 1

__
TR96-042
| 26th July 1996
__

Oded Goldreich, Shai Halevi#### Collision-Free Hashing from Lattice Problems

__
TR96-041
| 24th July 1996
__

Oded Goldreich, Avi Wigderson#### On the Circuit Complexity of Perfect Hashing

Revisions: 1
,
Comments: 2

__
TR96-018
| 23rd February 1996
__

Oded Goldreich, Johan HÃ¥stad#### On the Message Complexity of Interactive Proof Systems

Revisions: 2

__
TR95-056
| 26th November 1995
__

Oded Goldreich#### Three XOR-Lemmas -- An Exposition

__
TR95-050
| 15th October 1995
__

Oded Goldreich, Noam Nisan, Avi Wigderson#### On Yao's XOR-Lemma

Revisions: 2
,
Comments: 1

__
TR95-029
| 15th June 1995
__

Oded Goldreich, Leonid Levin, Noam Nisan#### On Constructing 1-1 One-Way Functions

__
TR95-024
| 23rd May 1995
__

Mihir Bellare, Oded Goldreich, Madhu Sudan#### Free bits, PCP and Non-Approximability - Towards tight results

Revisions: 4

__
TR94-008
| 12th December 1994
__

Oded Goldreich#### Probabilistic Proof Systems (A Survey)

__
TR94-007
| 12th December 1994
__

Oded Goldreich, Rafail Ostrovsky, Erez Petrank#### Computational Complexity and Knowledge Complexity

__
TR94-002
| 12th December 1994
__

Oded Goldreich, Avi Wigderson#### Tiny Families of Functions with Random Properties: A Quality--Size Trade--off for Hashing

Revisions: 2

Oded Goldreich

We revisit the known proof of the lower bound on the length of relaxed locally decodable codes, providing an arguably simpler exposition that yields a slightly better lower bound for the non-adaptive case and a weaker bound in the general case.

Recall that a locally decodable code is an error ... more >>>

Oded Goldreich

This text provides a basic presentation of the the approximation method of Razborov (Matematicheskie Zametki, 1987) and its application by Smolensky (19th STOC, 1987) for proving lower bounds on the size of ${\cal AC}^0[p]$-circuits that compute sums mod~$q$ (for primes $q\neq p$).

The textbook presentations of the latter result ...
more >>>

Oded Goldreich, Laliv Tauber

Considering the bounded-degree graph model, we show that if the degree bound is two,

then every graph property can be tested within query complexity that only depends on the proximity parameter.

Specifically, the query complexity is ${\rm poly}(1/\epsilon)$, where $\epsilon$ denotes the proximity parameter.

The key observation is that a ...
more >>>

Oded Goldreich, Guy Rothblum, Tal Skverer

Interactive proofs of proximity (IPPs) offer ultra-fast

approximate verification of assertions regarding their input,

where ultra-fast means that only a small portion of the input is read

and approximate verification is analogous to the notion of

approximate decision that underlies property testing.

Specifically, in an IPP, the prover can make ...
more >>>

Nader Bshouty, Oded Goldreich

In this note we show that all sets that are neither finite nor too dense are non-trivial to test in the sense that, for every $\epsilon>0$, distinguishing between strings in the set and strings that are $\epsilon$-far from the set requires $\Omega(1/\epsilon)$ queries.

Specifically, we show that if, for ...
more >>>

Oded Goldreich

This is a purely pedagogical text.

We advocate using KW-games as a teaser (or ``riddle'') for a complexity theoretic course.

In particular, stating the KW-game for a familiar NP-complete problem such as 3-Colorability and asking to prove that it requires more than polylogarithmic communication poses a seemingly tractable question ...
more >>>

Oded Goldreich

This text provides a high-level description of the locally testable code constructed by Dinur, Evra, Livne, Lubotzky, and Mozes (ECCC, TR21-151).

In particular, the group theoretic aspects are abstracted as much as possible.

Oded Goldreich, Dana Ron

We initiate a study of a new model of property testing that is a hybrid of testing properties of distributions and testing properties of strings.

Specifically, the new model refers to testing properties of distributions, but these are distributions over huge objects (i.e., very long strings).

Accordingly, the ...
more >>>

Oded Goldreich, Dana Ron

A distribution is called $m$-grained if each element appears with probability that is an integer multiple of $1/m$.

We prove that, for any constant $c<1$, testing whether a distribution over $[\Theta(m)]$ is $m$-grained requires $\Omega(m^c)$ samples.

Oded Goldreich

We briefly discuss a few open problems in the study of various models of testing graph properties, focusing on the query complexity of the various tasks. In the dense graph model, we discuss several open problems, including:

* Determining the complexity of testing triangle-freeness.

* Characterizing the class of properties ...
more >>>

Oded Goldreich

We study two notions that refers to asymmetric graphs, which we view as graphs having a unique ordering that can be reconstructed by looking at an unlabeled version of the graph.

A {\em local self-ordering} procedure for a graph $G$ is given oracle access to an arbitrary isomorphic copy of ... more >>>

Oded Goldreich, Avi Wigderson

We consider the problem of efficiently constructing an as large as possible family of permutations such that each pair of permutations are far part (i.e., disagree on a constant fraction of their inputs).

Specifically, for every $n\in\N$, we present a collection of $N=N(n)=(n!)^{\Omega(1)}$ pairwise far apart permutations $\{\pi_i:[n]\to[n]\}_{i\in[N]}$ and ...
more >>>

Oded Goldreich, Avi Wigderson

We study the relation between the query complexity of adaptive and non-adaptive testers in the dense graph model.

It has been known for a couple of decades that the query complexity of non-adaptive testers is at most quadratic in the query complexity of adaptive testers.

We show that ...
more >>>

Oded Goldreich, Avi Wigderson

A graph $G$ is called {\em self-ordered}\/ (a.k.a asymmetric) if the identity permutation is its only automorphism.

Equivalently, there is a unique isomorphism from $G$ to any graph that is isomorphic to $G$.

We say that $G=(V,E)$ is {\em robustly self-ordered}\/ if the size of the symmetric difference ...
more >>>

Oded Goldreich

We consider the problem of testing asymmetry in the bounded-degree graph model, where a graph is called asymmetric if the identity permutation is its only automorphism. Seeking to determine the query complexity of this testing problem, we provide partial results. Considering the special case of $n$-vertex graphs with connected components ... more >>>

Oded Goldreich

We show that testing Hamiltonicity in the bounded-degree graph model requires a linear number of queries. This refers to both the path and the cycle versions of the problem, and similar results hold also for the directed analogues.

In addition, we present an alternative proof for the known fact that ...
more >>>

Oded Goldreich

For a constant integer $t$, we consider the problem of counting the number of $t$-cliques $\bmod 2$ in a given graph.

We show that this problem is not easier than determining whether a given graph contains a $t$-clique, and present a simple worst-case to average-case reduction for it. The ...
more >>>

Oded Goldreich, Dana Ron

We consider the query complexity of three versions of the problem of testing monomials and affine (and linear) subspaces with one-sided error, and obtain the following results:

\begin{itemize}

\item The general problem, in which the arity of the monomial (resp., co-dimension of the subspace) is not specified, has ...
more >>>

Marshall Ball, Oded Goldreich, Tal Malkin

Starting with the two standard model of randomized communication complexity, we study the communication complexity of functions when the protocol has access to a defective source of randomness.

Specifically, we consider both the public-randomness and private-randomness cases, while replacing the commonly postulated perfect randomness with distributions over $\ell$ bit ...
more >>>

Marshall Ball, Oded Goldreich, Tal Malkin

We initiate a comprehensive study of the question of randomness extractions from two somewhat dependent sources of defective randomness.

Specifically, we present three natural models, which are based on different natural perspectives on the notion of bounded dependency between a pair of distributions.

Going from the more restricted model ...
more >>>

Oded Goldreich

We consider arithmetic circuits with arbitrary large (multi-linear) gates for computing multi-linear functions. An adequate complexity measure for such circuits is the maximum between the arity of the gates and their number.

This model and the corresponding complexity measure were introduced by Goldreich and Wigderson (ECCC, TR13-043, 2013), ...
more >>>

Oded Goldreich

We consider two versions of the problem of testing graph isomorphism in the bounded-degree graph model: A version in which one graph is fixed, and a version in which the input consists of two graphs.

We essentially determine the query complexity of these testing problems in the special case of ...
more >>>

Oded Goldreich

Loosely speaking, the effective support size of a distribution is the size of the support of a distribution that is close to it (in totally variation distance).

We study the complexity of estimating the effective support size of an unknown distribution when given samples of the distributions as well ...
more >>>

Itai Benjamini, Oded Goldreich

We introduce the notion of pseudo-mixing time of a graph define as the number of steps in a random walk that suffices for generating a vertex that looks random to any polynomial-time observer, where, in addition to the tested vertex, the observer is also provided with oracle access to the ... more >>>

Oded Goldreich

In this work, dedicated to Shafi Goldwasser, we consider a relaxation of the notion of pseudodeterministic algorithms, which was put forward by Gat and Goldwasser ({\em ECCC}, TR11--136, 2011).

Pseudodeterministic algorithms are randomized algorithms that solve search problems by almost always providing the same canonical solution (per each input). ... more >>>

Oded Goldreich

Prior studies of testing graph properties presume that the tester can obtain uniformly distributed vertices in the tested graph (in addition to obtaining answers to the some type of graph-queries).

Here we envision settings in which it is only feasible to obtain random vertices drawn according to an arbitrary distribution ...
more >>>

Oded Goldreich

The standard models of testing graph properties postulate that the vertex-set consists of $\{1,2,...,n\}$, where $n$ is a natural number that is given explicitly to the tester.

Here we suggest more flexible models by postulating that the tester is given access to samples the arbitrary vertex-set; that is, the vertex-set ...
more >>>

Oded Goldreich

Focusing on property testing tasks that have query complexity that is independent of the size of the tested object (i.e., depends on the proximity parameter only), we prove the existence of a rich hierarchy of the corresponding complexity classes.

That is, for essentially any function $q:(0,1]\to\N$, we prove the existence ...
more >>>

Oded Goldreich, Guy Rothblum

We present constant-round interactive proof systems for sufficiently uniform versions of AC0[2] and NC1.

Both proof systems are doubly-efficient, and offer a better trade-off between the round complexity and the total communication than

the work of Reingold, Rothblum, and Rothblum (STOC, 2016).

Our proof system for AC0[2] supports a more ...
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 >>>

Oded Goldreich, Guy Rothblum

We present two main results regarding the complexity of counting the number of $t$-cliques in a graph.

\begin{enumerate}

\item{\em A worst-case to average-case reduction}:

We reduce counting $t$-cliques in any $n$-vertex graph to counting $t$-cliques in typical $n$-vertex graphs that are drawn from a simple distribution of min-entropy ${\widetilde\Omega}(n^2)$. For ...
more >>>

Oded Goldreich, Dana Ron

We initiate a study of testing properties of graphs that are presented as subgraphs of a fixed (or an explicitly given) graph.

The tester is given free access to a base graph $G=([\n],E)$, and oracle access to a function $f:E\to\{0,1\}$ that represents a subgraph of $G$.

The tester is ...
more >>>

Oded Goldreich, Avishay Tal

We consider new complexity measures for the model of multilinear circuits with general multilinear gates introduced by Goldreich and Wigderson (ECCC, 2013).

These complexity measures are related to the size of canonical constant-depth Boolean circuits, which extend the definition of canonical depth-three Boolean circuits.

We obtain matching lower and upper ...
more >>>

Oded Goldreich, Guy Rothblum

For every polynomial $q$, we present worst-case to average-case (almost-linear-time) reductions for a class of problems in $\cal P$ that are widely conjectured not to be solvable in time $q$.

These classes contain, for example, the problems of counting the number of $k$-cliques in a graph, for any fixed $k\geq3$.

more >>>

Oded Goldreich

We provide an overview of the doubly-efficient interactive proof systems of Reingold, Rothblum, and Rothblum (STOC, 2016).

Recall that by their result, any set that is decidable in polynomial-time by an algorithm of space complexity $s(n)\leq n^{0.499}$, has a constant-round interactive proof system

in which the prover runs polynomial time ...
more >>>

Oded Goldreich

We present a somewhat simpler variant of the doubly-efficient interactive proof systems of Goldwasser, Kalai, and Rothblum (JACM, 2015).

Recall that these proof systems apply to log-space uniform sets in NC (or, more generally, to inputs that are acceptable by log-space uniform bounded-depth circuits, where the number of rounds in ...
more >>>

Oded Goldreich, Guy Rothblum

A proof system is called doubly-efficient if the prescribed prover strategy can be implemented in polynomial-time and the verifier's strategy can be implemented in almost-linear-time.

We present direct constructions of doubly-efficient interactive proof systems for problems in $\cal P$ that are believed to have relatively high complexity.

Specifically, such ...
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 >>>

Oded Goldreich

Contemplating the recently announced 1-local expanders of Viola and Wigderson (ECCC, TR16-129, 2016), one may observe that weaker constructs are well know. For example, one may easily obtain a 4-regular $N$-vertex graph with spectral gap that is $\Omega(1/\log^2 N)$, and similarly a $O(1)$-regular $N$-vertex graph with spectral gap $1/\tildeO(\log N)$.

more >>>

Oded Goldreich

We consider the task of testing whether a Boolean function $f:\{0,1\}^\ell\to\{0,1\}$

is the indicator function of an $(\ell-k)$-dimensional affine space.

An optimal tester for this property was presented by Parnas, Ron, and Samorodnitsky ({\em SIDMA}, 2002), by mimicking the celebrated linearity tester (of Blum, Luby and Rubinfeld, {\em JCSS}, 1993) ...
more >>>

Oded Goldreich, Maya Leshkowitz

The known emulation of interactive proof systems by public-coins interactive proof systems proceeds by selecting, at each round, a message such that each message is selected with probability that is at most polynomially larger than its probability in the original protocol.

Specifically, the possible messages are essentially clustered according to ...
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

Inspired by Diakonikolas and Kane (2016), we reduce the class of problems consisting of testing whether an unknown distribution over $[n]$ equals a fixed distribution to this very problem when the fixed distribution is uniform over $[n]$. Our reduction preserves the parameters of the problem, which are $n$ and the ... more >>>

Oded Goldreich, Avishay Tal

We prove that random $n$-by-$n$ Toeplitz (alternatively Hankel) matrices over $GF(2)$ have rigidity $\Omega(\frac{n^3}{r^2\log n})$ for rank $r \ge \sqrt{n}$, with high probability. This improves, for $r = o(n/\log n \log\log n)$, over the $\Omega(\frac{n^2}{r} \cdot\log(\frac{n}{r}))$ bound that is known for many explicit matrices.

Our result implies that the explicit ... 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, Emanuele Viola, Avi Wigderson

We consider randomness extraction by AC0 circuits. The main parameter, $n$, is the length of the source, and all other parameters are functions of it. The additional extraction parameters are the min-entropy bound $k=k(n)$, the seed length $r=r(n)$, the output length $m=m(n)$, and the (output) deviation bound $\epsilon=\epsilon(n)$.

For $k ... more >>>

Oded Goldreich, Liav Teichner

We initiate a study of super-perfect zero-knowledge proof systems.

Loosely speaking, these are proof systems for which the interaction can be perfectly simulated in strict probabilistic polynomial-time.

In contrast, the standard definition of perfect zero-knowledge only requires that the interaction can be perfectly simulated

by a strict probabilistic polynomial-time that ...
more >>>

Oded Goldreich, Dana Ron

We initiate a study of learning and testing dynamic environments,

focusing on environment that evolve according to a fixed local rule.

The (proper) learning task consists of obtaining the initial configuration

of the environment, whereas for non-proper learning it suffices to predict

its future values. The testing task consists of ...
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 >>>

Oded Goldreich, Avi Wigderson

{\em Does derandomization of probabilistic algorithms become easier when the number of ``bad'' random inputs is extremely small?}

In relation to the above question, we put forward the following {\em quantified derandomization challenge}:

For a class of circuits $\cal C$ (e.g., P/poly or $AC^0,AC^0[2]$) and a bounding function $B:\N\to\N$ (e.g., ...
more >>>

Oded Goldreich, Dana Ron

The standard definition of property testing endows the tester with the ability to make arbitrary queries to ``elements''

of the tested object.

In contrast, sample-based testers only obtain independently distributed elements (a.k.a. labeled samples) of the tested object.

While sample-based testers were defined by

Goldreich, Goldwasser, and Ron ({\em JACM}\/ ...
more >>>

Oded Goldreich

A couple of years ago, Blais, Brody, and Matulef put forward a methodology for proving lower bounds on the query complexity

of property testing via communication complexity. They provided a restricted formulation of their methodology

(via ``simple combining operators'')

and also hinted towards a more general formulation, which we spell ...
more >>>

Oded Goldreich

We consider three types of multiple input problems in the context of property testing.

Specifically, for a property $\Pi\subseteq\{0,1\}^n$, a proximity parameter $\epsilon$, and an integer $m$, we consider the following problems:

\begin{enumerate}

\item Direct $m$-Sum Problem for $\Pi$ and $\epsilon$:

Given a sequence of $m$ inputs, output a sequence ...
more >>>

Oded Goldreich, Avi Wigderson

We propose that multi-linear functions of relatively low degree

over GF(2) may be good candidates for obtaining exponential

lower bounds on the size of constant-depth Boolean circuits

(computing explicit functions).

Specifically, we propose to move gradually from linear functions

to multilinear ones, and conjecture that, for any $t\geq2$,

more >>>

Oded Goldreich, Shafi Goldwasser, Dana Ron

We study the possibilities and limitations

of pseudodeterministic algorithms,

a notion put forward by Gat and Goldwasser (2011).

These are probabilistic algorithms that solve search problems

such that on each input, with high probability, they output

the same solution, which may be thought of as a canonical solution.

We consider ...
more >>>

Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler

(This is a revised version of work that was posted on arXiv in July 2010.)

We present sublinear-time (randomized) algorithms for finding simple cycles of length at least $k\geq3$ and tree-minors in bounded-degree graphs.

The complexity of these algorithms is related to the distance

of the graph from being ...
more >>>

Oded Goldreich, Igor Shinkar

Loosely speaking, a proximity-oblivious (property) tester is a randomized algorithm that makes a constant number of queries to a tested object and distinguishes objects that have a predetermined property from those that lack it. Specifically, for some threshold probability $c$, objects having the property are accepted with probability at least ... more >>>

Oded Goldreich

This note refers to the effect of the proximity parameter on the operation of (standard) property testers. Its bottom-line is that, except in pathological cases, the effect of the proximity parameter is restricted to determining the query complexity of the tester. The point is that, in non-pathological cases, the mapping ... more >>>

Oded Goldreich, Ron Rothblum

We take a closer look at several enhancements of the notion of trapdoor permutations. Specifically, we consider the notions of enhanced trapdoor permutation (Goldreich 2004) and doubly enhanced trapdoor permutation (Goldreich 2008) as well as intermediate notions (Rothblum 2010). These enhancements arose in the study of Oblivious Transfer and NIZK, ... more >>>

Oded Goldreich, Rani Izsak

We study the computability of one-way functions and pseudorandom generators

by monotone circuits, showing a substantial gap between the two:

On one hand, there exist one-way functions that are computable

by (uniform) polynomial-size monotone functions, provided (of course)

that one-way functions exist at all.

On the other hand, ...
more >>>

Oded Goldreich

We revisit the notion of a {\em targeted canonical derandomizer},

introduced in our recent ECCC Report (TR10-135) as a uniform notion of

a pseudorandom generator that suffices for yielding BPP=P.

The original notion was derived (as a variant of the standard notion

of a canonical derandomizer) by providing both ...
more >>>

Oded Goldreich, Or Meir

We initiate a study of input-oblivious proof systems, and present a few preliminary results regarding such systems.

Our results offer a perspective on the intersection of the non-uniform complexity class P/poly with uniform complexity classes such as NP and IP.

In particular, we provide a uniform complexity formulation of the ...
more >>>

Oded Goldreich, Salil Vadhan

We consider two basic computational problems

regarding discrete probability distributions:

(1) approximating the statistical difference (aka variation distance)

between two given distributions,

and (2) approximating the entropy of a given distribution.

Both problems are considered in two different settings.

In the first setting the approximation algorithm

more >>>

Oded Goldreich

We show that proving results such as BPP=P essentially

necessitate the construction of suitable pseudorandom generators

(i.e., generators that suffice for such derandomization results).

In particular, the main incarnation of this equivalence

refers to the standard notion of uniform derandomization

and to the corresponding pseudorandom generators

(i.e., the standard uniform ...
more >>>

Oded Goldreich

The aim of this article is to introduce the reader to the study

of testing graph properties, while focusing on the main models

and issues involved. No attempt is made to provide a

comprehensive survey of this study, and specific results

are often mentioned merely as illustrations of general ...
more >>>

Oded Goldreich

We take another step in the study of the testability

of small-width OBDDs, initiated by Ron and Tsur (Random'09).

That is, we consider algorithms that,

given oracle access to a function $f:\{0,1\}^n\to\{0,1\}$,

need to determine whether $f$ can be implemented

by some restricted class of OBDDs or is far from

more >>>

Oded Goldreich, Tali Kaufman

We present a general notion of properties that

are characterized by local conditions that are invariant

under a sufficiently rich class of symmetries.

Our framework generalizes two popular models of

testing graph properties as well as the algebraic

invariances studied by Kaufman and Sudan (STOC'08).

We show that, in the ... more >>>

Oded Goldreich, Brendan Juba, Madhu Sudan

We put forward a general theory of goal-oriented communication, where communication is not an end in itself, but rather a means to achieving some goals of the communicating parties. The goals can vary from setting to setting, and we provide a general framework for describing any such goal. In this ... more >>>

Zvika Brakerski, Oded Goldreich

We study methods of converting algorithms that distinguish pairs

of distributions with a gap that has an absolute value that is noticeable

into corresponding algorithms in which the gap is always positive.

Our focus is on designing algorithms that, in addition to the tested string,

obtain a ...
more >>>

Oded Goldreich

We present a candidate counterexample to the

easy cylinders conjecture, which was recently suggested

by Manindra Agrawal and Osamu Watanabe (ECCC, TR09-019).

Loosely speaking, the conjecture asserts that any 1-1 function

in $P/poly$ can be decomposed into ``cylinders'' of sub-exponential

size that can each be inverted by some polynomial-size circuit.

more >>>

Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg

Referring to the query complexity of property testing,

we prove the existence of a rich hierarchy of corresponding

complexity classes. That is, for any relevant function $q$,

we prove the existence of properties that have testing

complexity Theta(q).

Such results are proven in three standard

domains often considered in property ...
more >>>

Oded Goldreich, Dana Ron

We initiate a systematic study of a special type of property testers.

These testers consist of repeating a basic test

for a number of times that depends on the proximity parameters,

whereas the basic test is oblivious of the proximity parameter.

We refer to such basic ...
more >>>

Oded Goldreich, Dana Ron

In this paper we consider two refined questions regarding

the query complexity of testing graph properties

in the adjacency matrix model.

The first question refers to the relation between adaptive

and non-adaptive testers, whereas the second question refers to

testability within complexity that

is inversely proportional to ...
more >>>

Oded Goldreich, Or Meir

Given two codes R,C, their tensor product $R \otimes C$ consists of all matrices whose rows are codewords of R and whose columns are codewords of C. The product $R \otimes C$ is said to be robust if for every matrix M that is far from $R \otimes C$ it ... more >>>

Oded Goldreich

Motivated by a recent study of Zimand (22nd CCC, 2007),

we consider the average-case complexity of property testing

(focusing, for clarity, on testing properties of Boolean strings).

We make two observations:

1) In the context of average-case analysis with respect to

the uniform distribution (on all strings of ...
more >>>

Oded Goldreich, Or Sheffet

We initiate a general study of the randomness complexity of

property testing, aimed at reducing the randomness complexity of

testers without (significantly) increasing their query complexity.

One concrete motovation for this study is provided by the

observation that the product of the randomness and query complexity

of a tester determine ...
more >>>

Mihir Bellare, Oded Goldreich

This note points out a gap between two natural formulations of

the concept of a proof of knowledge, and shows that in all

natural cases (e.g., NP-statements) this gap can be closed.

The aforementioned formulations differ by whether they refer to

(all possible) probabilistic or deterministic prover strategies.

Unlike ...
more >>>

Oded Goldreich

This paper concerns the possibility of developing a coherent

theory of security when feasibility is associated

with expected probabilistic polynomial-time (expected PPT).

The source of difficulty is that

the known definitions of expected PPT strategies

(i.e., expected PPT interactive machines)

do not support natural results of the ...
more >>>

Oded Goldreich

We highlight a common theme in four relatively recent works

that establish remarkable results by an iterative approach.

Starting from a trivial construct,

each of these works applies an ingeniously designed

sequence of iterations that yields the desired result,

which is highly non-trivial. Furthermore, in each iteration,

more >>>

Oded Goldreich, Dana Ron

Inspired by Feige ({\em 36th STOC}, 2004),

we initiate a study of sublinear randomized algorithms

for approximating average parameters of a graph.

Specifically, we consider the average degree of a graph

and the average distance between pairs of vertices in a graph.

Since our focus is on sublinear algorithms, ...
more >>>

Oded Goldreich

The notion of promise problems was introduced and initially studied

by Even, Selman and Yacobi

(Information and Control, Vol.~61, pages 159-173, 1984).

In this article we survey some of the applications that this

notion has found in the twenty years that elapsed.

These include the notion ...
more >>>

Oded Goldreich

We survey known results regarding locally testable codes

and locally testable proofs (known as PCPs),

with emphasis on the length of these constructs.

Locally testability refers to approximately testing

large objects based on a very small number of probes,

each retrieving a single bit in the ...
more >>>

Oded Goldreich, Madhu Sudan, Luca Trevisan

Building on Barak's work (Random'02),

Fortnow and Santhanam (FOCS'04) proved a time hierarchy

for probabilistic machines with one bit of advice.

Their argument is based on an implicit translation technique,

which allow to translate separation results for short (say logarithmic)

advice (as shown by Barak) into separations for ...
more >>>

Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan

We continue the study of the trade-off between the length of PCPs

and their query complexity, establishing the following main results

(which refer to proofs of satisfiability of circuits of size $n$):

We present PCPs of length $\exp(\tildeO(\log\log n)^2)\cdot n$

that can be verified by making $o(\log\log n)$ Boolean queries.

more >>>

Oded Goldreich, Dana Ron

Following Feige, we consider the problem of

estimating the average degree of a graph.

Using ``neighbor queries'' as well as ``degree queries'',

we show that the average degree can be approximated

arbitrarily well in sublinear time, unless the graph is extremely sparse

(e.g., unless the graph has a sublinear ...
more >>>

Oded Goldreich, Asaf Nussboim

We initiate a general study of pseudo-random implementations

of huge random objects, and apply it to a few areas

in which random objects occur naturally.

For example, a random object being considered may be

a random connected graph, a random bounded-degree graph,

or a random error-correcting code with good ...
more >>>

Eli Ben-Sasson, Oded Goldreich, Madhu Sudan

We present upper bounds on the size of codes that are locally

testable by querying only two input symbols. For linear codes, we

show that any $2$-locally testable code with minimal distance

$\delta n$ over a finite field $F$ cannot have more than

$|F|^{3/\delta}$ codewords. This result holds even ...
more >>>

Oded Goldreich

Zero-knowledge proofs are proofs that are both convincing and yet

yield nothing beyond the validity of the assertion being proven.

Since their introduction about twenty years ago,

zero-knowledge proofs have attracted a lot of attention

and have, in turn, contributed to the development of other

areas of cryptography and complexity ...
more >>>

Oded Goldreich, Madhu Sudan

Locally testable codes are error-correcting codes that admit

very efficient codeword tests. Specifically, using a constant

number of (random) queries, non-codewords are rejected with

probability proportional to their distance from the code.

Locally testable codes are believed to be the combinatorial

core of PCPs. However, the relation is ...
more >>>

Oded Goldreich, Vered Rosen

Assuming the inractability of factoring, we show that

the output of the exponentiation modulo a composite function

$f_{N,g}(x)=g^x\bmod N$ (where $N=P\cdot Q$) is pseudorandom,

even when its input is restricted to be half the size.

This result is equivalent to the simultaneous hardness of the upper

half of the bits ...
more >>>

Noga Alon, Oded Goldreich, Yishay Mansour

We say that a distribution over $\{0,1\}^n$

is almost $k$-wise independent

if its restriction to every $k$ coordinates results in a

distribution that is close to the uniform distribution.

A natural question regarding almost $k$-wise independent

distributions is how close they are to some $k$-wise

independent distribution. We show ...
more >>>

Oded Goldreich

We consider the function ensembles emerging from the

construction of Goldreich, Goldwasser and Micali (GGM),

when applied to an arbitrary pseudoramdon generator.

We show that, in general, such functions

fail to yield correlation intractable ensembles.

Specifically, it may happen that, given a description of such a ...
more >>>

Oded Goldreich, Avi Wigderson

For every $\epsilon>0$,

we present a {\em deterministic}\/ log-space algorithm

that correctly decides undirected graph connectivity

on all but at most $2^{n^\epsilon}$ of the $n$-vertex graphs.

The same holds for every problem in Symmetric Log-space (i.e., $\SL$).

Making no assumptions (and in particular not assuming the ... more >>>

Oded Goldreich

Using known results regarding PCP,

we present simple proofs of the inapproximability

of vertex cover for hypergraphs.

Specifically, we show that

(1) Approximating the size of the minimum vertex cover

in $O(1)$-regular hypergraphs to within a factor of~1.99999 is NP-hard.

(2) Approximating the size ...
more >>>

Boaz Barak, Oded Goldreich

We put forward a new type of

computationally-sound proof systems, called universal-arguments,

which are related but different from both CS-proofs (as defined

by Micali) and arguments (as defined by Brassard, Chaum and

Crepeau). In particular, we adopt the instance-based

prover-efficiency paradigm of CS-proofs, but follow the

computational-soundness condition of ...
more >>>

Oded Goldreich

Following Dwork, Naor, and Sahai (30th STOC, 1998),

we consider concurrent execution of protocols in a

semi-synchronized network. Specifically, we assume that each party

holds a local clock such that a constant bound on the relative rates

of these clocks is a-priori known, and consider protocols that

employ ...
more >>>

Oded Goldreich, Howard Karloff, Leonard Schulman, Luca Trevisan

We prove that if a linear error correcting code

$\C:\{0,1\}^n\to\{0,1\}^m$ is such that a bit of the message can

be probabilistically reconstructed by looking at two entries of a

corrupted codeword, then $m = 2^{\Omega(n)}$. We also present

several extensions of this result.

We show a reduction from the ... more >>>

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, Ke Yang

Informally, an <i>obfuscator</i> <b>O</b> is an (efficient, probabilistic)

"compiler" that takes as input a program (or circuit) <b>P</b> and

produces a new program <b>O(P)</b> that has the same functionality as <b>P</b>

yet is "unintelligible" in some sense. Obfuscators, if they exist,

would have a wide variety of cryptographic ...
more >>>

Oded Goldreich, Salil Vadhan, Avi Wigderson

We continue the investigation of interactive proofs with bounded

communication, as initiated by Goldreich and Hastad (IPL 1998).

Let $L$ be a language that has an interactive proof in which the prover

sends few (say $b$) bits to the verifier.

We prove that the complement $\bar L$ has ...
more >>>

Oded Goldreich, Luca Trevisan

Property testing is a relaxation of decision problems

in which it is required to distinguish {\sc yes}-instances

(i.e., objects having a predetermined property) from instances

that are far from any {\sc yes}-instance.

We presents three theorems regarding testing graph

properties in the adjacency matrix representation. ...
more >>>

Oded Goldreich

We suggest a candidate one-way function using combinatorial

constructs such as expander graphs. These graphs are used to

determine a sequence of small overlapping subsets of input bits,

to which a hard-wired random predicate is applied.

Thus, the function is extremely easy to evaluate:

all that is needed ...
more >>>

Oded Goldreich, Avi Wigderson

In the theory of pseudorandomness, potential (uniform) observers

are modeled as probabilistic polynomial-time machines.

In fact many of the central results in

that theory are proven via probabilistic polynomial-time reductions.

In this paper we show that analogous deterministic reductions

are unlikely to hold. We conclude that randomness ...
more >>>

Oded Goldreich, Dana Ron

We consider testing graph expansion in the bounded-degree graph model.

Specifically, we refer to algorithms for testing whether the graph

has a second eigenvalue bounded above by a given threshold

or is far from any graph with such (or related) property.

We present a natural algorithm aimed ... more >>>

Oded Goldreich, Salil Vadhan, Avi Wigderson

A hitting-set generator is a deterministic

algorithm which generates a set of strings that intersects

every dense set recognizable by a small circuit.

A polynomial time hitting-set generator readily implies $RP=P$.

Andreev \etal\/ (ICALP'96, and JACM 1998)

showed that if polynomial-time hitting-set

generator in fact implies ...
more >>>

Ran Canetti, Oded Goldreich, Silvio Micali.

We introduce the notion of Resettable Zero-Knowledge (rZK),

a new security measure for cryptographic protocols

which strengthens the classical notion of zero-knowledge.

In essence, an rZK protocol is one that remains zero knowledge

even if an adeversary can interact with the prover many times, each

time ...
more >>>

Oded Goldreich, Silvio Micali.

We introduce the notion of Interleaved Zero-Knowledge (iZK),

a new security measure for cryptographic protocols which strengthens

the classical notion of zero-knowledge, in a way suitable for multiple

concurrent executions in an asynchronous environment like the internet.

We prove that iZK protocols are robust: they are ``parallelizable'',

and ...
more >>>

Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky

We present improved algorithms for testing monotonicity of functions.

Namely, given the ability to query an unknown function $f$, where

$\Sigma$ and $\Xi$ are finite ordered sets, the test always accepts a

monotone $f$, and rejects $f$ with high probability if it is $\e$-far

from being monotone (i.e., every ...
more >>>

Oded Goldreich, Amit Sahai, Salil Vadhan

We extend the study of non-interactive statistical zero-knowledge

proofs. Our main focus is to compare the class NISZK of problems

possessing such non-interactive proofs to the class SZK of problems

possessing interactive statistical zero-knowledge proofs. Along these

lines, we first show that if statistical zero knowledge is non-trivial

then so ...
more >>>

Oded Goldreich, Daniele Micciancio, Shmuel Safra and Jean-Pierre Seifert.

We show that given oracle access to a subroutine which

returns approximate closest vectors in a lattice, one may find in

polynomial-time approximate shortest vectors in a lattice.

The level of approximation is maintained; that is, for any function

$f$, the following holds:

Suppose that the subroutine, on input a ...
more >>>

Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson

This paper initiates the study of deterministic amplification of space

bounded probabilistic algorithms. The straightforward implementations of

known amplification methods cannot be used for such algorithms, since they

consume too much space. We present a new implementation of the

Ajtai-Koml\'{o}s-Szemer\'{e}di method, that enables to amplify an $S$ ...
more >>>

Oded Goldreich, Salil Vadhan

We consider the following (promise) problem, denoted ED (for Entropy

Difference): The input is a pairs of circuits, and YES instances (resp.,

NO instances) are such pairs in which the first (resp., second) circuit

generates a distribution with noticeably higher entropy.

On one hand we show that any language ... more >>>

Oded Goldreich, Dana Ron, Madhu Sudan

The Chinese Remainder Theorem states that a positive

integer m is uniquely specified by its remainder modulo

k relatively prime integers p_1,...,p_k, provided

m < \prod_{i=1}^k p_i. Thus the residues of m modulo

relatively prime integers p_1 < p_2 < ... < p_n

form a redundant representation of m if ...
more >>>

Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan

This is a revised version of work which has appeared

in preliminary form in the 36th FOCS, 1995.

Given a function $f$ mapping $n$-variate inputs from a finite field

$F$ into $F$,

we consider the task of reconstructing a list of all $n$-variate

degree $d$ polynomials which agree with $f$

more >>>

Mihir Bellare, Oded Goldreich, Erez Petrank

A Uniform Generation procedure for $NP$ is an

algorithm which given any input in a fixed NP-language, outputs a uniformly

distributed NP-witness for membership of the input in the language.

We present a Uniform Generation procedure for $NP$ that runs in probabilistic

polynomial-time with an NP-oracle. This improves upon ...
more >>>

Oded Goldreich, Madhu Sudan

We consider the existence of pairs of probability ensembles which

may be efficiently distinguished given $k$ samples

but cannot be efficiently distinguished given $k'<k$ samples.

It is well known that in any such pair of ensembles it cannot be that

both are efficiently computable

(and that such phenomena ...
more >>>

Alfredo De Santis, Giovanni Di Crescenzo, Oded Goldreich, Giuseppe Persiano

The input to the {\em Graph Clustering Problem}\/

consists of a sequence of integers $m_1,...,m_t$

and a sequence of $\sum_{i=1}^{t}m_i$ graphs.

The question is whether the equivalence classes,

under the graph isomorphism relation,

of the input graphs have sizes which match the input sequence of integers.

In this note ...
more >>>

Oded Goldreich

In 1984, Leonid Levin has initiated a theory of average-case complexity.

We provide an exposition of the basic definitions suggested by Levin,

and discuss some of the considerations underlying these definitions.

Oded Goldreich

We consider the question of determining whether

a given object has a predetermined property or is ``far'' from any

object having the property.

Specifically, objects are modeled by functions,

and distance between functions is measured as the fraction

of the domain on which the functions differ.

We ...
more >>>

Oded Goldreich, David Zuckerman

We provide another proof of the Sipser--Lautemann Theorem

by which $BPP\subseteq MA$ ($\subseteq PH$).

The current proof is based on strong

results regarding the amplification of $BPP$, due to Zuckerman.

Given these results, the current proof is even simpler than previous ones.

Furthermore, extending the proof leads ...
more >>>

Oded Goldreich

We show simple constant-round interactive proof systems for

problems capturing the approximability, to within a factor of $\sqrt{n}$,

of optimization problems in integer lattices; specifically,

the closest vector problem (CVP), and the shortest vector problem (SVP).

These interactive proofs are for the ``coNP direction'';

that is, ...
more >>>

Scott E. Decatur, Oded Goldreich, Dana Ron

In a variety of PAC learning models, a tradeoff between time and

information seems to exist: with unlimited time, a small amount of

information suffices, but with time restrictions, more information

sometimes seems to be required.

In addition, it has long been known that there are

concept classes ...
more >>>

Oded Goldreich

We consider the problem of estimating the average of a huge set of values.

That is,

given oracle access to an arbitrary function $f:\{0,1\}^n\mapsto[0,1]$,

we need to estimate $2^{-n} \sum_{x\in\{0,1\}^n} f(x)$

upto an additive error of $\epsilon$.

We are allowed to employ a randomized algorithm which may ...
more >>>

Oded Goldreich, Shai Halevi

Following Ajtai's lead, Ajtai and Dwork have recently introduced a

public-key encryption scheme which is secure under the assumption

that a certain computational problem on lattices is hard on the

worst-case. Their encryption method may cause decryption errors,

though with small probability (i.e., inversely proportional to the

more >>>

Oded Goldreich, Bernd Meyer

We present a simple proof to the existence of a probability ensemble

with tiny support which cannot be distinguished from the uniform ensemble

by any recursive computation.

Since the support is tiny (i.e, sub-polynomial),

this ensemble can be distinguish from the uniform ensemble

by a (non-uniform) family ...
more >>>

Oded Goldreich, Dana Ron

In this paper, we consider the question of determining whether

a function $f$ has property $P$ or is $\e$-far from any

function with property $P$.

The property testing algorithm is given a sample of the value

of $f$ on instances drawn according to some distribution.

In some cases,

more >>>

Oded Goldreich, Shai Halevi

We present a new proposal for a trapdoor one-way function,

from which we derive public-key encryption and digital

signatures. The security of the new construction is based

on the conjectured computational difficulty of lattice-reduction

problems, providing a possible alternative to existing

more >>>

Oded Goldreich

The Graph Clustering Problem is parameterized by a sequence

of positive integers, $m_1,...,m_t$.

The input is a sequence of $\sum_{i=1}^{t}m_i$ graphs,

and the question is whether the equivalence classes

under the graph isomorphism relation have sizes which match

the sequence of parameters.

In this note

we show ...
more >>>

Oded Goldreich, Muli Safra

The current proof of the PCP Theorem (i.e., NP=PCP(log,O(1)))

is very complicated.

One source of difficulty is the technically involved

analysis of low-degree tests.

Here, we refer to the difficulty of obtaining strong results

regarding low-degree tests; namely, results of the type obtained and

used by ...
more >>>

Oded Goldreich, Shai Halevi

Recently Ajtai described a construction of one-way functions whose

security is equivalent to the difficulty of some well known approximation

problems in lattices. We show that essentially the same

construction can also be used to obtain collision-free hashing.

Oded Goldreich, Avi Wigderson

We consider the size of circuits which perfectly hash

an arbitrary subset $S\!\subset\!\bitset^n$ of cardinality $2^k$

into $\bitset^m$.

We observe that, in general, the size of such circuits is

exponential in $2k-m$,

and provide a matching upper bound.

Oded Goldreich, Johan HÃ¥stad

We investigate the computational complexity of languages

which have interactive proof systems of bounded message complexity.

In particular, we show that

(1) If $L$ has an interactive proof in which the total

communication is bounded by $c(n)$ bits

then $L$ can be recognized a probabilitic machine

in time ...
more >>>

Oded Goldreich

We provide an exposition of three Lemmas which relate

general properties of distributions

with the exclusive-or of certain bit locations.

The first XOR-Lemma, commonly attributed to U.V. Vazirani,

relates the statistical distance of a distribution from uniform

to the maximum bias of the xor of certain bit positions.

more >>>

Oded Goldreich, Noam Nisan, Avi Wigderson

Oded Goldreich, Leonid Levin, Noam Nisan

We show how to construct length-preserving 1-1 one-way

functions based on popular intractability assumptions (e.g., RSA, DLP).

Such 1-1 functions should not

be confused with (infinite) families of (finite) one-way permutations.

What we want and obtain is a single (infinite) 1-1 one-way function.

Mihir Bellare, Oded Goldreich, Madhu Sudan

This paper continues the investigation of the connection between proof

systems and approximation. The emphasis is on proving ``tight''

non-approximability results via consideration of measures like the

``free bit complexity'' and the ``amortized free bit complexity'' of

proof systems.

The first part of the paper presents a collection of new ... more >>>

Oded Goldreich

Various types of probabilistic proof systems have played

a central role in the development of computer science in the last decade.

In this exposition, we concentrate on three such proof systems ---

interactive proofs, zero-knowledge proofs,

and probabilistic checkable proofs --- stressing the essential

role of randomness in each ...
more >>>

Oded Goldreich, Rafail Ostrovsky, Erez Petrank

We study the computational complexity of languages which have

interactive proofs of logarithmic knowledge complexity. We show that

all such languages can be recognized in ${\cal BPP}^{\cal NP}$. Prior

to this work, for languages with greater-than-zero knowledge

complexity (and specifically, even for knowledge complexity 1) only

trivial computational complexity bounds ...
more >>>

Oded Goldreich, Avi Wigderson

We present three explicit constructions of hash functions,

which exhibit a trade-off between the size of the family

(and hence the number of random bits needed to generate a member of the family),

and the quality (or error parameter) of the pseudo-random property it

achieves. Unlike previous constructions, ...
more >>>