Publication | Date of Publication | Type |
---|
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 |
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 (Valiant’s) Polynomial-Size Monotone Formula for Majority | 2022-08-30 | Paper |
Two Comments on Targeted Canonical Derandomizers | 2022-08-30 | Paper |
On the Effect of the Proximity Parameter on Property Testers | 2022-08-30 | Paper |
On the Size of Depth-Three 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 |
Super-Perfect Zero-Knowledge Proofs | 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 |
Reducing Testing Affine Spaces to Testing Linearity of Functions | 2022-08-30 | Paper |
Deconstructing 1-Local Expanders | 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 |
On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions | 2022-08-30 | Paper |
Constant-Round Interactive Proof Systems for AC0[2 and NC1] | 2022-08-30 | Paper |
Flexible Models for Testing Graph Properties | 2022-08-30 | Paper |
Pseudo-mixing Time of Random Walks | 2022-08-30 | Paper |
On Constructing Expanders for Any Number of Vertices | 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 |
On the Power of Cascade Ciphers | 2022-01-08 | Paper |
A Simple Protocol for Signing Contracts | 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/Q4601820 | 2018-01-24 | Paper |
https://portal.mardi4nfdi.de/entity/Q4601849 | 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 (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 | 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 |
https://portal.mardi4nfdi.de/entity/Q2913810 | 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 |
Testing Graph Blow-Up | 2011-08-19 | Paper |
Proximity Oblivious Testing and the Role of Invariances | 2011-08-19 | Paper |
Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard | 2011-08-19 | Paper |
Proving Computational Ability | 2011-08-19 | Paper |
On Constructing 1-1 One-Way Functions | 2011-08-19 | Paper |
On the Circuit Complexity of Perfect Hashing | 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 |
Strong Proofs of Knowledge | 2011-08-19 | Paper |
Simplified Derandomization of BPP Using a Hitting Set Generator | 2011-08-19 | Paper |
On Testing Expansion in Bounded-Degree Graphs | 2011-08-19 | Paper |
Candidate One-Way Functions Based on Expander Graphs | 2011-08-19 | Paper |
Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs | 2011-08-19 | Paper |
The GGM Construction Does NOT Yield Correlation Intractable Function Ensembles | 2011-08-19 | Paper |
From Logarithmic Advice to Single-Bit Advice | 2011-08-19 | Paper |
On Probabilistic versus Deterministic Provers in the Definition of Proofs of Knowledge | 2011-08-19 | Paper |
On the Average-Case Complexity of Property Testing | 2011-08-19 | Paper |
A Candidate Counterexample to the Easy Cylinders Conjecture | 2011-08-19 | Paper |
From Absolute Distinguishability to Positive Distinguishability | 2011-08-19 | Paper |
In a World of P=BPP | 2011-08-19 | Paper |
Notes on Levin’s Theory of Average-Case Complexity | 2011-08-19 | Paper |
Three XOR-Lemmas — An Exposition | 2011-08-19 | Paper |
On Yao’s XOR-Lemma | 2011-08-19 | Paper |
A Sample of Samplers: A Computational Perspective on Sampling | 2011-08-19 | Paper |
Short Locally Testable Codes and Proofs | 2011-08-19 | Paper |
Bravely, Moderately: A Common Theme in Four Recent Works | 2011-08-19 | Paper |
On the Complexity of Computational Problems Regarding Distributions | 2011-08-19 | Paper |
Basing Non-Interactive Zero-Knowledge on (Enhanced) Trapdoor Permutations: The State of the Art | 2011-08-19 | Paper |
Average Case Complexity, Revisited | 2011-08-19 | Paper |
Basic Facts about Expander Graphs | 2011-08-19 | Paper |
A Brief Introduction to Property Testing | 2011-08-19 | Paper |
Introduction to Testing Graph Properties | 2011-08-19 | Paper |
Randomness and Computation | 2011-08-19 | Paper |
On Security Preserving Reductions – Revised Terminology | 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 |
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 |
A Brief Introduction to Property Testing | 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 |
Introduction to Testing Graph Properties | 2010-10-12 | Paper |
Hierarchy Theorems for Property Testing | 2010-10-12 | Paper |
Algorithmic Aspects of Property Testing in the Dense Graphs Model | 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 Approximating the Average Distance Between Points | 2009-02-17 | Paper |
On the Randomness Complexity of Property Testing | 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/Q4231909 | 2000-04-26 | Paper |
https://portal.mardi4nfdi.de/entity/Q4252727 | 2000-04-26 | Paper |
Computational Sample Complexity | 2000-03-19 | 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 |
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 |
Fault-tolerant Computation in the Full Information Model | 1998-05-10 | Paper |
Free Bits, PCPs, and Nonapproximability---Towards Tight Results | 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 |
https://portal.mardi4nfdi.de/entity/Q5748796 | 1990-01-01 | Paper |
https://portal.mardi4nfdi.de/entity/Q5750398 | 1990-01-01 | Paper |
https://portal.mardi4nfdi.de/entity/Q5750402 | 1990-01-01 | Paper |
https://portal.mardi4nfdi.de/entity/Q5751836 | 1990-01-01 | Paper |
An improved parallel algorithm for integer GCD | 1990-01-01 | Paper |
On the number of monochromatic close pairs of beads in a rosary | 1990-01-01 | Paper |
A note on computational indistinguishability | 1990-01-01 | Paper |
The best of both worlds: Guaranteeing termination in fast randomized Byzantine agreement protocols | 1990-01-01 | Paper |
A trade-off between information and communication in broadcast protocols | 1990-01-01 | Paper |
On the power of two-point based sampling | 1989-01-01 | Paper |
https://portal.mardi4nfdi.de/entity/Q3787498 | 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/Q3796744 | 1988-01-01 | Paper |
https://portal.mardi4nfdi.de/entity/Q3816074 | 1988-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/Q3775469 | 1987-01-01 | Paper |
https://portal.mardi4nfdi.de/entity/Q3777937 | 1987-01-01 | Paper |
https://portal.mardi4nfdi.de/entity/Q3724235 | 1986-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/Q4725777 | 1986-01-01 | Paper |
https://portal.mardi4nfdi.de/entity/Q3743317 | 1985-01-01 | Paper |
DES-like functions can generate the alternating group | 1983-01-01 | Paper |
https://portal.mardi4nfdi.de/entity/Q3325625 | 1983-01-01 | Paper |
The minimum-length generator sequence problem is NP-hard | 1981-01-01 | Paper |