Person:1083474

Available identifiers

zbMath Open hastad.johan-tDBLP47/3155WikidataQ92756 ScholiaQ92756MaRDI QIDQ1083474

List of research outcomes

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
Recent results in hardness of approximation	2022-12-09	Paper
Some recent strong inapproximability results	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
https://portal.mardi4nfdi.de/entity/Q4636457	2018-04-19	Paper
https://portal.mardi4nfdi.de/entity/Q5368897	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
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
https://portal.mardi4nfdi.de/entity/Q3191584	2014-10-06	Paper
https://portal.mardi4nfdi.de/entity/Q3191597	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 GF[2 n]	2011-08-17	Paper
https://portal.mardi4nfdi.de/entity/Q3002760	2011-05-24	Paper
https://portal.mardi4nfdi.de/entity/Q3002788	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
https://portal.mardi4nfdi.de/entity/Q5421814	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
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
On the power of interaction	1990-01-01	Paper
Simultaneously good bases of a lattice and its reciprocal lattice	1990-01-01	Paper
Tensor rank is NP-complete	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
Solving Simultaneous Modular Equations of Low Degree	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
Does co-NP have short interactive proofs ?	1987-01-01	Paper
One-way permutations in NC 0	1987-01-01	Paper
Simultaneous diophantine approximation of rationals by rationals	1986-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q3745271	1986-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q3775466	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 T. Håstad