| 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 |
| 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 |
| Pseudo-mixing Time of Random Walks | 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 |
| The subgraph testing model | 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 |
| Simple doubly-efficient interactive proof systems for locally-characterizable sets | 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 |
| Universal locally testable codes | 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 |
| 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 | 2017-09-29 | Paper |
| On the complexity of global computation in the presence of link failures: the case of uni-directional faults | 2017-08-21 | Paper |
| On Sample-Based Testers | 2017-05-19 | Paper |
| On the possibilities and limitations of pseudodeterministic algorithms | 2017-05-16 | 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 the Cryptographic Applications of Random Functions (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 (extended abstract) | 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 |
| 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 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 \(\mathrm{P}=\mathrm{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 |
| 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. The basics of computational complexity. | 2011-01-10 | 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 |
| Introduction to testing graph properties | 2010-10-12 | Paper |
| Hierarchy theorems for property testing | 2010-10-12 | Paper |
| Short locally testable codes and proofs: a survey in two parts | 2010-10-12 | Paper |
| Pseudorandomness | 2010-09-10 | Paper |
| On testing computability by small width OBDDs | 2010-09-10 | Paper |
| A primer on pseudorandom generators | 2010-08-31 | Paper |
| Robust PSPs of proximity, shorter PSPs 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 |
| Bounds on \(2\)-query codeword testing | 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 |
| https://portal.mardi4nfdi.de/entity/Q3816074 | 1988-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/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 |
