| Publication | Date of Publication | Type |
|---|
On interactive proofs of proximity with proof-oblivious queries
| 2024-09-25 | Paper |
Testing distributions of huge objects
TheoretiCS | 2024-07-03 | Paper |
Robustly self-ordered graphs: constructions and applications to property testing
TheoretiCS | 2024-06-27 | Paper |
scientific article; zbMATH DE number 7829244 (Why is no real title available?)
| 2024-04-09 | Paper |
scientific article; zbMATH DE number 7829310 (Why is no real title available?)
| 2024-04-09 | Paper |
A lower bound on the complexity of testing grained distributions
Computational Complexity | 2023-12-02 | Paper |
Good permutation codes based on the shuffle-exchange network
Israel Journal of Mathematics | 2023-10-23 | Paper |
Robustly self-ordered graphs: constructions and applications to property testing
| 2023-07-12 | Paper |
Communication complexity with defective randomness
| 2023-07-12 | Paper |
Probabilistic proof systems -- a survey
Lecture Notes in Computer Science | 2022-11-09 | Paper |
Deconstructing 1-Local Expanders
Lecture Notes in Computer Science | 2022-08-30 | Paper |
On Constructing Expanders for Any Number of Vertices
Lecture Notes in Computer Science | 2022-08-30 | Paper |
Flexible Models for Testing Graph Properties
Lecture Notes in Computer Science | 2022-08-30 | Paper |
Reducing Testing Affine Spaces to Testing Linearity of Functions
Lecture Notes in Computer Science | 2022-08-30 | Paper |
A Probabilistic Error-Correcting Scheme that Provides Partial Secrecy
Lecture Notes in Computer Science | 2022-08-30 | Paper |
Bridging a Small Gap in the Gap Amplification of Assignment Testers
Lecture Notes in Computer Science | 2022-08-30 | Paper |
On the Effect of the Proximity Parameter on Property Testers
Lecture Notes in Computer Science | 2022-08-30 | Paper |
On the Relation Between the Relative Earth Mover Distance and the Variation Distance (an Exposition)
Lecture Notes in Computer Science | 2022-08-30 | Paper |
The Uniform Distribution Is Complete with Respect to Testing Identity to a Fixed Distribution
Lecture Notes in Computer Science | 2022-08-30 | Paper |
On Emulating Interactive Proofs with Public Coins
Lecture Notes in Computer Science | 2022-08-30 | Paper |
Worst-Case to Average-Case Reductions for Subclasses of P
Lecture Notes in Computer Science | 2022-08-30 | Paper |
On the Optimal Analysis of the Collision Probability Tester (an Exposition)
Lecture Notes in Computer Science | 2022-08-30 | Paper |
Constant-Round Interactive Proof Systems for AC0[2 and NC1]
Lecture Notes in Computer Science | 2022-08-30 | Paper |
Super-Perfect Zero-Knowledge Proofs
Lecture Notes in Computer Science | 2022-08-30 | Paper |
On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions
Lecture Notes in Computer Science | 2022-08-30 | Paper |
On (Valiant’s) Polynomial-Size Monotone Formula for Majority
Lecture Notes in Computer Science | 2022-08-30 | Paper |
On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions
Lecture Notes in Computer Science | 2022-08-30 | Paper |
On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing
Lecture Notes in Computer Science | 2022-08-30 | Paper |
Two Comments on Targeted Canonical Derandomizers
Lecture Notes in Computer Science | 2022-08-30 | Paper |
Pseudo-mixing Time of Random Walks
Lecture Notes in Computer Science | 2022-08-30 | Paper |
Improved bounds on the an-complexity of \(O(1)\)-linear functions
Computational Complexity | 2022-08-01 | Paper |
Every Set in P Is Strongly Testable Under a Suitable Encoding
| 2022-07-18 | Paper |
The subgraph testing model
| 2022-07-18 | Paper |
The subgraph testing model
ACM Transactions on Computation Theory | 2022-03-07 | Paper |
On the power of cascade ciphers
Advances in cryptology. Proceedings of CRYPTO '84 (a workshop on the theory and application of cryptographic techniques held at the University of California, Santa Barbara, August 19--22, 1984) | 2022-01-08 | Paper |
A simple protocol for signing contracts
Advances in cryptology. Proceedings of CRYPTO '84 (a workshop on the theory and application of cryptographic techniques held at the University of California, Santa Barbara, August 19--22, 1984) | 2022-01-08 | Paper |
Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP
Theoretical Computer Science | 2021-07-22 | Paper |
Simple doubly-efficient interactive proof systems for locally-characterizable sets
| 2021-06-15 | Paper |
Cryptography and cryptographic protocols
Distributed Computing | 2020-12-04 | Paper |
Testing graphs in vertex-distribution-free models
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Hierarchy theorems for testing properties in size-oblivious query complexity
Computational Complexity | 2019-12-19 | Paper |
Strong locally testable codes with relaxed local decoders
ACM Transactions on Computation Theory | 2019-12-16 | Paper |
On sample-based testers
ACM Transactions on Computation Theory | 2019-12-06 | Paper |
Universal locally testable codes
Chicago Journal of Theoretical Computer Science | 2018-08-08 | Paper |
Matrix rigidity of random Toeplitz matrices
Computational Complexity | 2018-08-03 | Paper |
On doubly-efficient interactive proof systems
Foundations and Trends® in Theoretical Computer Science | 2018-07-02 | Paper |
Proofs of proximity for context-free languages and read-once branching programs
Information and Computation | 2018-06-14 | Paper |
On learning and testing dynamic environments
Journal of the ACM | 2018-05-17 | Paper |
On randomness extraction in \({\mathcal{AC}}^0\)
| 2018-01-24 | Paper |
Strong locally testable codes with relaxed local decoders
| 2018-01-24 | Paper |
Introduction to Property Testing
| 2017-10-25 | Paper |
Matrix rigidity of random toeplitz matrices
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
On the complexity of global computation in the presence of link failures: the case of uni-directional faults
Proceedings of the eleventh annual ACM symposium on Principles of distributed computing - PODC '92 | 2017-08-21 | Paper |
On Sample-Based Testers
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science | 2017-05-19 | Paper |
On the possibilities and limitations of pseudodeterministic algorithms
Proceedings of the 4th conference on Innovations in Theoretical Computer Science | 2017-05-16 | Paper |
RSA/Rabin least significant bits are $$ \tfrac{1} {2} + \tfrac{1} {{poly \left( {\log N} \right)}} $$ secure (Extended Abstract)
Advances in cryptology. Proceedings of CRYPTO '84 (a workshop on the theory and application of cryptographic techniques held at the University of California, Santa Barbara, August 19--22, 1984) | 2017-04-10 | Paper |
On the Cryptographic Applications of Random Functions (Extended Abstract)
Advances in cryptology. Proceedings of CRYPTO '84 (a workshop on the theory and application of cryptographic techniques held at the University of California, Santa Barbara, August 19--22, 1984) | 2017-04-10 | Paper |
On multiple input problems in property testing
| 2017-03-22 | Paper |
Input-oblivious proof systems and a uniform complexity perspective on P/poly
ACM Transactions on Computation Theory | 2016-10-24 | Paper |
Chinese remaindering with errors
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
Computational complexity and knowledge complexity (extended abstract)
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 | 2016-09-01 | Paper |
Tiny families of functions with random properties: a quality-size trade-off for hashing (preliminary version)
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 | 2016-09-01 | Paper |
The graph clustering problem has a perfect zero-knowledge interactive proof
Information Processing Letters | 2016-06-16 | Paper |
On the complexity of interactive proofs with bounded communication
Information Processing Letters | 2016-06-09 | Paper |
On universal learning algorithms
Information Processing Letters | 2016-05-26 | Paper |
Two-sided error proximity oblivious testing
Random Structures & Algorithms | 2016-03-22 | Paper |
Proofs of proximity for context-free languages and read-once branching programs
Automata, Languages, and Programming | 2015-10-27 | Paper |
On derandomizing algorithms that err extremely rarely
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
Asynchronous secure computation
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 | 2015-05-07 | Paper |
On proximity oblivious testing
Proceedings of the forty-first annual ACM symposium on Theory of computing | 2015-02-04 | Paper |
On basing one-way functions on NP-hardness
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
Finding cycles and trees in sublinear time
Random Structures & Algorithms | 2014-10-16 | Paper |
Resettable zero-knowledge (extended abstract)
Proceedings of the thirty-second annual ACM symposium on Theory of computing | 2014-09-26 | Paper |
Erratum for: ``On basing one-way functions on NP-hardness
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
On the (im)possibility of obfuscating programs
Journal of the ACM | 2014-02-17 | Paper |
A theory of goal-oriented communication
Journal of the ACM | 2014-02-17 | Paper |
Enhancements of trapdoor permutations
Journal of Cryptology | 2013-08-01 | Paper |
More constructions of lossy and correlation-secure trapdoor functions
Journal of Cryptology | 2013-04-15 | Paper |
Two-sided error proximity oblivious testing (extended abstract)
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2012-11-02 | Paper |
Monotone circuits: one-way functions versus pseudorandom generators
Theory of Computing | 2012-09-27 | Paper |
The tensor product of two good codes is not necessarily robustly testable
Information Processing Letters | 2012-07-20 | Paper |
Hierarchy theorems for property testing
Computational Complexity | 2012-06-26 | Paper |
Basic Facts about Expander Graphs
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
Simplified derandomization of BPP using a hitting set generator
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
On security preserving reductions -- revised terminology
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
A Brief Introduction to Property Testing
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
Average case complexity, revisited
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
Proximity oblivious testing and the role of invariances
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
Proving computational ability
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
Strong proofs of knowledge
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
The GGM construction does NOT yield correlation intractable function ensembles
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
On the average-case complexity of property testing
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
From absolute distinguishability to positive distinguishability
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
Bravely, moderately: a common theme in four recent works
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
Contemplations on Testing Graph Properties
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
Another motivation for reducing the randomness complexity of algorithms
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
On constructing 1-1 one-way functions
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
Finding the shortest move-sequence in the graph-generalized 15-puzzle is NP-hard
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
Randomness and computation
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
Collision-free hashing from lattice problems
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More)
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
A candidate counterexample to the easy cylinders conjecture
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
Notes on Levin's theory of average-case complexity
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
From logarithmic advice to single-bit advice
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
On the Circuit Complexity of Perfect Hashing
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
Basing non-interactive zero-knowledge on (enhanced) trapdoor permutations: the state of the art
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
On probabilistic versus deterministic provers in the definition of proofs of knowledge
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
Introduction to testing graph properties
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
A sample of samplers: a computational perspective on sampling
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
On the complexity of computational problems regarding distributions
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
Candidate one-way functions based on expander graphs
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
Three XOR-lemmas -- an exposition
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
On Yao's XOR-lemma
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
In a world of \(\mathrm{P}=\mathrm{BPP}\)
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
Short locally testable codes and proofs
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
Testing graph blow-up
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
On testing expansion in bounded-degree graphs
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
Testing graph blow-up
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2011-08-17 | Paper |
Proximity Oblivious Testing and the Role of Invariances
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2011-08-17 | Paper |
Algorithmic aspects of property testing in the dense graphs model
SIAM Journal on Computing | 2011-07-29 | Paper |
On Proximity-Oblivious Testing
SIAM Journal on Computing | 2011-07-29 | Paper |
On the implementation of huge random objects
SIAM Journal on Computing | 2011-04-04 | Paper |
On the randomness complexity of property testing
Computational Complexity | 2011-02-07 | Paper |
The random oracle methodology, revisited.
Journal of the ACM | 2011-02-01 | Paper |
P, NP, and NP-completeness. The basics of computational complexity.
| 2011-01-10 | Paper |
A brief introduction to property testing
Property Testing | 2010-10-12 | Paper |
Algorithmic Aspects of Property Testing in the Dense Graphs Model
Property Testing | 2010-10-12 | Paper |
The program of the mini-workshop
Property Testing | 2010-10-12 | Paper |
Short locally testable codes and proofs: a survey in two parts
Property Testing | 2010-10-12 | Paper |
Introduction to testing graph properties
Property Testing | 2010-10-12 | Paper |
Hierarchy theorems for property testing
Property Testing | 2010-10-12 | Paper |
Pseudorandomness
| 2010-09-10 | Paper |
On testing computability by small width OBDDs
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2010-09-10 | Paper |
A primer on pseudorandom generators
| 2010-08-31 | Paper |
Robust PSPs of proximity, shorter PSPs and applications to coding
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing | 2010-08-15 | Paper |
Concurrent zero-knowledge with timing, revisited
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
More constructions of lossy and correlation-secure trapdoor functions
Public Key Cryptography – PKC 2010 | 2010-05-28 | Paper |
Bounds on \(2\)-query codeword testing
Lecture Notes in Computer Science | 2010-05-26 | Paper |
On expected probabilistic polynomial-time adversaries: a suggestion for restricted definitions and their benefits
Journal of Cryptology | 2010-03-01 | Paper |
Foundations of Cryptography
| 2010-01-07 | Paper |
Universal Arguments and their Applications
SIAM Journal on Computing | 2009-11-06 | Paper |
Algorithmic Aspects of Property Testing in the Dense Graphs Model
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-10-28 | Paper |
Hierarchy Theorems for Property Testing
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-10-28 | Paper |
Almost \(k\)-wise independence versus \(k\)-wise independence
Information Processing Letters | 2009-07-09 | Paper |
Theory of Cryptography
Lecture Notes in Computer Science | 2009-05-14 | Paper |
On the Randomness Complexity of Property Testing
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-02-17 | Paper |
On Approximating the Average Distance Between Points
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-02-17 | Paper |
Locally testable codes and PCPs of almost-linear length
Journal of the ACM | 2008-12-21 | Paper |
Probabilistic Proof Systems: A Primer
Foundations and Trends® in Theoretical Computer Science | 2008-10-20 | Paper |
Foundations of Cryptography – A Primer
Foundations and Trends™ in Theoretical Computer Science | 2008-09-01 | Paper |
Approximating average parameters of graphs
Random Structures & Algorithms | 2008-07-21 | Paper |
Computational Complexity
| 2008-06-30 | Paper |
Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
SIAM Journal on Computing | 2007-09-07 | Paper |
On Expected Probabilistic Polynomial-Time Adversaries: A Suggestion for Restricted Definitions and Their Benefits
Theory of Cryptography | 2007-08-30 | Paper |
Approximating Average Parameters of Graphs
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2007-08-28 | Paper |
Lower bounds for linear locally decodable codes and private information retrieval
Computational Complexity | 2007-01-24 | Paper |
scientific article; zbMATH DE number 5081837 (Why is no real title available?)
| 2007-01-05 | Paper |
Session-key generation using human passwords only
Journal of Cryptology | 2006-11-03 | Paper |
scientific article; zbMATH DE number 2196514 (Why is no real title available?)
| 2005-08-22 | Paper |
scientific article; zbMATH DE number 2134906 (Why is no real title available?)
| 2005-02-18 | Paper |
Private information retrieval
Journal of the ACM | 2005-01-25 | Paper |
Property testing and its connection to learning and approximation
Journal of the ACM | 2005-01-25 | Paper |
Foundations of Cryptography
| 2004-11-09 | Paper |
scientific article; zbMATH DE number 1687020 (Why is no real title available?)
| 2004-02-08 | Paper |
scientific article; zbMATH DE number 2019636 (Why is no real title available?)
| 2003-12-17 | Paper |
On interactive proofs with a laconic prover
Computational Complexity | 2003-11-17 | Paper |
On the security of modular exponentiation with application to the construction of pseudorandom generators
Journal of Cryptology | 2003-08-27 | Paper |
Three theorems regarding testing graph properties
Random Structures & Algorithms | 2003-08-06 | Paper |
scientific article; zbMATH DE number 1792102 (Why is no real title available?)
| 2003-05-22 | Paper |
Uniform generation of NP-witnesses using an NP-oracle
Information and Computation | 2003-01-14 | Paper |
scientific article; zbMATH DE number 1842483 (Why is no real title available?)
| 2002-12-08 | Paper |
scientific article; zbMATH DE number 1842504 (Why is no real title available?)
| 2002-12-08 | Paper |
scientific article; zbMATH DE number 1775406 (Why is no real title available?)
| 2002-09-24 | Paper |
scientific article; zbMATH DE number 1775425 (Why is no real title available?)
| 2002-09-17 | Paper |
scientific article; zbMATH DE number 1775382 (Why is no real title available?)
| 2002-09-17 | Paper |
scientific article; zbMATH DE number 1775414 (Why is no real title available?)
| 2002-08-01 | Paper |
Approximating shortest lattice vectors is not harder than approximating closest lattice vectors
Information Processing Letters | 2002-07-25 | Paper |
scientific article; zbMATH DE number 1754603 (Why is no real title available?)
| 2002-06-12 | Paper |
Foundations of Cryptography
| 2002-04-29 | Paper |
Property testing in bounded degree graphs
Algorithmica | 2002-03-07 | Paper |
scientific article; zbMATH DE number 1670863 (Why is no real title available?)
| 2001-11-11 | Paper |
Testing monotonicity
Combinatorica | 2001-06-12 | Paper |
On the limits of nonapproximability of lattice problems
Journal of Computer and System Sciences | 2001-05-28 | Paper |
Learning polynomials with queries: The highly noisy case
SIAM Journal on Discrete Mathematics | 2001-03-19 | Paper |
scientific article; zbMATH DE number 1088226 (Why is no real title available?)
| 2001-03-04 | Paper |
scientific article; zbMATH DE number 1559556 (Why is no real title available?)
| 2001-02-28 | Paper |
Preface (to the special issue on general secure multiparty computation)
Journal of Cryptology | 2000-11-27 | Paper |
scientific article; zbMATH DE number 1302844 (Why is no real title available?)
| 2000-10-17 | Paper |
Chinese remaindering with errors
IEEE Transactions on Information Theory | 2000-09-07 | Paper |
scientific article; zbMATH DE number 1418312 (Why is no real title available?)
| 2000-08-27 | Paper |
scientific article; zbMATH DE number 1306875 (Why is no real title available?)
| 2000-04-26 | Paper |
scientific article; zbMATH DE number 1261806 (Why is no real title available?)
| 2000-04-26 | Paper |
scientific article; zbMATH DE number 1418300 (Why is no real title available?)
| 2000-03-19 | Paper |
Computational Sample Complexity
SIAM Journal on Computing | 2000-03-19 | Paper |
A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem
SIAM Journal on Computing | 2000-03-19 | Paper |
scientific article; zbMATH DE number 1418269 (Why is no real title available?)
| 2000-03-19 | Paper |
scientific article; zbMATH DE number 1406782 (Why is no real title available?)
| 2000-03-01 | Paper |
A sublinear bipartiteness tester for bounded degree graphs
Combinatorica | 2000-02-21 | Paper |
Computational indistinguishability: A sample hierarchy
Journal of Computer and System Sciences | 2000-01-17 | Paper |
Efficient approximation of product distributions
| 1999-12-19 | Paper |
scientific article; zbMATH DE number 1335877 (Why is no real title available?)
| 1999-09-13 | Paper |
Quantifying knowledge complexity
Computational Complexity | 1999-09-01 | Paper |
scientific article; zbMATH DE number 1306862 (Why is no real title available?)
| 1999-08-31 | Paper |
scientific article; zbMATH DE number 1263180 (Why is no real title available?)
| 1999-07-26 | Paper |
scientific article; zbMATH DE number 1256678 (Why is no real title available?)
| 1999-03-01 | Paper |
scientific article; zbMATH DE number 1256784 (Why is no real title available?)
| 1999-03-01 | Paper |
scientific article; zbMATH DE number 1241385 (Why is no real title available?)
| 1999-01-17 | Paper |
Modern cryptography, probabilistic proofs and pseudo-randomness
Algorithms and Combinatorics | 1999-01-06 | Paper |
Computational Complexity and Knowledge Complexity
SIAM Journal on Computing | 1998-09-20 | Paper |
Computational indistinguishability: algorithms vs. circuits
Theoretical Computer Science | 1998-08-13 | Paper |
Tiny families of functions with random properties: A quality-size trade-off for hashing
| 1998-07-19 | Paper |
scientific article; zbMATH DE number 1088230 (Why is no real title available?)
| 1998-06-25 | Paper |
Fault-tolerant Computation in the Full Information Model
SIAM Journal on Computing | 1998-05-10 | Paper |
Free Bits, PCPs, and Nonapproximability---Towards Tight Results
SIAM Journal on Computing | 1998-05-10 | Paper |
Software protection and simulation on oblivious RAMs
Journal of the ACM | 1998-01-21 | Paper |
scientific article; zbMATH DE number 1088229 (Why is no real title available?)
| 1998-01-07 | Paper |
scientific article; zbMATH DE number 1072531 (Why is no real title available?)
| 1997-10-08 | Paper |
scientific article; zbMATH DE number 1031002 (Why is no real title available?)
| 1997-07-06 | Paper |
Lower bounds for sampling algorithms for estimating the average
Information Processing Letters | 1997-02-28 | Paper |
How to construct constant-round zero-knowledge proof systems for NP
Journal of Cryptology | 1996-10-14 | Paper |
scientific article; zbMATH DE number 850075 (Why is no real title available?)
| 1996-09-15 | Paper |
On-line/off-line digital signatures
Journal of Cryptology | 1996-08-20 | Paper |
On the Composition of Zero-Knowledge Proof Systems
SIAM Journal on Computing | 1996-07-02 | Paper |
scientific article; zbMATH DE number 708820 (Why is no real title available?)
| 1995-11-06 | Paper |
Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
Journal of the ACM | 1994-11-24 | Paper |
The random oracle hypothesis is false
Journal of Computer and System Sciences | 1994-10-13 | Paper |
On the Existence of Pseudorandom Generators
SIAM Journal on Computing | 1994-09-13 | Paper |
Definitions and properties of zero-knowledge proof systems
Journal of Cryptology | 1994-07-24 | Paper |
Randomness in interactive proofs
Computational Complexity | 1994-05-08 | Paper |
Bounds on tradeoffs between randomness and communication complexity
Computational Complexity | 1993-10-18 | Paper |
A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm
Journal of Cryptology | 1993-08-29 | Paper |
scientific article; zbMATH DE number 177820 (Why is no real title available?)
| 1993-05-18 | Paper |
A uniform-complexity treatment of encryption and zero-knowledge
Journal of Cryptology | 1993-05-16 | Paper |
Addendum to “simple constructions of almost k-wise independent random variables”
Random Structures & Algorithms | 1993-05-16 | Paper |
On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization
Journal of Computer and System Sciences | 1993-01-16 | Paper |
Simple Constructions of Almost k-wise Independent Random Variables
Random Structures & Algorithms | 1992-10-18 | Paper |
On the theory of average case complexity
Journal of Computer and System Sciences | 1992-09-27 | Paper |
Sparse pseudorandom distributions
Random Structures & Algorithms | 1992-06-28 | Paper |
Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection
Distributed Computing | 1991-01-01 | Paper |
On the complexity of computation in the presence of link failures: The case of a ring
Distributed Computing | 1991-01-01 | Paper |
A note on computational indistinguishability
Information Processing Letters | 1990-01-01 | Paper |
scientific article; zbMATH DE number 4186980 (Why is no real title available?)
| 1990-01-01 | Paper |
On the number of monochromatic close pairs of beads in a rosary
Discrete Mathematics | 1990-01-01 | Paper |
The best of both worlds: Guaranteeing termination in fast randomized Byzantine agreement protocols
Information Processing Letters | 1990-01-01 | Paper |
scientific article; zbMATH DE number 4185032 (Why is no real title available?)
| 1990-01-01 | Paper |
scientific article; zbMATH DE number 4182679 (Why is no real title available?)
| 1990-01-01 | Paper |
A trade-off between information and communication in broadcast protocols
Journal of the ACM | 1990-01-01 | Paper |
scientific article; zbMATH DE number 4185024 (Why is no real title available?)
| 1990-01-01 | Paper |
An improved parallel algorithm for integer GCD
Algorithmica | 1990-01-01 | Paper |
On the power of two-point based sampling
Journal of Complexity | 1989-01-01 | Paper |
scientific article; zbMATH DE number 4087662 (Why is no real title available?)
| 1988-01-01 | Paper |
scientific article; zbMATH DE number 4062584 (Why is no real title available?)
| 1988-01-01 | Paper |
Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
SIAM Journal on Computing | 1988-01-01 | Paper |
RSA and Rabin Functions: Certain Parts are as Hard as the Whole
SIAM Journal on Computing | 1988-01-01 | Paper |
scientific article; zbMATH DE number 4051007 (Why is no real title available?)
| 1988-01-01 | Paper |
Electing a leader in a ring with link failures
Acta Informatica | 1987-01-01 | Paper |
scientific article; zbMATH DE number 4020467 (Why is no real title available?)
| 1987-01-01 | Paper |
scientific article; zbMATH DE number 4037759 (Why is no real title available?)
| 1987-01-01 | Paper |
scientific article; zbMATH DE number 4035726 (Why is no real title available?)
| 1987-01-01 | Paper |
scientific article; zbMATH DE number 3954815 (Why is no real title available?)
| 1986-01-01 | Paper |
scientific article; zbMATH DE number 3999326 (Why is no real title available?)
| 1986-01-01 | Paper |
scientific article; zbMATH DE number 3960854 (Why is no real title available?)
| 1986-01-01 | Paper |
scientific article; zbMATH DE number 3963720 (Why is no real title available?)
| 1986-01-01 | Paper |
scientific article; zbMATH DE number 3977016 (Why is no real title available?)
| 1985-01-01 | Paper |
DES-like functions can generate the alternating group
IEEE Transactions on Information Theory | 1983-01-01 | Paper |
scientific article; zbMATH DE number 3856987 (Why is no real title available?)
| 1983-01-01 | Paper |
The minimum-length generator sequence problem is NP-hard
Journal of Algorithms | 1981-01-01 | Paper |
