| Publication | Date of Publication | Type |
|---|
| On interactive proofs of proximity with proof-oblivious queries | 2024-09-25 | Paper |
| Testing distributions of huge objects | 2024-07-03 | Paper |
| Robustly self-ordered graphs: constructions and applications to property testing | 2024-06-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6126235 | 2024-04-09 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6126319 | 2024-04-09 | Paper |
| A lower bound on the complexity of testing grained distributions | 2023-12-02 | Paper |
| Good permutation codes based on the shuffle-exchange network | 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 | 2022-11-09 | Paper |
| Pseudo-mixing Time of Random Walks | 2022-08-30 | Paper |
| Deconstructing 1-Local Expanders | 2022-08-30 | Paper |
| On Constructing Expanders for Any Number of Vertices | 2022-08-30 | Paper |
| Flexible Models for Testing Graph Properties | 2022-08-30 | Paper |
| Reducing Testing Affine Spaces to Testing Linearity of Functions | 2022-08-30 | Paper |
| A Probabilistic Error-Correcting Scheme that Provides Partial Secrecy | 2022-08-30 | Paper |
| Bridging a Small Gap in the Gap Amplification of Assignment Testers | 2022-08-30 | Paper |
| On the Effect of the Proximity Parameter on Property Testers | 2022-08-30 | Paper |
| On the Relation Between the Relative Earth Mover Distance and the Variation Distance (an Exposition) | 2022-08-30 | Paper |
| The Uniform Distribution Is Complete with Respect to Testing Identity to a Fixed Distribution | 2022-08-30 | Paper |
| On Emulating Interactive Proofs with Public Coins | 2022-08-30 | Paper |
| Worst-Case to Average-Case Reductions for Subclasses of P | 2022-08-30 | Paper |
| On the Optimal Analysis of the Collision Probability Tester (an Exposition) | 2022-08-30 | Paper |
| Constant-Round Interactive Proof Systems for AC0[2] and NC1 | 2022-08-30 | Paper |
| Super-Perfect Zero-Knowledge Proofs | 2022-08-30 | Paper |
| On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions | 2022-08-30 | Paper |
| On (Valiant’s) Polynomial-Size Monotone Formula for Majority | 2022-08-30 | Paper |
| On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions | 2022-08-30 | Paper |
| On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing | 2022-08-30 | Paper |
| Two Comments on Targeted Canonical Derandomizers | 2022-08-30 | Paper |
| Improved bounds on the an-complexity of \(O(1)\)-linear functions | 2022-08-01 | Paper |
| Every Set in P Is Strongly Testable Under a Suitable Encoding | 2022-07-18 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5090414 | 2022-07-18 | Paper |
| The Subgraph Testing Model | 2022-03-07 | Paper |
| A Simple Protocol for Signing Contracts | 2022-01-08 | Paper |
| On the Power of Cascade Ciphers | 2022-01-08 | Paper |
| Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP | 2021-07-22 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4993281 | 2021-06-15 | Paper |
| Cryptography and cryptographic protocols | 2020-12-04 | Paper |
| Testing graphs in vertex-distribution-free models | 2020-01-30 | Paper |
| Hierarchy theorems for testing properties in size-oblivious query complexity | 2019-12-19 | Paper |
| Strong Locally Testable Codes with Relaxed Local Decoders | 2019-12-16 | Paper |
| On Sample-Based Testers | 2019-12-06 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4578332 | 2018-08-08 | Paper |
| Matrix rigidity of random Toeplitz matrices | 2018-08-03 | Paper |
| On Doubly-Efficient Interactive Proof Systems | 2018-07-02 | Paper |
| Proofs of proximity for context-free languages and read-once branching programs | 2018-06-14 | Paper |
| On Learning and Testing Dynamic Environments | 2018-05-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4601849 | 2018-01-24 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4601820 | 2018-01-24 | Paper |
| Introduction to Property Testing | 2017-10-25 | Paper |
| Matrix rigidity of random toeplitz matrices | 2017-09-29 | Paper |
| On the complexity of global computation in the presence of link failures | 2017-08-21 | Paper |
| On Sample-Based Testers | 2017-05-19 | Paper |
| On the possibilities and limitations of pseudodeterministic algorithms | 2017-05-16 | Paper |
| On the Cryptographic Applications of Random Functions (Extended Abstract) | 2017-04-10 | Paper |
| RSA/Rabin least significant bits are $$ \tfrac{1} {2} + \tfrac{1} {{poly \left( {\log N} \right)}} $$ secure (Extended Abstract) | 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 | 2016-10-24 | Paper |
| Chinese remaindering with errors | 2016-09-29 | Paper |
| Computational complexity and knowledge complexity (extended abstract) | 2016-09-01 | Paper |
| Tiny families of functions with random properties: a quality-size trade-off for hashing (preliminary version) | 2016-09-01 | Paper |
| The graph clustering problem has a perfect zero-knowledge interactive proof | 2016-06-16 | Paper |
| On the complexity of interactive proofs with bounded communication | 2016-06-09 | Paper |
| On universal learning algorithms | 2016-05-26 | Paper |
| Two-sided error proximity oblivious testing | 2016-03-22 | Paper |
| Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs | 2015-10-27 | Paper |
| On derandomizing algorithms that err extremely rarely | 2015-06-26 | Paper |
| Asynchronous secure computation | 2015-05-07 | Paper |
| On proximity oblivious testing | 2015-02-04 | Paper |
| On basing one-way functions on NP-hardness | 2014-11-25 | Paper |
| Finding cycles and trees in sublinear time | 2014-10-16 | Paper |
| Resettable zero-knowledge (extended abstract) | 2014-09-26 | Paper |
| Erratum for: ``On basing one-way functions on NP-hardness | 2014-08-13 | Paper |
| On the (im)possibility of obfuscating programs | 2014-02-17 | Paper |
| A theory of goal-oriented communication | 2014-02-17 | Paper |
| Enhancements of trapdoor permutations | 2013-08-01 | Paper |
| More constructions of lossy and correlation-secure trapdoor functions | 2013-04-15 | Paper |
| Two-Sided Error Proximity Oblivious Testing | 2012-11-02 | Paper |
| Monotone circuits: one-way functions versus pseudorandom generators | 2012-09-27 | Paper |
| The tensor product of two good codes is not necessarily robustly testable | 2012-07-20 | Paper |
| Hierarchy theorems for property testing | 2012-06-26 | Paper |
| On Probabilistic versus Deterministic Provers in the Definition of Proofs of Knowledge | 2011-08-19 | Paper |
| Introduction to Testing Graph Properties | 2011-08-19 | Paper |
| A Sample of Samplers: A Computational Perspective on Sampling | 2011-08-19 | Paper |
| On the Complexity of Computational Problems Regarding Distributions | 2011-08-19 | Paper |
| Candidate One-Way Functions Based on Expander Graphs | 2011-08-19 | Paper |
| Three XOR-Lemmas — An Exposition | 2011-08-19 | Paper |
| On Yao’s XOR-Lemma | 2011-08-19 | Paper |
| In a World of P=BPP | 2011-08-19 | Paper |
| Short Locally Testable Codes and Proofs | 2011-08-19 | Paper |
| Testing Graph Blow-Up | 2011-08-19 | Paper |
| On Testing Expansion in Bounded-Degree Graphs | 2011-08-19 | Paper |
| Basic Facts about Expander Graphs | 2011-08-19 | Paper |
| Simplified Derandomization of BPP Using a Hitting Set Generator | 2011-08-19 | Paper |
| On Security Preserving Reductions – Revised Terminology | 2011-08-19 | Paper |
| Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs | 2011-08-19 | Paper |
| A Brief Introduction to Property Testing | 2011-08-19 | Paper |
| Average Case Complexity, Revisited | 2011-08-19 | Paper |
| Proximity Oblivious Testing and the Role of Invariances | 2011-08-19 | Paper |
| Proving Computational Ability | 2011-08-19 | Paper |
| Strong Proofs of Knowledge | 2011-08-19 | Paper |
| The GGM Construction Does NOT Yield Correlation Intractable Function Ensembles | 2011-08-19 | Paper |
| On the Average-Case Complexity of Property Testing | 2011-08-19 | Paper |
| From Absolute Distinguishability to Positive Distinguishability | 2011-08-19 | Paper |
| Bravely, Moderately: A Common Theme in Four Recent Works | 2011-08-19 | Paper |
| Contemplations on Testing Graph Properties | 2011-08-19 | Paper |
| Another Motivation for Reducing the Randomness Complexity of Algorithms | 2011-08-19 | Paper |
| On Constructing 1-1 One-Way Functions | 2011-08-19 | Paper |
| Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard | 2011-08-19 | Paper |
| Randomness and Computation | 2011-08-19 | Paper |
| Collision-Free Hashing from Lattice Problems | 2011-08-19 | Paper |
| Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More) | 2011-08-19 | Paper |
| A Candidate Counterexample to the Easy Cylinders Conjecture | 2011-08-19 | Paper |
| Notes on Levin’s Theory of Average-Case Complexity | 2011-08-19 | Paper |
| From Logarithmic Advice to Single-Bit Advice | 2011-08-19 | Paper |
| On the Circuit Complexity of Perfect Hashing | 2011-08-19 | Paper |
| Basing Non-Interactive Zero-Knowledge on (Enhanced) Trapdoor Permutations: The State of the Art | 2011-08-19 | Paper |
| Testing Graph Blow-Up | 2011-08-17 | Paper |
| Proximity Oblivious Testing and the Role of Invariances | 2011-08-17 | Paper |
| Algorithmic Aspects of Property Testing in the Dense Graphs Model | 2011-07-29 | Paper |
| On Proximity-Oblivious Testing | 2011-07-29 | Paper |
| On the Implementation of Huge Random Objects | 2011-04-04 | Paper |
| On the randomness complexity of property testing | 2011-02-07 | Paper |
| The random oracle methodology, revisited | 2011-02-01 | Paper |
| P, NP, and NP-Completeness | 2011-01-10 | Paper |
| Introduction to Testing Graph Properties | 2010-10-12 | Paper |
| Hierarchy Theorems for Property Testing | 2010-10-12 | Paper |
| A Brief Introduction to Property Testing | 2010-10-12 | Paper |
| Algorithmic Aspects of Property Testing in the Dense Graphs Model | 2010-10-12 | Paper |
| The Program of the Mini-Workshop | 2010-10-12 | Paper |
| Short Locally Testable Codes and Proofs: A Survey in Two Parts | 2010-10-12 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3588158 | 2010-09-10 | Paper |
| On Testing Computability by Small Width OBDDs | 2010-09-10 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3585016 | 2010-08-31 | Paper |
| Robust pcps of proximity, shorter pcps and applications to coding | 2010-08-15 | Paper |
| Concurrent zero-knowledge with timing, revisited | 2010-08-05 | Paper |
| More Constructions of Lossy and Correlation-Secure Trapdoor Functions | 2010-05-28 | Paper |
| Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques | 2010-05-26 | Paper |
| On expected probabilistic polynomial-time adversaries: a suggestion for restricted definitions and their benefits | 2010-03-01 | Paper |
| Foundations of Cryptography | 2010-01-07 | Paper |
| Universal Arguments and their Applications | 2009-11-06 | Paper |
| Algorithmic Aspects of Property Testing in the Dense Graphs Model | 2009-10-28 | Paper |
| Hierarchy Theorems for Property Testing | 2009-10-28 | Paper |
| Almost \(k\)-wise independence versus \(k\)-wise independence | 2009-07-09 | Paper |
| Theory of Cryptography | 2009-05-14 | Paper |
| On the Randomness Complexity of Property Testing | 2009-02-17 | Paper |
| On Approximating the Average Distance Between Points | 2009-02-17 | Paper |
| Locally testable codes and PCPs of almost-linear length | 2008-12-21 | Paper |
| Probabilistic Proof Systems: A Primer | 2008-10-20 | Paper |
| Foundations of Cryptography – A Primer | 2008-09-01 | Paper |
| Approximating average parameters of graphs | 2008-07-21 | Paper |
| Computational Complexity | 2008-06-30 | Paper |
| Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding | 2007-09-07 | Paper |
| On Expected Probabilistic Polynomial-Time Adversaries: A Suggestion for Restricted Definitions and Their Benefits | 2007-08-30 | Paper |
| Approximating Average Parameters of Graphs | 2007-08-28 | Paper |
| Lower bounds for linear locally decodable codes and private information retrieval | 2007-01-24 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3413440 | 2007-01-05 | Paper |
| Session-key generation using human passwords only | 2006-11-03 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5465361 | 2005-08-22 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4650572 | 2005-02-18 | Paper |
| Property testing and its connection to learning and approximation | 2005-01-25 | Paper |
| Private information retrieval | 2005-01-25 | Paper |
| Foundations of Cryptography | 2004-11-09 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2762124 | 2004-02-08 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4440439 | 2003-12-17 | Paper |
| On interactive proofs with a laconic prover | 2003-11-17 | Paper |
| On the security of modular exponentiation with application to the construction of pseudorandom generators | 2003-08-27 | Paper |
| Three theorems regarding testing graph properties | 2003-08-06 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4552044 | 2003-05-22 | Paper |
| Uniform generation of NP-witnesses using an NP-oracle | 2003-01-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4783716 | 2002-12-08 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4783738 | 2002-12-08 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4542539 | 2002-09-24 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4542514 | 2002-09-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4542558 | 2002-09-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4542547 | 2002-08-01 | Paper |
| Approximating shortest lattice vectors is not harder than approximating closest lattice vectors | 2002-07-25 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4535028 | 2002-06-12 | Paper |
| Foundations of Cryptography | 2002-04-29 | Paper |
| Property testing in bounded degree graphs | 2002-03-07 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2754188 | 2001-11-11 | Paper |
| Testing monotonicity | 2001-06-12 | Paper |
| On the limits of nonapproximability of lattice problems | 2001-05-28 | Paper |
| Learning polynomials with queries: The highly noisy case | 2001-03-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4364542 | 2001-03-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4527008 | 2001-02-28 | Paper |
| Preface (to the special issue on general secure multiparty computation) | 2000-11-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4249327 | 2000-10-17 | Paper |
| Chinese remaindering with errors | 2000-09-07 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4941874 | 2000-08-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4252727 | 2000-04-26 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4231909 | 2000-04-26 | Paper |
| A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem | 2000-03-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4941829 | 2000-03-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4941860 | 2000-03-19 | Paper |
| Computational Sample Complexity | 2000-03-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4940698 | 2000-03-01 | Paper |
| A sublinear bipartiteness tester for bounded degree graphs | 2000-02-21 | Paper |
| Computational indistinguishability: A sample hierarchy | 2000-01-17 | Paper |
| Efficient approximation of product distributions | 1999-12-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4258568 | 1999-09-13 | Paper |
| Quantifying knowledge complexity | 1999-09-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4252714 | 1999-08-31 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4234050 | 1999-07-26 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4228521 | 1999-03-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4230365 | 1999-03-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4224925 | 1999-01-17 | Paper |
| Modern cryptography, probabilistic proofs and pseudo-randomness | 1999-01-06 | Paper |
| Computational Complexity and Knowledge Complexity | 1998-09-20 | Paper |
| Computational indistinguishability: algorithms vs. circuits | 1998-08-13 | Paper |
| Tiny families of functions with random properties: A quality-size trade-off for hashing | 1998-07-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4364546 | 1998-06-25 | Paper |
| Free Bits, PCPs, and Nonapproximability---Towards Tight Results | 1998-05-10 | Paper |
| Fault-tolerant Computation in the Full Information Model | 1998-05-10 | Paper |
| Software protection and simulation on oblivious RAMs | 1998-01-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4364545 | 1998-01-07 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4359458 | 1997-10-08 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4343445 | 1997-07-06 | Paper |
| Lower bounds for sampling algorithms for estimating the average | 1997-02-28 | Paper |
| How to construct constant-round zero-knowledge proof systems for NP | 1996-10-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4866089 | 1996-09-15 | Paper |
| On-line/off-line digital signatures | 1996-08-20 | Paper |
| On the Composition of Zero-Knowledge Proof Systems | 1996-07-02 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4318711 | 1995-11-06 | Paper |
| Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems | 1994-11-24 | Paper |
| The random oracle hypothesis is false | 1994-10-13 | Paper |
| On the Existence of Pseudorandom Generators | 1994-09-13 | Paper |
| Definitions and properties of zero-knowledge proof systems | 1994-07-24 | Paper |
| Randomness in interactive proofs | 1994-05-08 | Paper |
| Bounds on tradeoffs between randomness and communication complexity | 1993-10-18 | Paper |
| A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm | 1993-08-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4038698 | 1993-05-18 | Paper |
| A uniform-complexity treatment of encryption and zero-knowledge | 1993-05-16 | Paper |
| Addendum to “simple constructions of almost k-wise independent random variables” | 1993-05-16 | Paper |
| On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization | 1993-01-16 | Paper |
| Simple Constructions of Almost k-wise Independent Random Variables | 1992-10-18 | Paper |
| On the theory of average case complexity | 1992-09-27 | Paper |
| Sparse pseudorandom distributions | 1992-06-28 | Paper |
| Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection | 1991-01-01 | Paper |
| On the complexity of computation in the presence of link failures: The case of a ring | 1991-01-01 | Paper |
| A trade-off between information and communication in broadcast protocols | 1990-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5750398 | 1990-01-01 | Paper |
| An improved parallel algorithm for integer GCD | 1990-01-01 | Paper |
| A note on computational indistinguishability | 1990-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5751836 | 1990-01-01 | Paper |
| On the number of monochromatic close pairs of beads in a rosary | 1990-01-01 | Paper |
| The best of both worlds: Guaranteeing termination in fast randomized Byzantine agreement protocols | 1990-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5750402 | 1990-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5748796 | 1990-01-01 | Paper |
| On the power of two-point based sampling | 1989-01-01 | Paper |
| Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity | 1988-01-01 | Paper |
| RSA and Rabin Functions: Certain Parts are as Hard as the Whole | 1988-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3787498 | 1988-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3816074 | 1988-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3796744 | 1988-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3777937 | 1987-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3775469 | 1987-01-01 | Paper |
| Electing a leader in a ring with link failures | 1987-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3763584 | 1987-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3729902 | 1986-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3731512 | 1986-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3724235 | 1986-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4725777 | 1986-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3743317 | 1985-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3325625 | 1983-01-01 | Paper |
| DES-like functions can generate the alternating group | 1983-01-01 | Paper |
| The minimum-length generator sequence problem is NP-hard | 1981-01-01 | Paper |
