Oded Goldreich

Electron. Colloquium Comput. Complex., 2024

Solving Tree Evaluation in o(log n · log log n) space.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2024

On the Cook-Mertz Tree Evaluation procedure.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2024

On the relaxed LDC of BGHSV: A survey that corrects the record.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2024

On the query complexity of testing local graph properties in the bounded-degree graph model.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2024

On locally-characterized expander graphs (a survey).

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2024

2023

A Lower Bound on the Complexity of Testing Grained Distributions.

[BibT_eX]

[DOI]

Comput. Complex., December, 2023

On Testing Group Properties.

[BibT_eX]

[DOI]

Laliv Tauber

Electron. Colloquium Comput. Complex., 2023

On Testing Isomorphism to a Fixed Graph in the Bounded-Degree Graph Model.

[BibT_eX]

[DOI]

Laliv Tauber

Electron. Colloquium Comput. Complex., 2023

On coarse and fine approximate counting of t-cliques.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

On the complexity of enumerating ordered sets.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

On the Lower Bound on the Length of Relaxed Locally Decodable Codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

On teaching the approximation method for circuit lower bounds.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

2022

On properties that are non-trivial to test.

[BibT_eX]

[DOI]

Nader H. Bshouty

Electron. Colloquium Comput. Complex., 2022

Testing in the bounded-degree graph model with degree bound two.

[BibT_eX]

[DOI]

Laliv Tauber

Electron. Colloquium Comput. Complex., 2022

On Interactive Proofs of Proximity with Proof-Oblivious Queries.

[BibT_eX]

[DOI]

Tal Skverer

Electron. Colloquium Comput. Complex., 2022

Improved bounds on the AN-complexity of O(1)-linear functions.

[BibT_eX]

[DOI]

Comput. Complex., 2022

2021

Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2021

Testing Distributions of Huge Objects.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

The KW Games as a Teaser.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Open Problems in Property Testing of Graphs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Robust Self-Ordering versus Local Self-Ordering.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

2020

A Probabilistic Error-Correcting Scheme that Provides Partial Secrecy.

[BibT_eX]

[DOI]

Scott E. Decatur

Proceedings of the Computational Complexity and Property Testing, 2020

Pseudo-mixing Time of Random Walks.

[BibT_eX]

[DOI]

Itai Benjamini

Proceedings of the Computational Complexity and Property Testing, 2020

On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions.

[BibT_eX]

[DOI]

Proceedings of the Computational Complexity and Property Testing, 2020

On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions.

[BibT_eX]

[DOI]

Avishay Tal

Proceedings of the Computational Complexity and Property Testing, 2020

Super-Perfect Zero-Knowledge Proofs.

[BibT_eX]

[DOI]

Liav Teichner

Proceedings of the Computational Complexity and Property Testing, 2020

Constant-Round Interactive Proof Systems for AC0[2] and NC1.

[BibT_eX]

[DOI]

Proceedings of the Computational Complexity and Property Testing, 2020

Worst-Case to Average-Case Reductions for Subclasses of P.

[BibT_eX]

[DOI]

Proceedings of the Computational Complexity and Property Testing, 2020

On the Relation Between the Relative Earth Mover Distance and the Variation Distance (an Exposition).

[BibT_eX]

[DOI]

Proceedings of the Computational Complexity and Property Testing, 2020

Bridging a Small Gap in the Gap Amplification of Assignment Testers.

[BibT_eX]

[DOI]

Or Meir

Proceedings of the Computational Complexity and Property Testing, 2020

On Emulating Interactive Proofs with Public Coins.

[BibT_eX]

[DOI]

Maya Leshkowitz

Proceedings of the Computational Complexity and Property Testing, 2020

On Constructing Expanders for Any Number of Vertices.

[BibT_eX]

[DOI]

Proceedings of the Computational Complexity and Property Testing, 2020

Flexible Models for Testing Graph Properties.

[BibT_eX]

[DOI]

Proceedings of the Computational Complexity and Property Testing, 2020

On the Optimal Analysis of the Collision Probability Tester (an Exposition).

[BibT_eX]

[DOI]

Proceedings of the Computational Complexity and Property Testing, 2020

Deconstructing 1-Local Expanders.

[BibT_eX]

[DOI]

Proceedings of the Computational Complexity and Property Testing, 2020

Reducing Testing Affine Spaces to Testing Linearity of Functions.

[BibT_eX]

[DOI]

Proceedings of the Computational Complexity and Property Testing, 2020

The Uniform Distribution Is Complete with Respect to Testing Identity to a Fixed Distribution.

[BibT_eX]

[DOI]

Proceedings of the Computational Complexity and Property Testing, 2020

On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing.

[BibT_eX]

[DOI]

Proceedings of the Computational Complexity and Property Testing, 2020

On the Effect of the Proximity Parameter on Property Testers.

[BibT_eX]

[DOI]

Proceedings of the Computational Complexity and Property Testing, 2020

Two Comments on Targeted Canonical Derandomizers.

[BibT_eX]

[DOI]

