Johan Håstad

Generating author description...

All published works

Action	Title	Year	Authors
+ PDF Chat	On Small-depth Frege Proofs for PHP	2024	Johan Håstad
+ PDF Chat	On small-depth Frege proofs for PHP	2023	Johan Håstad
+ PDF Chat	On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited	2022	Johan Håstad Kilian Risse
+	On bounded depth proofs for Tseitin formulas on the grid; revisited	2022	Johan Håstad Kilian Risse
+	Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound	2021	Venkatesan Guruswami Johan Håstad
+ PDF Chat	Explicit two-deletion codes with redundancy matching the existential bound	2021	Venkatesan Guruswami Johan Håstad
+ PDF Chat	d-Galvin Families	2020	Johan Håstad Guillaume Lagarde Joseph Swernofsky
+	Explicit two-deletion codes with redundancy matching the existential bound	2020	Venkatesan Guruswami Johan Håstad
+ PDF Chat	Bounded Independence versus Symmetric Tests	2019	Ravi B. Boppana Johan Håstad Chin Ho Lee Emanuele Viola
+	$d$-Galvin families	2019	Johan Håstad Guillaume Lagarde Joseph Swernofsky
+	$d$-Galvin families	2019	Johan Håstad Guillaume Lagarde Joseph Swernofsky
+ PDF Chat	An Average-Case Depth Hierarchy Theorem for Boolean Circuits	2017	Johan Håstad Benjamin Rossman Rocco A. Servedio Li-Yang Tan
+	Quantum algorithms for computing short discrete logarithms and factoring RSA integers	2017	Martin Ekerå Johan Håstad
+ PDF Chat	Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers	2017	Martin Ekerå Johan Håstad
+	Quantum algorithms for computing short discrete logarithms and factoring RSA integers	2017	Martin Ekerå Johan Håstad
+	An Improved Bound on the Fraction of Correctable Deletions	2016	Boris Bukh Venkatesan Guruswami Johan Håstad
+	Bounded Independence vs. Moduli	2016	Ravi B. Boppana Johan Håstad Chin Ho Lee Emanuele Viola
+	An improved bound on the fraction of correctable deletions	2015	Boris Bukh Venkatesan Guruswami Johan Håstad
+	An improved bound on the fraction of correctable deletions	2015	Boris Bukh Venkatesan Guruswami Johan Håstad
+ PDF Chat	Super-polylogarithmic hypergraph coloring hardness via low-degree long codes	2014	Venkatesan Guruswami Prahladh Harsha Johan Håstad Srikanth Srinivasan Girish Varma
+	On the Power of Many One-Bit Provers	2013	Per Austrin Johan Håstad Rafael Pass
+ PDF Chat	On the power of many one-bit provers	2013	Per Austrin Johan Håstad Rafael Pass
+	Super-polylogarithmic hypergraph coloring hardness via low-degree long codes.	2013	Venkatesan Guruswami Prahladh Harsha Johan Håstad Srikanth Srinivasan Girish Varma
+	On the Power of Many One-Bit Provers	2013	Per Austrin Johan Håstad Rafael Pass
+	Making the Long Code Shorter	2012	Boaz Barak Parikshit Gopalan Johan Håstad Raghu Meka Prasad Raghavendra David Steurer
+	On the Usefulness of Predicates	2012	Per Austrin Johan Håstad
+	On the correlation of parity and small-depth circuits.	2012	Johan Håstad
+	On the Usefulness of Predicates	2012	Per Austrin Johan Håstad
+	Making the long code shorter, with applications to the Unique Games Conjecture	2011	Boaz Barak Parikshit Gopalan Johan Håstad Raghu Meka Prasad Raghavendra David Steurer
+ PDF Chat	On the List-Decodability of Random Linear Codes	2011	Venkatesan Guruswami Johan Håstad Swastik Kopparty
+	Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant.	2011	Venkatesan Guruswami Johan Håstad Rajsekar Manokaran Prasad Raghavendra Moses Charikar
+	Making the long code shorter, with applications to the Unique Games Conjecture	2011	Boaz Barak Parikshit Gopalan Johan Håstad Raghu Meka Prasad Raghavendra David Steurer
+ PDF Chat	Randomly Supported Independence and Resistance	2011	Per Austrin Johan Håstad
+ PDF Chat	On the list-decodability of random linear codes	2010	Venkatesan Guruswami Johan Håstad Swastik Kopparty
+	On the List-Decodability of Random Linear Codes	2010	Venkatesan Guruswami Johan Håstad Swastik Kopparty
+	On the List-Decodability of Random Linear Codes	2010	Venkatesan Guruswami Johan Håstad Swastik Kopparty
+	On the Approximation Resistance of a Random Predicate	2009	Johan Håstad
+	Every 2-csp Allows Nontrivial Approximation	2008	Johan Håstad
+ PDF Chat	Towards an optimal separation of space and length in resolution	2008	Jakob Nordström Johan Håstad
+	Towards an Optimal Separation of Space and Length in Resolution	2008	Jakob Nordström Johan Håstad
+	On the Approximation Resistance of a Random Predicate	2007	Johan Håstad
+	The square lattice shuffle	2006	Johan Håstad
+	Inapproximability - some history and some open problems	2004	Johan Håstad
+	The shrinkage exponent is 2	2002	Johan Håstad
+	On the advantage over a random assignment	2002	Johan Håstad S. Venkatesh
+	A New Way of Using Semidefinite Programming with Applications to Linear Equations mod p	2001	Gunnar Andersson Lars Engebretsen Johan Håstad
+ PDF Chat	A Smaller Sleeping Bag for a Baby Snake	2001	Johan Håstad Svante Linusson Johan Wästlund
+	A new way to use semidefinite programming with applications to linear equations mod p	1999	Gunnar Andersson Lars Engebretsen Johan Håstad
+	On the shrinkage exponent for read-once formulae	1995	Johan Håstad Alexander Razborov Andrew Chi-Chih Yao
+	On the Distribution of Multiplicative Translates of Sets of Residues (mod p)	1994	Johan Håstad Jeffrey C. Lagarias Andrew Odlyzko
+ PDF Chat	Simple Constructions of Almost k‐wise Independent Random Variables	1992	Noga Alon Oded Goldreich Johan Håstad René Peralta
+	Tensor rank is NP-complete	1990	Johan Håstad
+	Simultaneously good bases of a lattice and its reciprocal lattice	1990	Johan Håstad Jeffrey C. Lagarias
+	Tensor rank is NP-complete	1989	Johan Håstad
+ PDF Chat	Dual vectors and lower bounds for the nearest lattice point problem	1988	Johan Håstad
+	Optimal bounds for decision problems on the CRCW PRAM	1987	Paul Beame Johan Håstad
+	Simultaneous Diophantine approximation of rationals by rationals	1986	Jeffrey C. Lagarias Johan Håstad
+	The Bit Extraction Problem of t-Resilient Functions (Preliminary Version)	1985	Benny Chor Oded Goldreich Johan Håstad Joel Friedman Steven Rudich Roman Smolensky

