Publications by Johan Håstad
Refereegranskade
Artiklar
[1]
V. Guruswami and J. Håstad, "Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound," IEEE Transactions on Information Theory, vol. 67, no. 10, pp. 6384-6394, 2021.
[2]
J. Håstad, "On Small-depth Frege Proofs for Tseitin for Grids," Journal of the ACM, vol. 68, no. 1, 2021.
[3]
J. Håstad, G. Lagarde and J. Swernofsky, "d-Galvin families," The Electronic Journal of Combinatorics, vol. 27, no. 1, 2020.
[4]
R. Boppana et al., "Bounded Independence versus Symmetric Tests," ACM Transactions on Computation Theory, vol. 11, no. 4, 2019.
[5]
P. Austrin, V. Guruswami and J. Håstad, "(2 + ϵ)-SAT is NP-hard," SIAM journal on computing (Print), vol. 46, no. 5, pp. 1554-1573, 2017.
[6]
B. Bukh, V. Guruswami and J. Håstad, "An Improved Bound on the Fraction of Correctable Deletions," IEEE Transactions on Information Theory, vol. 63, no. 1, pp. 93-103, 2017.
[7]
J. Håstad et al., "An average-case depth hierarchy theorem for boolean circuits," Journal of the ACM, vol. 64, no. 5, 2017.
[8]
J. Håstad et al., "Improved NP-Inapproximability for 2-Variable Linear Equations," Theory of Computing, vol. 13, 2017.
[9]
J. Håstad and R. Manokaran, "On the Hardness of Approximating Balanced Homogeneous 3-Lin," Theory of Computing, vol. 13, 2017.
[10]
V. Guruswami et al., "SUPER-POLYLOGARITHMIC HYPERGRAPH COLORING HARDNESS VIA LOW-DEGREE LONG CODES," SIAM journal on computing (Print), vol. 46, no. 1, pp. 132-159, 2017.
[11]
J. Håstad, "The Square Lattice Shuffle (vol 29, pg 466, 2006)," Random structures & algorithms (Print), vol. 48, no. 1, pp. 213-213, 2016.
[12]
B. Barak et al., "Making the long code shorter," SIAM journal on computing (Print), vol. 44, no. 5, pp. 1287-1324, 2015.
[13]
J. Håstad, "On the correlation of parity and small-depth circuits," SIAM journal on computing (Print), vol. 43, no. 5, pp. 1699-1708, 2014.
[14]
J. Håstad, "On the np-hardness of max-not-2," SIAM journal on computing (Print), vol. 43, no. 1, pp. 179-193, 2014.
[15]
J. Håstad et al., "POLYNOMIAL TIME ALGORITHMS FOR FINDING INTEGER RELATIONS AMONG REAL NUMBERS (vol 18, pg 859, 1989)," SIAM journal on computing (Print), vol. 43, no. 1, pp. 254-254, 2014.
[16]
J. Nordström and J. Håstad, "Towards an optimal separation of space and lenght in resolution," Theory of Computing, vol. 9, pp. 471-557, 2013.
[17]
M. Cheraghchi et al., "Approximating linear threshold predicates," ACM Transactions on Computation Theory, vol. 4, no. 1, pp. 2, 2012.
[18]
P. Austrin and J. Håstad, "On the Usefulness of Predicates," ACM Transactions on Computation Theory, vol. 5, no. 1, 2012.
[19]
V. Guruswami et al., "BEATING THE RANDOM ORDERING IS HARD : EVERY ORDERING CSP IS APPROXIMATION RESISTANT," SIAM journal on computing (Print), vol. 40, no. 3, pp. 878-914, 2011.
[20]
V. Guruswami, J. Håstad and S. Kopparty, "On the List-Decodability of Random Linear Codes," IEEE Transactions on Information Theory, vol. 57, no. 2, pp. 718-725, 2011.
[21]
P. Austrin and J. Håstad, "Randomly supported independence and resistance," SIAM journal on computing (Print), vol. 40, no. 1, pp. 1-27, 2011.
[22]
J. Håstad, "Special issue "conference on computational complexity 2009" guest editor's foreword," Computational Complexity, vol. 19, no. 2, pp. 151-152, 2010.
[23]
J. Håstad, "On the Approximation Resistance of a Random Predicate," Computational Complexity, vol. 18, no. 3, pp. 413-434, 2009.
[24]
J. Håstad, "EVERY 2-CSP ALLOWS NONTRIVIAL APPROXIMATION," Computational Complexity, vol. 17, no. 4, pp. 549-566, 2008.
[25]
J. Håstad and M. Näslund, "Practical construction and analysis of pseudo-randomness primitives," Journal of Cryptology, vol. 21, no. 1, pp. 1-26, 2008.
[26]
J. Håstad, "On the efficient approximability of constraint satisfaction problems," London Mathematical Society Lecture Notes, vol. 346, pp. 201-222, 2007.
[27]
J. Håstad and A. Wigderson, "The randomized communicatin complexity of set disjointness," Theory of Computing, vol. 3, pp. 211-219, 2007.
[28]
J. Håstad, "The security of the IAPM and IACBC modes," Journal of Cryptology, vol. 20, no. 2, pp. 153-163, 2007.
[29]
J. Håstad, "The square lattice shuffle," Random structures & algorithms (Print), vol. 29, no. 4, pp. 466-474, 2006.
[30]
J. Håstad and S. Khot, "Query efficient PCPs with perfect completeness," Theory of Computing, vol. 1, pp. 119-149, 2005.
[31]
J. Håstad and S. Venkatesh, "On the advantage over a random assignment," Random structures & algorithms (Print), vol. 25, no. 2, pp. 117-149, 2004.
[32]
J. Håstad and M. Naslund, "The security of all RSA and discrete log bits," Journal of the ACM, vol. 51, no. 2, pp. 187-230, 2004.
[33]
J. Håstad, L. Ivansson and J. Lagergren, "Fitting points on the real line and its application to RH mapping," Journal of Algorithms, vol. 49, no. 1, pp. 42-62, 2003.
[34]
J. Håstad and A. Wigderson, "Simple analysis of graph tests for linearity and PCP," Random structures & algorithms (Print), vol. 22, no. 2, pp. 139-160, 2003.
[35]
V. Guruswami et al., "Combinatorial bounds for list decoding," IEEE Transactions on Information Theory, vol. 48, no. 5, pp. 1021-1034, 2002.
[36]
V. Guruswami, J. Håstad and M. Sudan, "Hardness of approximate hypergraph coloring," SIAM journal on computing (Print), vol. 31, no. 6, pp. 1663-1686, 2002.
[37]
G. Andersson, L. Engebretsen and J. Håstad, "A new way of using semidefinite programming with applications to linear equations mod p," Journal of Algorithms, vol. 39, no. 2, pp. 162-204, 2001.
[38]
J. Håstad, "A slight sharpening of LMN," Journal of computer and system sciences (Print), vol. 63, no. 3, pp. 498-508, 2001.
[39]
J. Håstad, S. Linusson and J. Wastlund, "A smaller sleeping bag for a baby snake," Discrete & Computational Geometry, vol. 26, no. 1, pp. 173-181, 2001.
[40]
Y. Aumann et al., "Linear-consistency testing," Journal of computer and system sciences (Print), vol. 62, no. 4, pp. 589-607, 2001.
[41]
D. Dor et al., "On lower bounds for selecting the median," SIAM Journal on Discrete Mathematics, vol. 14, no. 3, pp. 299-311, 2001.
[42]
J. Håstad, "Some optimal inapproximability results," Journal of the ACM, vol. 48, no. 4, pp. 798-859, 2001.
[43]
J. Håstad, "On bounded occurrence constraint satisfaction," Information Processing Letters, vol. 74, no. 02-jan, pp. 1-6, 2000.
[44]
A. Andersson et al., "Tight bounds for searching a sorted array of strings," SIAM journal on computing (Print), vol. 30, no. 5, pp. 1552-1578, 2000.
[45]
Konferensbidrag
[46]
J. Håstad, "On small-depth Frege proofs for PHP," in Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023, 2023, pp. 37-49.
[47]
K. Risse and J. Håstad, "On bounded depth proofs for Tseitin formulas on the grid; revisited," in 2022 IEEE 63RD ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2022, pp. 1138-1149.
[48]
V. Guruswami and J. Håstad, "Explicit two-deletion codes with redundancy matching the existential bound," in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2021, pp. 21-32.
[49]
P. Austrin, J. Brown-Cohen and J. Håstad, "Optimal inapproximability with universal factor graphs," in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2021, pp. 434-453.
[50]
J. Håstad, "Knuth Prize Lecture : On the difficulty of approximating boolean max-CSPs," in 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), 2018.
[51]
J. Håstad, "On small-depth Frege proofs for Tseitin for grids," in 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 2017, pp. 97-108.
[52]
M. Ekerå and J. Håstad, "Quantum algorithms for computing short discrete logarithms and factoring RSA integers," in 8th International Workshop on Post-Quantum Cryptography, PQCrypto 2017, 2017, pp. 347-363.
[53]
J. Håstad, "An Average-case Depth Hierarchy Theorem for Higher Depths," in 2016 IEEE 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2016, pp. 79-88.
[54]
R. Boppana et al., "Bounded Independence vs. Moduli," in Leibniz International Proceedings in Informatics, LIPIcs, 2016.
[55]
J. Håstad et al., "Improved NP-inapproximability for 2-variable linear equations," in Leibniz International Proceedings in Informatics, LIPIcs, 2015, pp. 341-360.
[56]
P. Austrin, J. Håstad and V. Guruswami, "(2 + epsilon)-Sat Is NP-hard," in Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2014, pp. 1-10.
[57]
E. Blais et al., "On DNF Approximators for Monotone Boolean Functions," in Automata, Languages, and Programming : 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, 2014, pp. 235-246.
[58]
V. Guruswami et al., "Super-polylogarithmic hypergraph coloring hardness via low-degree long codes," in Proceedings of the Annual ACM Symposium on Theory of Computing, 2014, pp. 614-623.
[59]
P. Austrin, J. Håstad and R. Pass, "On the power of many one-bit provers," in ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science, 2013, pp. 215-220.
[60]
B. Barak et al., "Making the Long Code Shorter," in Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, 2012, pp. 370-379.
[61]
J. Håstad, "On the NP-hardness of Max-Not-2," in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012, pp. 170-181.
[62]
P. Austrin and J. Håstad, "On the usefulness of predicates," in 2012 IEEE 27th Annual Conference On Computational Complexity (CCC), 2012, pp. 53-63.
[63]
[64]
J. Håstad, "Satisfying degree-d equations of GF[2]," in Proceedings of the 14th international workshop and 15th international conference on Approximation, randomization, and combinatorial optimization: : algorithms and techniques, 2011, pp. 242-253.
[65]
J. Håstad et al., "An Efficient Parallel Repetition Theorem," in THEORY OF CRYPTOGRAPHY, PROCEEDINGS, 2010, pp. 1-18.
[66]
M. Cheraghchi et al., "Approximating Linear Threshold Predicates," in 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2010)/14th International Workshop on Randomization and Computation (RANDOM 2010), 2010.
[67]
V. Guruswami, J. Håstad and S. Kopparty, "On the list-decodability of random linear codes," in Proceedings of the Annual ACM Symposium on Theory of Computing, 2010, pp. 409-416.
[68]
P. Austrin and J. Håstad, "Randomly Supported Independence and Resistance," in STOC'09 : PROCEEDINGS OF THE 2009 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2009, pp. 483-492.
[69]
J. Nordström and J. Håstad, "Towards an Optimal Separation of Space and Length in Resolution," in STOC'08 : PROCEEDINGS OF THE 2008 ACM INTERNATIONAL SYMPOSIUM ON THEORY OF COMPUTING, 2008, pp. 701-710.
[70]
J. Håstad, "On Nontrivial Approximation of CSPs," in 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006; Barcelona; Spain; 28-30 August 2006, 2007.
[71]
J. Håstad, "Complexity theory, proofs and approximation," in European Congress of Mathematics, 2005, pp. 733-750.
[72]
J. Håstad, "Every 2-CSP Allows Nontrivial Approximation," in Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005, pp. 740-746.
[73]
Y. Dodis et al., "Randomness extraction and key derivation using the CBC, Cascade and HMAC Modes," in ADVANCES IN CRYPTOLOGY - CRYPTO 2004, PROCEEDINGS, 2004, pp. 494-510.
Icke refereegranskade
Konferensbidrag
[74]
J. Håstad, "On the approximation resistance of a random predicate," in Approximation, Randomization, and Combinatorial Optimization : Algorithms and Techniques, 2007, pp. 149-163.
Senaste synkning med DiVA:
2024-05-05 01:51:12