| Publication | Date of Publication | Type |
|---|
| https://portal.mardi4nfdi.de/entity/Q6147248 | 2024-01-15 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6147276 | 2024-01-15 | Paper |
| Some recent strong inapproximability results | 2022-12-09 | Paper |
| Recent results in hardness of approximation | 2022-12-09 | Paper |
| On Small-depth Frege Proofs for Tseitin for Grids | 2022-12-08 | Paper |
| Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound | 2022-02-17 | Paper |
| \(d\)-Galvin families | 2020-02-10 | Paper |
| Bounded independence versus symmetric tests | 2019-12-16 | Paper |
| Quantum algorithms for computing short discrete logarithms and factoring RSA integers | 2018-09-12 | Paper |
| An average-case depth hierarchy theorem for Boolean circuits | 2018-05-17 | Paper |
| Bounded independence vs. moduli | 2018-04-19 | Paper |
| On the hardness of approximating balanced homogenous 3-Lin | 2017-10-11 | Paper |
| \((2+\varepsilon)\)-Sat is NP-hard | 2017-10-06 | Paper |
| On the List-Decodability of Random Linear Codes | 2017-07-27 | Paper |
| On the power of many one-bit provers | 2017-05-16 | Paper |
| An Improved Bound on the Fraction of Correctable Deletions | 2017-05-02 | Paper |
| Super-polylogarithmic hypergraph coloring hardness via low-degree long codes | 2017-03-10 | Paper |
| The complexity of searching a sorted array of strings | 2016-09-01 | Paper |
| On the complexity of interactive proofs with bounded communication | 2016-06-09 | Paper |
| The square lattice shuffle, correction | 2016-02-03 | Paper |
| Making the Long Code Shorter | 2015-11-04 | Paper |
| Approximating linear threshold predicates | 2015-09-24 | Paper |
| On the usefulness of predicates | 2015-09-24 | Paper |
| The security of all RSA and discrete log bits | 2015-08-01 | Paper |
| Super-polylogarithmic hypergraph coloring hardness via low-degree long codes | 2015-06-26 | Paper |
| On the Correlation of Parity and Small-Depth Circuits | 2015-02-09 | Paper |
| Randomly supported independence and resistance | 2015-02-04 | Paper |
| Towards an optimal separation of space and length in resolution | 2014-10-06 | Paper |
| Satisfying degree-\(d\) equations over \(\mathrm{GF}[2]^n\) | 2014-10-06 | Paper |
| On the list-decodability of random linear codes | 2014-08-13 | Paper |
| On DNF approximators for monotone Boolean functions | 2014-07-01 | Paper |
| On the NP-hardness of MAX-Not-2 | 2014-06-04 | Paper |
| Erratum: Polynomial Time Algorithms for Finding Integer Relations Among Real Numbers | 2014-06-04 | Paper |
| On the NP-hardness of Max-Not-2 | 2012-11-02 | Paper |
| Beating the random ordering is hard: every ordering CSP is approximation resistant | 2011-10-18 | Paper |
| Satisfying degree-\(d\) equations over \(\mathrm{GF}[2]^{n}\) | 2011-08-17 | Paper |
| The randomized communication complexity of set disjointness | 2011-05-24 | Paper |
| Query efficient PCPs with perfect completeness | 2011-05-24 | Paper |
| Randomly Supported Independence and Resistance | 2011-05-17 | Paper |
| On the approximation resistance of a random predicate | 2011-02-18 | Paper |
| Approximating linear threshold predicates | 2010-09-10 | Paper |
| Every 2-CSP allows nontrivial approximation | 2010-08-16 | Paper |
| Every 2-CSP allows nontrivial approximation | 2010-03-15 | Paper |
| An efficient parallel repetition theorem | 2010-02-24 | Paper |
| On the Approximation Resistance of a Random Predicate | 2009-02-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5302095 | 2009-01-05 | Paper |
| Practical construction and analysis of pseudo-randomness primitives | 2008-04-16 | Paper |
| Some optimal inapproximability results | 2008-02-11 | Paper |
| On the efficient approximability of constraint satisfaction problems | 2007-10-24 | Paper |
| The security of the IAPM and IACBC modes | 2007-05-03 | Paper |
| The square lattice shuffle | 2007-02-07 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5694913 | 2005-10-05 | Paper |
| Advances in Cryptology – CRYPTO 2004 | 2005-08-23 | Paper |
| Combinatorial bounds for list decoding | 2005-05-11 | Paper |
| Fitting points on the real line and its application to RH mapping | 2004-10-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4474190 | 2004-08-04 | Paper |
| Simple analysis of graph tests for linearity and PCP | 2003-04-03 | Paper |
| A new way of using semidefinite programming with applications to linear equations mod \(p\) | 2002-12-10 | Paper |
| Hardness of Approximate Hypergraph Coloring | 2002-09-29 | Paper |
| On bounded occurrence constraint satisfaction | 2002-07-25 | Paper |
| A slight sharpening of LMN | 2002-07-04 | Paper |
| Linear-consistency testing. | 2002-07-02 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4234106 | 2002-01-30 | Paper |
| A smaller sleeping bag for a baby snake | 2002-01-09 | Paper |
| On lower bounds for selecting the median | 2001-06-21 | Paper |
| Tight bounds for searching a sorted array of strings | 2001-03-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4526964 | 2001-02-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4941830 | 2000-12-18 | Paper |
| Clique is hard to approximate within \(n^{1-\epsilon}\) | 2000-12-06 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4252728 | 2000-04-26 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4252269 | 2000-02-02 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4252043 | 1999-11-08 | Paper |
| A Pseudorandom Generator from any One-way Function | 1999-10-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4228449 | 1999-10-04 | Paper |
| Monotone Circuits for Connectivity Have Depth (log n)2-o(1) | 1998-09-20 | Paper |
| On approximating NP-hard optimization problems | 1998-08-05 | Paper |
| The Shrinkage Exponent of de Morgan Formulas is 2 | 1998-05-10 | Paper |
| Circuit Bottom Fan-in and Computational Power | 1998-05-10 | Paper |
| On the shrinkage exponent for read-once formulae | 1997-09-29 | Paper |
| Linearity testing in characteristic two | 1997-08-07 | Paper |
| Analysis of Backoff Protocols for Multiple Access Channels | 1997-03-03 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4870112 | 1996-05-09 | Paper |
| Top-down lower bounds for depth-three circuits | 1996-01-07 | Paper |
| On the distribution of multiplicative translates of sets of residues \((\text{mod }p)\) | 1995-02-13 | Paper |
| The random oracle hypothesis is false | 1994-10-13 | Paper |
| On the Size of Weights for Threshold Gates | 1994-09-26 | Paper |
| Optimal depth, very small size circuits for symmetric functions in \(AC^ 0\) | 1994-08-31 | Paper |
| The discrete logarithm modulo a composite hides \(O(n)\) bits | 1994-06-30 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4287360 | 1994-04-12 | Paper |
| A well-characterized approximation problem | 1994-03-13 | Paper |
| On average time hierarchies | 1994-02-24 | Paper |
| On the power of small-depth threshold circuits | 1993-10-10 | Paper |
| Majority gates vs. general weighted threshold gates | 1993-08-08 | Paper |
| Addendum to “simple constructions of almost k-wise independent random variables” | 1993-05-16 | Paper |
| Simple Constructions of Almost k-wise Independent Random Variables | 1992-10-18 | Paper |
| A simple lower bound for monotone clique using a communication game | 1992-09-26 | Paper |
| Optimal bounds for decision problems on the CRCW PRAM | 1992-06-25 | Paper |
| Statistical zero-knowledge languages can be recognized in two rounds | 1991-01-01 | Paper |
| Relativized perfect zero knowledge is not BPP | 1991-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5750398 | 1990-01-01 | Paper |
| Tensor rank is NP-complete | 1990-01-01 | Paper |
| Simultaneously good bases of a lattice and its reciprocal lattice | 1990-01-01 | Paper |
| On the power of interaction | 1990-01-01 | Paper |
| Polynomial Time Algorithms for Finding Integer Relations among Real Numbers | 1989-01-01 | Paper |
| Dual vectors and lower bounds for the nearest lattice point problem | 1988-01-01 | Paper |
| Reconstructing Truncated Integer Variables Satisfying Linear Congruences | 1988-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3815525 | 1988-01-01 | Paper |
| Solving Simultaneous Modular Equations of Low Degree | 1988-01-01 | Paper |
| Does co-NP have short interactive proofs ? | 1987-01-01 | Paper |
| One-way permutations in NC 0 | 1987-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3775466 | 1986-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3745271 | 1986-01-01 | Paper |
| Simultaneous diophantine approximation of rationals by rationals | 1986-01-01 | Paper |
| A logarithmic approximation of linearly-ordered colourings | N/A | Paper |