Common Coauthors

Coauthor	Papers Together
Venkatesan Guruswami	13
Per Austrin	6
Prasad Raghavendra	4
Swastik Kopparty	4
Raghu Meka	3
Jeffrey C. Lagarias	3
Rafael Pass	3
Boaz Barak	3
Guillaume Lagarde	3
David Steurer	3
Boris Bukh	3
Joseph Swernofsky	3
Parikshit Gopalan	3
Martin Ekerå	3
Jakob Nordström	2
Oded Goldreich	2
Chin Ho Lee	2
Prahladh Harsha	2
Srikanth Srinivasan	2
Lars Engebretsen	2
Ravi B. Boppana	2
Emanuele Viola	2
Kilian Risse	2
Gunnar Andersson	2
Girish Varma	2
Benny Chor	1
Li-Yang Tan	1
Steven Rudich	1
Joel Friedman	1
Rajsekar Manokaran	1
Moses Charikar	1
Alexander Razborov	1
Andrew Chi-Chih Yao	1
S. Venkatesh	1
Rocco A. Servedio	1
Noga Alon	1
Benjamin Rossman	1
Johan Wästlund	1
Roman Smolensky	1
Paul Beame	1
Andrew Odlyzko	1
René Peralta	1
Svante Linusson	1

Commonly Cited References

