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