Proceedings of the Computational Complexity and Property Testing, 2020

On (Valiant's) Polynomial-Size Monotone Formula for Majority.

[BibT_eX]

[DOI]

Proceedings of the Computational Complexity and Property Testing, 2020

Constructing Large Families of Pairwise Far Permutations: Good Permutation Codes Based on the Shuffle-Exchange Network.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

One-Sided Error Testing of Monomials and Affine Subspaces.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

On Testing Asymmetry in the Bounded Degree Graph Model.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

On Testing Hamiltonicity in the Bounded Degree Graph Model.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

On Counting $t$-Cliques Mod 2.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

Communication Complexity with Defective Randomness.

[BibT_eX]

[DOI]

Marshall Ball

Tal Malkin

Electron. Colloquium Comput. Complex., 2020

2019

Improved bounds on the AN-complexity of multilinear functions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

Testing Isomorphism in the Bounded-Degree Graph Model.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

On the Complexity of Estimating the Effective Support Size.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

Multi-pseudodeterministic algorithms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

Pseudo-Mixing Time of Random Walks.

[BibT_eX]

[DOI]

Itai Benjamini

Electron. Colloquium Comput. Complex., 2019

Randomness Extraction from Somewhat Dependent Sources.

[BibT_eX]

[DOI]

Marshall Ball

Tal Malkin

Electron. Colloquium Comput. Complex., 2019

Testing Bipartitness in an Augmented VDF Bounded-Degree Graph Model.

[BibT_eX]

[DOI]

CoRR, 2019

Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity.

[BibT_eX]

[DOI]

Comput. Complex., 2019

How to play any mental game, or a completeness theorem for protocols with honest majority.

[BibT_eX]

[DOI]

Proceedings of the Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, 2019

Proofs that yield nothing but their validity and a methodology of cryptographic protocol design.

[BibT_eX]

[DOI]

Proceedings of the Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, 2019

How to construct random functions.

[BibT_eX]

[DOI]

Proceedings of the Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, 2019

On some noncryptographic works of Goldwasser and Micali.

[BibT_eX]

[DOI]

Proceedings of the Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, 2019

On the impact of cryptography on complexity theory.

[BibT_eX]

[DOI]

Proceedings of the Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, 2019

On the foundations of cryptography.

[BibT_eX]

[DOI]

Proceedings of the Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, 2019

Preface.

[BibT_eX]

[DOI]

Proceedings of the Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, 2019

2018

On Doubly-Efficient Interactive Proof Systems.

[BibT_eX]

[DOI]

Found. Trends Theor. Comput. Sci., 2018

Constant-round interactive proof systems for AC0[2] and NC1.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Counting t-cliques: Worst-case to average-case reductions and Direct interactive proof systems.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

The Subgraph Testing Model.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Testing Graphs in Vertex-Distribution-Free Models.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Flexible models for testing graph properties.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Every set in P is strongly testable under a suitable encoding.

[BibT_eX]

[DOI]

Irit Dinur

Electron. Colloquium Comput. Complex., 2018

Universal Locally Testable Codes.

[BibT_eX]

[DOI]

Chic. J. Theor. Comput. Sci., 2018

Matrix rigidity of random Toeplitz matrices.

[BibT_eX]

[DOI]

Avishay Tal

Comput. Complex., 2018

Counting t-Cliques: Worst-Case to Average-Case Reductions and Direct Interactive Proof Systems.

[BibT_eX]

[DOI]

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions.

[BibT_eX]

[DOI]

Avishay Tal

Electron. Colloquium Comput. Complex., 2017

Worst-case to Average-case reductions for subclasses of P.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Simple doubly-efficient interactive proof systems for locally-characterizable sets.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Overview of the doubly-efficient interactive proof systems of RRR.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

On the doubly-efficient interactive proof systems of GKR.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Introduction to Property Testing.

[BibT_eX]

[DOI]

Cambridge University Press, ISBN: 9781108135252, 2017

2016

Testing Bipartiteness of Graphs in Sublinear Time.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Testing Bipartiteness in the Dense-Graph Model.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Estimating Simple Graph Parameters in Sublinear Time.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Two-sided error proximity oblivious testing.

[BibT_eX]

[DOI]

Igor Shinkar

Random Struct. Algorithms, 2016

Deconstructing 1-local expanders.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Reducing testing affine spaces to testing linearity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

On Emulating Interactive Proofs with Public Coins.

[BibT_eX]

[DOI]

Maya Leshkowitz

Electron. Colloquium Comput. Complex., 2016

The uniform distribution is complete with respect to testing identity to a fixed distribution.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Special Issue on the 10th Theory of Cryptography Conference: Editor's Foreword.

[BibT_eX]

[DOI]

Comput. Complex., 2016

2015

On Randomness Extraction in AC0.

[BibT_eX]

[DOI]

Emanuele Viola

Electron. Colloquium Comput. Complex., 2015

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

[BibT_eX]

[DOI]

Ron Rothblum

Electron. Colloquium Comput. Complex., 2015

Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs - (Extended Abstract).

[BibT_eX]

[DOI]

Ron D. Rothblum

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

Super-Perfect Zero-Knowledge Proofs.

[BibT_eX]

[DOI]

Liav Teichner

Electron. Colloquium Comput. Complex., 2014

On Learning and Testing Dynamic Environments.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Strong Locally Testable Codes with Relaxed Local Decoders.

[BibT_eX]

[DOI]

Ilan Komargodski

Electron. Colloquium Comput. Complex., 2014

2013

A Short Tutorial of Zero-Knowledge.

[BibT_eX]

[DOI]

Proceedings of the Secure Multi-Party Computation, 2013

General Cryptographic Protocols: The Very Basics.

[BibT_eX]

[DOI]

Proceedings of the Secure Multi-Party Computation, 2013

More Constructions of Lossy and Correlation-Secure Trapdoor Functions.

[BibT_eX]

[DOI]

David Mandell Freeman

J. Cryptol., 2013

On Derandomizing Algorithms that Err Extremely Rarely.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

On Sample-Based Testers.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

On Multiple Input Problems in Property Testing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

2012

On intellectual and instrumental values in science.

[BibT_eX]

[DOI]

SIGACT News, 2012

On struggle and competition in scientic fields.

[BibT_eX]

[DOI]

SIGACT News, 2012

The tensor product of two good codes is not necessarily robustly testable.

[BibT_eX]

[DOI]

Or Meir

Inf. Process. Lett., 2012

On the possibilities and limitations of pseudodeterministic algorithms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Two-Sided Error Proximity Oblivious Testing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

On the Effect of the Proximity Parameter on Property Testers.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Finding Cycles and Trees in Sublinear Time.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Invitation to complexity theory.

[BibT_eX]

[DOI]

XRDS, 2012

Special issue from RANDOM'09: Editors' Foreword.

[BibT_eX]

[DOI]

Comput. Complex., 2012

Hierarchy Theorems for Property Testing.

[BibT_eX]

[DOI]

Comput. Complex., 2012

Two-Sided Error Proximity Oblivious Testing - (Extended Abstract).

[BibT_eX]

[DOI]

Igor Shinkar

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

On Proximity-Oblivious Testing.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

Algorithmic Aspects of Property Testing in the Dense Graphs Model.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

On the complexity of computational problems regarding distributions (a survey).

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Enhancements of Trapdoor Permutations.

[BibT_eX]

[DOI]

Ron Rothblum

Electron. Colloquium Comput. Complex., 2011

Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly.

[BibT_eX]

[DOI]

Or Meir

Electron. Colloquium Comput. Complex., 2011

Monotone Circuits: One-Way Functions versus Pseudorandom Generators.

[BibT_eX]

[DOI]

Rani Izsak

Electron. Colloquium Comput. Complex., 2011

Two Comments on Targeted Canonical Derandomizers.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Testing Graph Blow-Up.

[BibT_eX]

[DOI]

Lidor Avigad

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

Another Proof That BPP Í PH\mathcal{BPP}\subseteq \mathcal{PH} (and More).

[BibT_eX]

[DOI]

David Zuckerman

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

On the Circuit Complexity of Perfect Hashing.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Simplified Derandomization of BPP Using a Hitting Set Generator.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

On the Complexity of Computational Problems Regarding Distributions.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

From Logarithmic Advice to Single-Bit Advice.

[BibT_eX]

[DOI]

Luca Trevisan

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

On Testing Expansion in Bounded-Degree Graphs.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

On Yao's XOR-Lemma.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

On Constructing 1-1 One-Way Functions.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Proximity Oblivious Testing and the Role of Invariances.

[BibT_eX]

[DOI]

Tali Kaufman

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Collision-Free Hashing from Lattice Problems.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Another Motivation for Reducing the Randomness Complexity of Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Contemplations on Testing Graph Properties.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

On Security Preserving Reductions - Revised Terminology.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Randomness and Computation.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Introduction to Testing Graph Properties.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

A Brief Introduction to Property Testing.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Basic Facts about Expander Graphs.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Average Case Complexity, Revisited.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Basing Non-Interactive Zero-Knowledge on (Enhanced) Trapdoor Permutations: The State of the Art.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Bravely, Moderately: A Common Theme in Four Recent Works.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Short Locally Testable Codes and Proofs.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

A Sample of Samplers: A Computational Perspective on Sampling.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Three XOR-Lemmas - An Exposition.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

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

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

In a World of P=BPP.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

A Candidate Counterexample to the Easy Cylinders Conjecture.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

On the Average-Case Complexity of Property Testing.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

The GGM Construction Does NOT Yield Correlation Intractable Function Ensembles.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Candidate One-Way Functions Based on Expander Graphs.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Strong Proofs of Knowledge.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

From Absolute Distinguishability to Positive Distinguishability.

[BibT_eX]

[DOI]

Zvika Brakerski

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

On Probabilistic versus Deterministic Provers in the Definition of Proofs of Knowledge.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Proving Computational Ability.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

Testing Graph Blow-Up.

[BibT_eX]

[DOI]

Lidor Avigad

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

2010

On the Implementation of Huge Random Objects.

[BibT_eX]

[DOI]

Asaf Nussboim

SIAM J. Comput., 2010

Proximity Oblivious Testing and the Role of Invariances.

[BibT_eX]

[DOI]

Tali Kaufman

Electron. Colloquium Comput. Complex., 2010

In a World of P=BPP.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Introduction to Testing Graph Properties.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

On Testing Computability by Small Width OBDDs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

On The Randomness Complexity of Property Testing.

[BibT_eX]

[DOI]

Or Sheffet

Comput. Complex., 2010

Erratum for: on basing one-way functions on NP-hardness.

[BibT_eX]

[DOI]

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Algorithmic Aspects of Property Testing in the Dense Graphs Model.

[BibT_eX]

[DOI]

Proceedings of the Property Testing - Current Research and Surveys, 2010

Hierarchy Theorems for Property Testing.

[BibT_eX]

[DOI]

Proceedings of the Property Testing - Current Research and Surveys, 2010

Introduction to Testing Graph Properties.

[BibT_eX]

[DOI]

Proceedings of the Property Testing - Current Research and Surveys, 2010

Short Locally Testable Codes and Proofs: A Survey in Two Parts.

[BibT_eX]

[DOI]

Proceedings of the Property Testing - Current Research and Surveys, 2010

The Program of the Mini-Workshop.

[BibT_eX]

[DOI]

Proceedings of the Property Testing - Current Research and Surveys, 2010

A Brief Introduction to Property Testing.

[BibT_eX]

[DOI]

Proceedings of the Property Testing - Current Research and Surveys, 2010

P, NP, and NP-Completeness: The Basics of Complexity Theory.

[BibT_eX]

[DOI]

Cambridge University Press, ISBN: 9780511761355, 2010

2009

On our duties as scientists.

[BibT_eX]

[DOI]

SIGACT News, 2009

A Theory of Goal-Oriented Communication.

[BibT_eX]

[DOI]

Brendan Juba

Electron. Colloquium Comput. Complex., 2009

A Candidate Counterexample to the Easy Cylinders Conjecture.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

From absolute distinguishability to positive distinguishability.

[BibT_eX]

[DOI]

Zvika Brakerski

Electron. Colloquium Comput. Complex., 2009

2008

Computational complexity: a conceptual perspective.

[BibT_eX]

[DOI]

SIGACT News, 2008

Universal Arguments and their Applications.

[BibT_eX]

[DOI]

Boaz Barak

SIAM J. Comput., 2008

Probabilistic Proof Systems: A Primer.

[BibT_eX]

[DOI]

Found. Trends Theor. Comput. Sci., 2008

Preface to the Special Issue from Random'06.

[BibT_eX]

[DOI]

Comput. Complex., 2008

Computational complexity - a conceptual perspective.

[BibT_eX]

[DOI]

Cambridge University Press, ISBN: 9780511804106, 2008

2007

On the Average-Case Complexity of Property Testing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

Special Issue On Worst-case Versus Average-case Complexity Editors' Foreword.

[BibT_eX]

[DOI]

Comput. Complex., 2007

On Approximating the Average Distance Between Points.

[BibT_eX]

[DOI]

Kfir Barhum

Adi Shraibman

Proceedings of the Approximation, 2007

2006

Special Issue on Randomness and Complexity.

[BibT_eX]

SIAM J. Comput., 2006

Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding.

[BibT_eX]

[DOI]

SIAM J. Comput., 2006

Session-Key Generation Using Human Passwords Only.

[BibT_eX]

[DOI]

Yehuda Lindell

J. Cryptol., 2006

On Post-Modern Cryptography.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2006

On Expected Probabilistic Polynomial-Time Adversaries -- A suggestion for restricted definitions and their benefits.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

On Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Lower bounds for linear locally decodable codes and private information retrieval.

[BibT_eX]

[DOI]

Comput. Complex., 2006

On basing one-way functions on NP-hardness.

[BibT_eX]

[DOI]

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

On Teaching the Basics of Complexity Theory.

[BibT_eX]

[DOI]

Proceedings of the Theoretical Computer Science, 2006

On Promise Problems: A Survey.

[BibT_eX]

[DOI]

Proceedings of the Theoretical Computer Science, 2006

2005

Foundations of Cryptography - A Primer.

[BibT_eX]

[DOI]

Found. Trends Theor. Comput. Sci., 2005

Bravely, Moderately: A Common Theme in Four Recent Results

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

Approximating Average Parameters of Graphs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

Short Locally Testable Codes and Proofs (Survey)

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

Contemplations on Testing Graph Properties.

[BibT_eX]

[DOI]

Proceedings of the Sublinear Algorithms, 17.07. - 22.07.2005, 2005

Short PCPs Verifiable in Polylogarithmic Time.

[BibT_eX]

[DOI]

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004

The random oracle methodology, revisited.

[BibT_eX]

[DOI]

J. ACM, 2004

The Power of Verification Queries in Message Authentication and Authenticated Encryption.

[BibT_eX]

[DOI]

Anton Mityagin

IACR Cryptol. ePrint Arch., 2004

From logarithmic advice to single-bit advice

[BibT_eX]

[DOI]

Luca Trevisan

Electron. Colloquium Comput. Complex., 2004

On Estimating the Average Degree of a Graph

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2004

The Foundations of Cryptography - Volume 2: Basic Applications.

[BibT_eX]

[DOI]

Cambridge University Press, ISBN: 9780511721656, 2004

Pseudorandomness - Part I.

[BibT_eX]

[DOI]

Proceedings of the Computational Complexity Theory., 2004

Preface to "Week Three: Randomness in Computation".

[BibT_eX]

[DOI]

Proceedings of the Computational Complexity Theory., 2004

2003

Almost k-wise independence versus k-wise independence.

[BibT_eX]

[DOI]

Noga Alon

Yishay Mansour

Inf. Process. Lett., 2003

On the random-oracle methodology as applied to length-restricted signature schemes.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2003

Bounds on 2-Query Codeword Testing.

[BibT_eX]

[DOI]

Eli Ben-Sasson

Electron. Colloquium Comput. Complex., 2003

Cryptography and cryptographic protocols.

[BibT_eX]

[DOI]

Distributed Comput., 2003

2002

On Chosen Ciphertext Security of Multiple Encryptions.

[BibT_eX]

[DOI]

Yoad Lustig

Moni Naor

IACR Cryptol. ePrint Arch., 2002

Zero-Knowledge twenty years after its invention

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2002

Locally Testable Codes and PCPs of Almost-Linear Length

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2002

On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators

[BibT_eX]

[DOI]

Vered Rosen

Electron. Colloquium Comput. Complex., 2002

The GGM Construction does NOT yield Correlation Intractable Function Ensembles.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2002

Derandomization that is rarely wrong from short advice that is typically good

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2002

On interactive proofs with a laconic prover.

[BibT_eX]

[DOI]

Comput. Complex., 2002

Property Testing in Bounded Degree Graphs.

[BibT_eX]

[DOI]

Algorithmica, 2002

Zero-Knowledge.

[BibT_eX]

[DOI]

Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

2001

Resettably-Sound Zero-Knowledge and its Applications.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2001

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2001

Concurrent Zero-Knowledge With Timing, Revisited

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2001

On the (Im)possibility of Obfuscating Programs

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2001

Three Theorems regarding Testing Graph Properties.

[BibT_eX]

[DOI]

Luca Trevisan

Electron. Colloquium Comput. Complex., 2001

The Foundations of Cryptography - Volume 1: Basic Techniques.

[BibT_eX]

[DOI]

Cambridge University Press, ISBN: 9780511546891, 2001

2000

A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem.

[BibT_eX]

[DOI]

Shmuel Safra

SIAM J. Comput., 2000

Preface.

[BibT_eX]

[DOI]

J. Cryptol., 2000

On the Limits of Nonapproximability of Lattice Problems.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2000

On Security Preserving Reductions - Revised Terminology.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2000

Candidate One-Way Functions Based on Expander Graphs

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2000

On Pseudorandomness with respect to Deterministic Observers.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2000

On Testing Expansion in Bounded-Degree Graphs

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2000

Simplified derandomization of BPP using a hitting set generator.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2000

Testing Monotonicity.

[BibT_eX]

[DOI]

Comb., 2000

Resettable zero-knowledge (extended abstract).

[BibT_eX]

[DOI]

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

On Pseudorandomness with respect to Deterministic Observes.

[BibT_eX]

Proceedings of the ICALP Workshops 2000, 2000

Pseudorandomness.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

1999

Computational Sample Complexity.

[BibT_eX]

[DOI]

Scott E. Decatur

SIAM J. Comput., 1999

Computational Indistinguishability: A Sample Hierarchy.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1999

The Graph Clustering Problem has a Perfect Zero-Knowledge Interactive Proof.

[BibT_eX]

[DOI]

Alfredo De Santis

Giovanni Di Crescenzo

Giuseppe Persiano

Inf. Process. Lett., 1999

Approximating Shortest Lattice Vectors is not Harder than Approximating Closest Lattice Vectors.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1999

Resettable Zero-Knowledge.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1999

Interleaved Zero-Knowledge in the Public-Key Model.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1999

Improved Testing Algorithms for Monotonicity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1999

Can Statistical Zero Knowledge be made Non-Interactive? or On the Relationship of SZK and NISZK

[BibT_eX]

[DOI]

Amit Sahai

Electron. Colloquium Comput. Complex., 1999

A Sublinear Bipartiteness Tester for Bounded Degree Graphs.

[BibT_eX]

[DOI]

Comb., 1999

Quantifying Knowledge Complexity.

[BibT_eX]

[DOI]

Comput. Complex., 1999

Improved Derandomization of BPP Using a Hitting Set Generator.

[BibT_eX]

[DOI]

Proceedings of the Randomization, 1999

Stateless Evaluation of Pseudorandom Functions: Security beyond the Birthday Barrier.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1999

1998

Computational Indistinguishability: Algorithms vs. Circuits.

[BibT_eX]

[DOI]

Bernd Meyer

Theor. Comput. Sci., 1998

Computational Complexity and Knowledge Complexity.

[BibT_eX]

[DOI]

Rafail Ostrovsky

SIAM J. Comput., 1998

Fault-Tolerant Computation in the Full Information Model.

[BibT_eX]

[DOI]

Nathan Linial

SIAM J. Comput., 1998

Free Bits, PCPs, and Nonapproximability-Towards Tight Results.

[BibT_eX]

[DOI]

SIAM J. Comput., 1998

Efficient approximation of product distributions.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 1998

Private Information Retrieval.

[BibT_eX]

[DOI]

J. ACM, 1998

On the Complexity of Interactive Proofs with Bounded Communication.

[BibT_eX]

[DOI]

Johan Håstad

Inf. Process. Lett., 1998

On the possibility of basing Cryptography on the assumption that P ≠ NP.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 1998

Deterministic Amplification of Space Bounded Probabilistic Algorithms.

[BibT_eX]

[DOI]

Ziv Bar-Yossef

Electron. Colloquium Comput. Complex., 1998

Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1998

Chinese Remaindering with Errors

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1998

Learning Polynomials with Queries - The Highly Noisy Case.

[BibT_eX]

[DOI]

Ronitt Rubinfeld

Electron. Colloquium Comput. Complex., 1998

Uniform Generation of NP-witnesses using an NP-oracle.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1998

The Graph Clustering Problem has a Perfect Zero-Knowledge Proof

[BibT_eX]

[DOI]

Alfredo De Santis

Giovanni Di Crescenzo

Giuseppe Persiano

Electron. Colloquium Comput. Complex., 1998

Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge.

[BibT_eX]

[DOI]

Amit Sahai

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

A Sublinear Bipartiteness Tester for Bunded Degree Graphs.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

The Random Oracle Methodology, Revisited (Preliminary Version).

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Testing Monotonicity.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Modern Cryptography, Probabilistic Proofs and Pseudorandomness.

[BibT_eX]

[DOI]

Algorithms and Combinatorics 17, Springer, ISBN: 978-3-540-64766-9, 1998

1997

Theory of computing: a scientific perspective (extended abstract).

[BibT_eX]

[DOI]

SIGACT News, 1997

On Universal Learning Algorithms.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1997

Self-Delegation with Controlled Propagation - or - What If You Lose Your Laptop.

[BibT_eX]

[DOI]

Birgit Pfitzmann

Ronald L. Rivest

IACR Cryptol. ePrint Arch., 1997

A Probabilistic Error-Correcting Scheme.

[BibT_eX]

[DOI]

Scott E. Decatur

IACR Cryptol. ePrint Arch., 1997

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1997

Combinatorial Property Testing (a survey).

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1997

Another proof that BPP subseteq PH (and more).

[BibT_eX]

[DOI]

David Zuckerman

Electron. Colloquium Comput. Complex., 1997

On the Limits of Non-Approximability of Lattice Problems

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1997

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1997

Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1997

On the Foundations of Modern Cryptography.

[BibT_eX]

[DOI]

Christos H. Papadimitriou

Proceedings of the Advances in Cryptology, 1997

1996

The future of computational complexity theory: part I.

[BibT_eX]

[DOI]

Alexander A. Razborov

Michael Sipser

SIGACT News, 1996

On the Composition of Zero-Knowledge Proof Systems.

[BibT_eX]

[DOI]

SIAM J. Comput., 1996

How to Construct Constant-Round Zero-Knowledge Proof Systems for NP.

[BibT_eX]

Ariel Kahan

J. Cryptol., 1996

On-Line/Off-Line Digital Signatures.

[BibT_eX]

[DOI]

J. Cryptol., 1996

Software Protection and Simulation on Oblivious RAMs.

[BibT_eX]

[DOI]

Rafail Ostrovsky

J. ACM, 1996

Property Testing and its connection to Learning and Approximation

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1996

Public-Key Cryptosystems from Lattice Reduction Problems

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1996

The Graph Clustering Problem has a Perfect Zero-Knowledge Proof.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1996

A Combinatorial Consistency Lemma with application to the PCP Theorem

[BibT_eX]

[DOI]

Shmuel Safra

Electron. Colloquium Comput. Complex., 1996

Collision-Free Hashing from Lattice Problems

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1996

On the Circuit Complexity of Perfect Hashing

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1996

On the Message Complexity of Interactive Proof Systems

[BibT_eX]

[DOI]

Johan Håstad

Electron. Colloquium Comput. Complex., 1996

Theory of Computing: A Scientific Perspective.

[BibT_eX]

[DOI]

ACM Comput. Surv., 1996

Adaptively Secure Multi-Party Computation.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

1995

Lower Bounds for Sampling Algorithms for Estimating the Average.

[BibT_eX]

[DOI]

Guy Even

Inf. Process. Lett., 1995

Three XOR-Lemmas - An Exposition

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1995

On Yao's XOR-Lemma

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1995

On Constructing 1-1 One-Way Functions

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1995

Free Bits, PCP and Non-Approximability - Towards Tight Results

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1995

Incremental cryptography and application to virus protection.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Free Bits, PCPs and Non-Approximability - Towards Tight Results.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Honest Verifier vs Dishonest Verifier in Public Coin Zero-Knowledge Proofs.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1995

1994

A taxonomy of proof systems (part 2).

[BibT_eX]

[DOI]

SIGACT News, 1994

Definitions and Properties of Zero-Knowledge Proof Systems.

[BibT_eX]

[DOI]

Yair Oren

J. Cryptol., 1994

The Random Oracle Hypothesis Is False.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1994

Probabilistic Proof Systems (A Survey)

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1994

Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1994

Tiny families of functions with random properties (preliminary version): a quality-size trade-off for hashing.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Computational complexity and knowledge complexity (extended abstract).

[BibT_eX]

[DOI]

Rafail Ostrovsky

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Incremental Cryptography: The Case of Hashing and Signing.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1994

1993

A taxonomy of proof systems (part 1).

[BibT_eX]

[DOI]

SIGACT News, 1993

On the Existence of Pseudorandom Generators.

[BibT_eX]

[DOI]

Michael Luby

SIAM J. Comput., 1993

Addendum to "Simple Construction of Almost k-wise Independent Random Variables".

[BibT_eX]

[DOI]

Random Struct. Algorithms, 1993

A Perfect Zero-Knowledge Proof System for a Problem Equivalent to the Discrete Logarithm.

[BibT_eX]

[DOI]

Eyal Kushilevitz

J. Cryptol., 1993

A Uniform-Complexity Treatment of Encryption and Zero-Knowledge.

[BibT_eX]

[DOI]

J. Cryptol., 1993

Bounds on Tradeoffs Between Randomness and Communication Complexity.

[BibT_eX]

[DOI]

Comput. Complex., 1993

Randomness in Interactive Proofs.

[BibT_eX]

[DOI]

Comput. Complex., 1993

Asynchronous secure computation.

[BibT_eX]

[DOI]

Michael Ben-Or

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

1992

Critique of some trends in the TCS community in light of two controversies.

[BibT_eX]

[DOI]

SIGACT News, 1992

Sparse Pseudorandom Distributions.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 1992

Simple Construction of Almost k-wise Independent Random Variables.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 1992

On the Theory of Average Case Complexity.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1992

On the Time-Complexity of Broadcast in Multi-hop Radio Networks: An Exponential Gap Between Determinism and Randomization.

[BibT_eX]

[DOI]

Reuven Bar-Yehuda

Alon Itai

J. Comput. Syst. Sci., 1992

Approximations of General Independent Distributions

[BibT_eX]

[DOI]

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

On the Complexity of Global Computation in the Presence of Link Failures: The Case of Uni-Directional Faults.

[BibT_eX]

[DOI]

Dror Sneh

Proceedings of the Eleventh Annual ACM Symposium on Principles of Distributed Computing, 1992

Towards a Computational Theory of Statistical Tests (Extended Abstract)

[BibT_eX]

[DOI]

Manuel Blum

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

On Defining Proofs of Knowledge.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1992

1991

Proofs that Yield Nothing But Their Validity for All Languages in NP Have Zero-Knowledge Proof Systems.

[BibT_eX]

[DOI]

J. ACM, 1991

On the Complexity of Computation in the Presence of Link Failures: The Case of a Ring.

[BibT_eX]

[DOI]

Liuba Shrira

Distributed Comput., 1991

Efficient Emulation of Single-Hop Radio Network with Collision Detection on Multi-Hop Radio Network with no Collision Detection.

[BibT_eX]

[DOI]

Reuven Bar-Yehuda

Alon Itai

Distributed Comput., 1991

Fault-tolerant Computation in the Full Information Model (Extended Abstract)

[BibT_eX]

[DOI]

Nathan Linial

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1990

A Trade-Off between Information and Communication in Broadcast Protocols

[BibT_eX]

[DOI]

J. ACM, April, 1990

A fair protocol for signing contracts.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 1990

The Best of Both Worlds: Guaranteeing Termination in Fast Randomized Byzantine Agreement Protocols.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1990

A Note on Computational Indistinguishability.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1990

On the number of monochromatic close pairs of beads in a rosary.

[BibT_eX]

[DOI]

Discret. Math., 1990

An Improved Parallel Algorithm for Integer GCD.

[BibT_eX]

[DOI]

Algorithmica, 1990

A Quantitative Approach to Dynamic Networks.

[BibT_eX]

[DOI]

Baruch Awerbuch

Amir Herzberg

Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing, 1990

Security Preserving Amplification of Hardness

[BibT_eX]

[DOI]

Russell Impagliazzo

Ramarathnam Venkatesan

David Zuckerman

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Simple Constructions of Almost k-Wise Independent Random Variables

[BibT_eX]

[DOI]

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989

On the power of two-point based sampling.

[BibT_eX]

[DOI]

J. Complex., 1989

On Completeness and Soundness in Interactive Proof Systems.

[BibT_eX]

Adv. Comput. Res., 1989

A Hard-Core Predicate for all One-Way Functions

[BibT_eX]

[DOI]

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

Source to Destination Communication in the Presence of Faults.

[BibT_eX]

[DOI]

Amir Herzberg

Yishay Mansour

Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, 1989

On-Line/Off-Line Digital Schemes.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1989

On the Theory of Average Case Complexity (abstract).

[BibT_eX]

[DOI]

Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

1988

Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity.

[BibT_eX]

[DOI]

SIAM J. Comput., 1988

RSA and Rabin Functions: Certain Parts are as Hard as the Whole.

[BibT_eX]

[DOI]

SIAM J. Comput., 1988

On the Existence of Pseudorandom Generators (Extended Abstract)

[BibT_eX]

[DOI]

Michael Luby

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

A Perfect Zero-Knowledge Proof for a Problem Equivalent to Discrete Logarithm.

[BibT_eX]

[DOI]

Eyal Kushilevitz

Proceedings of the Advances in Cryptology, 1988

Everything Provable is Provable in Zero-Knowledge.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1988

A Tradeoff between Information and Communication in Broadcast Protocols.

[BibT_eX]

[DOI]

Proceedings of the VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing, 1988

1987

Electing a Leader in a Ring with Link Failures.

[BibT_eX]

[DOI]

Liuba Shrira

Acta Informatica, 1987

How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority

[BibT_eX]

[DOI]

Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

Towards a Theory of Software Protection and Simulation by Oblivious RAMs

[BibT_eX]

[DOI]

Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

On the Time-Complexity of Broadcast in Radio Networks: An Exponential Gap Between Determinism and Randomization.

[BibT_eX]

[DOI]

Reuven Bar-Yehuda

Alon Itai

Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, 1987

Interactive Proof Systems: Provers that never Fail and Random Selection (Extended Abstract)

[BibT_eX]

[DOI]

Yishay Mansour

Michael Sipser

Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

How to Solve any Protocol Problem - An Efficiency Improvement.

[BibT_eX]

[DOI]

Ronen Vainish

Proceedings of the Advances in Cryptology, 1987

1986

How to construct random functions.

[BibT_eX]

[DOI]

J. ACM, 1986

The Effect of Link Failures on Computations in Asynchronous Rings.

[BibT_eX]

[DOI]

Liuba Shrira

Proceedings of the Fifth Annual ACM Symposium on Principles of Distributed Computing, 1986

Proofs that Release Minimum Knowledge.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1986, 1986

Proofs that Yield Nothing But their Validity and a Methodology of Cryptographic Protocol Design (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

How to Prove all NP-Statements in Zero-Knowledge, and a Methodology of Cryptographic Protocol Design.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1986

Towards a Theory of Software Protection.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1986

Two Remarks Concerning the Goldwasser-Micali-Rivest Signature Scheme.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1986

1985

On the Power of Cascade Ciphers

[BibT_eX]

[DOI]

ACM Trans. Comput. Syst., 1985

A Randomized Protocol for Signing Contracts.

[BibT_eX]

[DOI]

Abraham Lempel

Commun. ACM, 1985

A Fair Protocol for Signing Contracts (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Automata, 1985

The Bit Extraction Problem of t-Resilient Functions (Preliminary Version)

[BibT_eX]

[DOI]

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

On the Security of Ping-Pong Protocols when Implemented using the RSA.

[BibT_eX]

[DOI]

Adi Shamir

Proceedings of the Advances in Cryptology, 1985

The Bit Security of Modular Squaring Given Partial Factorization of the Modulos.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1985

1984

Correction to 'DES-like functions can generate the alternating group' (Nov 83 863-865).

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 1984

On the np-completeness of certain network testing problems.

[BibT_eX]

[DOI]

Networks, 1984

How to Construct Random Functions (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

RSA/Rabin Bits are 1/2 + 1/poly(log N) Secure

[BibT_eX]

[DOI]

Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

On Concurrent Identification Protocols.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology: Proceedings of EUROCRYPT 84, 1984

On the Number of Close-and-Equal Pairs of Bits in a String.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology: Proceedings of EUROCRYPT 84, 1984

On the Cryptographic Applications of Random Functions.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1984

RSA/Rabin Least Significant Bits are 1/2 + 1/(poly(log N)) Secure.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1984

1983

DES-like functions can generate the alternating group.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 1983

Electronic Wallet.

[BibT_eX]

Proceedings of the Advances in Cryptology, 1983

A Simple Protocol for Signing Contracts.

[BibT_eX]

Proceedings of the Advances in Cryptology, 1983

1982

On the Security of Multi-Party Ping-Pong Protocols.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology: Proceedings of CRYPTO '82, 1982

1981

The Minimum-Length Generator Sequence Problem is NP-Hard.

[BibT_eX]

[DOI]