Action	Title	Year	Authors	# of times referenced
+ PDF Chat	Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming	1995	Michel X. Goemans David P. Williamson	5
+ PDF Chat	Approximation Resistant Predicates from Pairwise Independence	2009	Per Austrin Elchanan Mossel	4
+ PDF Chat	Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer	1997	Peter W. Shor	3
+	Lower Bound for the Linear Multiple Packing of the Binary Hamming Space	2000	Volodia Blinovsky	3
+	Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization	1995	Farid Alizadeh	3
+ PDF Chat	Polylogarithmic independence fools <i>AC</i> <sup>0</sup> circuits	2008	Mark Braverman	3
+	An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle	1995	Jan Krajı́ček Pavel Pudlák Alan R. Woods	3
+	On the convexity of one coding-theory function	2008	Vladimir Blinovsky	3
+ PDF Chat	Factoring polynomials with rational coefficients	1982	A. K. Lenstra H. W. Lenstra László Lovász	3
+	Deletion Codes in the High-Noise and High-Rate Regimes	2017	Venkatesan Guruswami Carol Wang	2
+ PDF Chat	An Average-Case Depth Hierarchy Theorem for Boolean Circuits	2015	Benjamin Rossman Rocco A. Servedio Li-Yang Tan	2
+	Efficient Low-Redundancy Codes for Correcting Multiple Deletions	2017	Joshua Brakensiek Venkatesan Guruswami Samuel Zbarsky	2
+	Balancing sets of vectors	2009	Gábor Hegedüs	2
+	The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer	1999	Michele Mosca Artur Ekert	2
+ PDF Chat	Codes Correcting Two Deletions	2018	Ryan Gabrys Frédéric Sala	2
+ PDF Chat	Deterministic Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors	2018	Kuan Cheng Zhengzhong Jin Xin Li Ke Wu	2
+ PDF Chat	Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate	2010	Venkatesan Guruswami Adam Smith	2
+	Explicit Capacity-achieving Codes for Worst-Case Additive Errors	2009	Venkatesan Guruswami Adam Smith	2
+ PDF Chat	Fooling Functions of Halfspaces under Product Distributions	2010	Parikshit Gopalan Ryan O’Donnell Yi Wu David Zuckerman	2
+	Introduction to Approximation Theory	1969	T. J. Rivlin E. W. Cheney	2
+	Maximizing Quadratic Programs: Extending Grothendieck's Inequality	2004	Moses Charikar Anthony Wirth	2
+	Expected length of the longest common subsequence for large alphabets	2004	Marcos Kiwi Martin Loebl Jiřı́ Matoušek	2
+	A New Proof of Szemer�di's Theorem for Arithmetic Progressions of Length Four	1998	W. T. Gowers	2
+ PDF Chat	None	2007	Michael Alekhnovich Jan Johannsen Toniann Pitassi Alasdair Urquhart	2
+	On the density of families of sets	1972	N. Sauer	2
+	Coordinate density of sets of vectors	1978	Mark G. Karpovsky Vitali Milman	2
+	The asymptotic spectrum of tensors.	1988	Volker Strassen	2
+	Noise stability of functions with low influences: invariance and optimality	2005	Elchanan Mossel Ryan O’Donnell Krzysztof Oleszkiewicz	2
+ PDF Chat	Gaussian Bounds for Noise Correlation of Functions	2010	Elchanan Mossel	2
+ PDF Chat	Gowers uniformity, influence of variables, and PCPs	2006	Alex Samorodnitsky Luca Trevisan	2
+	Efficient Deterministic Single Round Document Exchange for Edit Distance	2015	Djamal Belazzougui	2
+	Rank and optimal computation of generic tensors	1983	Volker Strassen	2
+	A simple parallel algorithm for the maximal independent set problem	1985	Michael Luby	2
+	An Introduction to the Geometry of Numbers	1959	J. W. S. Cassels	2
+ PDF Chat	Longest Common Subsequences in Sets of Words	2014	Boris Bukh Jie Ma	2
+	On the algorithmic complexity of associative algebras	1981	Alfredo C. Alder Volker Strassen	2
+ PDF Chat	A tight bound for black and white pebbles on the pyramid	1985	Maria Klawe	2
+	Matrix multiplication via arithmetic progressions	1987	Don Coppersmith S. Winograd	2
+ PDF Chat	A Simple Proof of Bazzi’s Theorem	2009	Alexander Razborov	2
+	On Lovász’ lattice reduction and the nearest lattice point problem	1986	László Babai	2
+	On the complexity of computing bilinear forms with {0, 1} constants	1980	Teofilo F. Gonzalez Joseph F. JáJá	2
+ PDF Chat	Optimal Testing of Reed-Muller Codes	2010	Arnab Bhattacharyya Swastik Kopparty Grant Schoenebeck Madhu Sudan David Zuckerman	2
+ PDF Chat	A PCP Characterization of AM	2011	Andrew Drucker	2
+ PDF Chat	A combinatorial problem; stability and order for models and theories in infinitary languages	1972	Saharon Shelah	2
+	The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number	2011	Venkatesan Guruswami Ali Kemal Sinop	2
+ PDF Chat	Rounding Semidefinite Programming Hierarchies via Global Correlation	2011	Boaz Barak Prasad Raghavendra David Steurer	2
+	A fast and simple randomized parallel algorithm for the maximal independent set problem	1986	Noga Alon László Babai Alon Itai	2
+	A new proof of Szemerédi's theorem	2001	W. T. Gowers	2
+	Lower Bounds for Space in Resolution	1999	Jacobo Torán	2
+	Linear and nonlinear programming.	1986		2