| Publication | Date of Publication | Type |
|---|
scientific article; zbMATH DE number 7788340 (Why is no real title available?)
| 2024-01-15 | Paper |
scientific article; zbMATH DE number 7788365 (Why is no real title available?)
| 2024-01-15 | Paper |
Some recent strong inapproximability results
Algorithm Theory — SWAT'98 | 2022-12-09 | Paper |
Recent results in hardness of approximation
Algorithm Theory — SWAT '94 | 2022-12-09 | Paper |
On Small-depth Frege Proofs for Tseitin for Grids
Journal of the ACM | 2022-12-08 | Paper |
Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound
IEEE Transactions on Information Theory | 2022-02-17 | Paper |
\(d\)-Galvin families
The Electronic Journal of Combinatorics | 2020-02-10 | Paper |
Bounded independence versus symmetric tests
ACM Transactions on Computation Theory | 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
Journal of the ACM | 2018-05-17 | Paper |
Bounded independence vs. moduli
| 2018-04-19 | Paper |
On the hardness of approximating balanced homogenous 3-Lin
Theory of Computing | 2017-10-11 | Paper |
\((2+\varepsilon)\)-Sat is NP-hard
SIAM Journal on Computing | 2017-10-06 | Paper |
On the List-Decodability of Random Linear Codes
IEEE Transactions on Information Theory | 2017-07-27 | Paper |
On the power of many one-bit provers
Proceedings of the 4th conference on Innovations in Theoretical Computer Science | 2017-05-16 | Paper |
An Improved Bound on the Fraction of Correctable Deletions
IEEE Transactions on Information Theory | 2017-05-02 | Paper |
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes
SIAM Journal on Computing | 2017-03-10 | Paper |
The complexity of searching a sorted array of strings
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 | 2016-09-01 | Paper |
On the complexity of interactive proofs with bounded communication
Information Processing Letters | 2016-06-09 | Paper |
The square lattice shuffle, correction
Random Structures \& Algorithms | 2016-02-03 | Paper |
Making the Long Code Shorter
SIAM Journal on Computing | 2015-11-04 | Paper |
Approximating linear threshold predicates
ACM Transactions on Computation Theory | 2015-09-24 | Paper |
On the usefulness of predicates
ACM Transactions on Computation Theory | 2015-09-24 | Paper |
The security of all RSA and discrete log bits
Journal of the ACM | 2015-08-01 | Paper |
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
On the Correlation of Parity and Small-Depth Circuits
SIAM Journal on Computing | 2015-02-09 | Paper |
Randomly supported independence and resistance
Proceedings of the forty-first annual ACM symposium on Theory of computing | 2015-02-04 | Paper |
Towards an optimal separation of space and length in resolution
Theory of Computing | 2014-10-06 | Paper |
Satisfying degree-\(d\) equations over \(\mathrm{GF}[2^n\)]
Theory of Computing | 2014-10-06 | Paper |
On the list-decodability of random linear codes
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
On DNF approximators for monotone Boolean functions
Automata, Languages, and Programming | 2014-07-01 | Paper |
On the NP-hardness of MAX-Not-2
SIAM Journal on Computing | 2014-06-04 | Paper |
Erratum: Polynomial Time Algorithms for Finding Integer Relations Among Real Numbers
SIAM Journal on Computing | 2014-06-04 | Paper |
On the NP-hardness of Max-Not-2
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2012-11-02 | Paper |
Beating the random ordering is hard: every ordering CSP is approximation resistant
SIAM Journal on Computing | 2011-10-18 | Paper |
Satisfying degree-\(d\) equations over \(\mathrm{GF}[2^{n}\)]
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2011-08-17 | Paper |
The randomized communication complexity of set disjointness
Theory of Computing | 2011-05-24 | Paper |
Query efficient PCPs with perfect completeness
Theory of Computing | 2011-05-24 | Paper |
Randomly Supported Independence and Resistance
SIAM Journal on Computing | 2011-05-17 | Paper |
On the approximation resistance of a random predicate
Computational Complexity | 2011-02-18 | Paper |
Approximating linear threshold predicates
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2010-09-10 | Paper |
Every 2-CSP allows nontrivial approximation
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Every 2-CSP allows nontrivial approximation
Computational Complexity | 2010-03-15 | Paper |
An efficient parallel repetition theorem
Theory of Cryptography | 2010-02-24 | Paper |
On the Approximation Resistance of a Random Predicate
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-02-17 | Paper |
scientific article; zbMATH DE number 5485584 (Why is no real title available?)
| 2009-01-05 | Paper |
Practical construction and analysis of pseudo-randomness primitives
Journal of Cryptology | 2008-04-16 | Paper |
Some optimal inapproximability results
Journal of the ACM | 2008-02-11 | Paper |
On the efficient approximability of constraint satisfaction problems
| 2007-10-24 | Paper |
The security of the IAPM and IACBC modes
Journal of Cryptology | 2007-05-03 | Paper |
The square lattice shuffle
Random Structures \& Algorithms | 2007-02-07 | Paper |
scientific article; zbMATH DE number 2212170 (Why is no real title available?)
| 2005-10-05 | Paper |
Advances in Cryptology – CRYPTO 2004
Lecture Notes in Computer Science | 2005-08-23 | Paper |
Combinatorial bounds for list decoding
IEEE Transactions on Information Theory | 2005-05-11 | Paper |
Fitting points on the real line and its application to RH mapping
Journal of Algorithms | 2004-10-01 | Paper |
scientific article; zbMATH DE number 2081080 (Why is no real title available?)
| 2004-08-04 | Paper |
Simple analysis of graph tests for linearity and PCP
Random Structures \& Algorithms | 2003-04-03 | Paper |
A new way of using semidefinite programming with applications to linear equations mod \(p\)
Journal of Algorithms | 2002-12-10 | Paper |
Hardness of Approximate Hypergraph Coloring
SIAM Journal on Computing | 2002-09-29 | Paper |
On bounded occurrence constraint satisfaction
Information Processing Letters | 2002-07-25 | Paper |
A slight sharpening of LMN
Journal of Computer and System Sciences | 2002-07-04 | Paper |
Linear-consistency testing.
Journal of Computer and System Sciences | 2002-07-02 | Paper |
scientific article; zbMATH DE number 1263233 (Why is no real title available?)
| 2002-01-30 | Paper |
A smaller sleeping bag for a baby snake
Discrete \& Computational Geometry | 2002-01-09 | Paper |
On lower bounds for selecting the median
SIAM Journal on Discrete Mathematics | 2001-06-21 | Paper |
Tight bounds for searching a sorted array of strings
SIAM Journal on Computing | 2001-03-19 | Paper |
scientific article; zbMATH DE number 1559516 (Why is no real title available?)
| 2001-02-28 | Paper |
scientific article; zbMATH DE number 1418270 (Why is no real title available?)
| 2000-12-18 | Paper |
Clique is hard to approximate within \(n^{1-\epsilon}\)
Acta Mathematica | 2000-12-06 | Paper |
scientific article; zbMATH DE number 1306876 (Why is no real title available?)
| 2000-04-26 | Paper |
scientific article; zbMATH DE number 1305390 (Why is no real title available?)
| 2000-02-02 | Paper |
scientific article; zbMATH DE number 1305100 (Why is no real title available?)
| 1999-11-08 | Paper |
A Pseudorandom Generator from any One-way Function
SIAM Journal on Computing | 1999-10-28 | Paper |
scientific article; zbMATH DE number 1256714 (Why is no real title available?)
| 1999-10-04 | Paper |
Monotone Circuits for Connectivity Have Depth (log n)2-o(1)
SIAM Journal on Computing | 1998-09-20 | Paper |
On approximating NP-hard optimization problems
Documenta Mathematica | 1998-08-05 | Paper |
The Shrinkage Exponent of de Morgan Formulas is 2
SIAM Journal on Computing | 1998-05-10 | Paper |
Circuit Bottom Fan-in and Computational Power
SIAM Journal on Computing | 1998-05-10 | Paper |
On the shrinkage exponent for read-once formulae
Theoretical Computer Science | 1997-09-29 | Paper |
Linearity testing in characteristic two
IEEE Transactions on Information Theory | 1997-08-07 | Paper |
Analysis of Backoff Protocols for Multiple Access Channels
SIAM Journal on Computing | 1997-03-03 | Paper |
scientific article; zbMATH DE number 857025 (Why is no real title available?)
| 1996-05-09 | Paper |
Top-down lower bounds for depth-three circuits
Computational Complexity | 1996-01-07 | Paper |
On the distribution of multiplicative translates of sets of residues \((\text{mod }p)\)
Journal of Number Theory | 1995-02-13 | Paper |
The random oracle hypothesis is false
Journal of Computer and System Sciences | 1994-10-13 | Paper |
On the Size of Weights for Threshold Gates
SIAM Journal on Discrete Mathematics | 1994-09-26 | Paper |
Optimal depth, very small size circuits for symmetric functions in \(AC^ 0\)
Information and Computation | 1994-08-31 | Paper |
The discrete logarithm modulo a composite hides \(O(n)\) bits
Journal of Computer and System Sciences | 1994-06-30 | Paper |
scientific article; zbMATH DE number 549856 (Why is no real title available?)
| 1994-04-12 | Paper |
A well-characterized approximation problem
Information Processing Letters | 1994-03-13 | Paper |
On average time hierarchies
Information Processing Letters | 1994-02-24 | Paper |
On the power of small-depth threshold circuits
Computational Complexity | 1993-10-10 | Paper |
Majority gates vs. general weighted threshold gates
Computational Complexity | 1993-08-08 | Paper |
Addendum to “simple constructions of almost k-wise independent random variables”
Random Structures \& Algorithms | 1993-05-16 | Paper |
Simple Constructions of Almost k-wise Independent Random Variables
Random Structures \& Algorithms | 1992-10-18 | Paper |
A simple lower bound for monotone clique using a communication game
Information Processing Letters | 1992-09-26 | Paper |
Optimal bounds for decision problems on the CRCW PRAM
Journal of the ACM | 1992-06-25 | Paper |
Statistical zero-knowledge languages can be recognized in two rounds
Journal of Computer and System Sciences | 1991-01-01 | Paper |
Relativized perfect zero knowledge is not BPP
Information and Computation | 1991-01-01 | Paper |
scientific article; zbMATH DE number 4185024 (Why is no real title available?)
| 1990-01-01 | Paper |
Tensor rank is NP-complete
Journal of Algorithms | 1990-01-01 | Paper |
Simultaneously good bases of a lattice and its reciprocal lattice
Mathematische Annalen | 1990-01-01 | Paper |
On the power of interaction
Combinatorica | 1990-01-01 | Paper |
Polynomial Time Algorithms for Finding Integer Relations among Real Numbers
SIAM Journal on Computing | 1989-01-01 | Paper |
Dual vectors and lower bounds for the nearest lattice point problem
Combinatorica | 1988-01-01 | Paper |
Reconstructing Truncated Integer Variables Satisfying Linear Congruences
SIAM Journal on Computing | 1988-01-01 | Paper |
scientific article; zbMATH DE number 4087011 (Why is no real title available?)
| 1988-01-01 | Paper |
Solving Simultaneous Modular Equations of Low Degree
SIAM Journal on Computing | 1988-01-01 | Paper |
Does co-NP have short interactive proofs ?
Information Processing Letters | 1987-01-01 | Paper |
One-way permutations in NC 0
Information Processing Letters | 1987-01-01 | Paper |
scientific article; zbMATH DE number 4035724 (Why is no real title available?)
| 1986-01-01 | Paper |
scientific article; zbMATH DE number 3980478 (Why is no real title available?)
| 1986-01-01 | Paper |
Simultaneous diophantine approximation of rationals by rationals
Journal of Number Theory | 1986-01-01 | Paper |
A logarithmic approximation of linearly-ordered colourings
| N/A | Paper |
