Johan Hastad

zbMath Openhastad.johan-tDBLP47/3155WikidataQ92756 ScholiaQ92756MaRDI QIDQ1083474

List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

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

Research outcomes over time

This page was built for person: Johan Hastad