Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDBibTeX records: Johan Håstad
@article{DBLP:journals/corr/abs-2401-15683,
author = {Johan H{\aa}stad},
title = {On Small-depth Frege Proofs for {PHP}},
journal = {CoRR},
volume = {abs/2401.15683},
year = {2024},
url = {https://doi.org/10.48550/arXiv.2401.15683},
doi = {10.48550/ARXIV.2401.15683},
eprinttype = {arXiv},
eprint = {2401.15683},
timestamp = {Tue, 06 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2401-15683.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eatcs/Hastad23,
author = {Johan H{\aa}stad},
title = {The {EATCS} Award 2023 - Laudatio for Amos Fiat},
journal = {Bull. {EATCS}},
volume = {140},
year = {2023},
url = {http://eatcs.org/beatcs/index.php/beatcs/article/view/776},
timestamp = {Thu, 01 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/eatcs/Hastad23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Hastad23,
author = {Johan H{\aa}stad},
title = {On small-depth Frege proofs for {PHP}},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {37--49},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00010},
doi = {10.1109/FOCS57990.2023.00010},
timestamp = {Tue, 02 Jan 2024 14:56:14 +0100},
biburl = {https://dblp.org/rec/conf/focs/Hastad23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Hastad23,
author = {Johan H{\aa}stad},
title = {On small-depth Frege proofs for {PHP}},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR23-042}},
year = {2023},
url = {https://eccc.weizmann.ac.il/report/2023/042},
eprinttype = {ECCC},
eprint = {TR23-042},
timestamp = {Tue, 13 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Hastad23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eatcs/Hastad22,
author = {Johan H{\aa}stad},
title = {The {EATCS} Award 2023 - Call for Nominations},
journal = {Bull. {EATCS}},
volume = {138},
year = {2022},
url = {http://eatcs.org/beatcs/index.php/beatcs/article/view/741},
timestamp = {Wed, 31 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/eatcs/Hastad22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/HastadR22,
author = {Johan H{\aa}stad and
Kilian Risse},
title = {On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited},
booktitle = {63rd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2022, Denver, CO, USA, October 31 - November 3, 2022},
pages = {1138--1149},
publisher = {{IEEE}},
year = {2022},
url = {https://doi.org/10.1109/FOCS54457.2022.00110},
doi = {10.1109/FOCS54457.2022.00110},
timestamp = {Sat, 31 Dec 2022 17:14:50 +0100},
biburl = {https://dblp.org/rec/conf/focs/HastadR22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2209-05839,
author = {Johan H{\aa}stad and
Kilian Risse},
title = {On bounded depth proofs for Tseitin formulas on the grid; revisited},
journal = {CoRR},
volume = {abs/2209.05839},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2209.05839},
doi = {10.48550/ARXIV.2209.05839},
eprinttype = {arXiv},
eprint = {2209.05839},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2209-05839.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/Hastad21,
author = {Johan H{\aa}stad},
title = {On Small-depth Frege Proofs for Tseitin for Grids},
journal = {J. {ACM}},
volume = {68},
number = {1},
pages = {1:1--1:31},
year = {2021},
url = {https://doi.org/10.1145/3425606},
doi = {10.1145/3425606},
timestamp = {Mon, 28 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jacm/Hastad21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tit/GuruswamiH21,
author = {Venkatesan Guruswami and
Johan H{\aa}stad},
title = {Explicit Two-Deletion Codes With Redundancy Matching the Existential
Bound},
journal = {{IEEE} Trans. Inf. Theory},
volume = {67},
number = {10},
pages = {6384--6394},
year = {2021},
url = {https://doi.org/10.1109/TIT.2021.3069446},
doi = {10.1109/TIT.2021.3069446},
timestamp = {Wed, 15 Dec 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tit/GuruswamiH21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/GuruswamiH21,
author = {Venkatesan Guruswami and
Johan H{\aa}stad},
editor = {D{\'{a}}niel Marx},
title = {Explicit two-deletion codes with redundancy matching the existential
bound},
booktitle = {Proceedings of the 2021 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2021, Virtual Conference, January 10 - 13, 2021},
pages = {21--32},
publisher = {{SIAM}},
year = {2021},
url = {https://doi.org/10.1137/1.9781611976465.2},
doi = {10.1137/1.9781611976465.2},
timestamp = {Thu, 15 Jul 2021 13:48:55 +0200},
biburl = {https://dblp.org/rec/conf/soda/GuruswamiH21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/AustrinBH21,
author = {Per Austrin and
Jonah Brown{-}Cohen and
Johan H{\aa}stad},
editor = {D{\'{a}}niel Marx},
title = {Optimal Inapproximability with Universal Factor Graphs},
booktitle = {Proceedings of the 2021 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2021, Virtual Conference, January 10 - 13, 2021},
pages = {434--453},
publisher = {{SIAM}},
year = {2021},
url = {https://doi.org/10.1137/1.9781611976465.27},
doi = {10.1137/1.9781611976465.27},
timestamp = {Thu, 15 Jul 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/AustrinBH21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/combinatorics/HastadLS20,
author = {Johan H{\aa}stad and
Guillaume Lagarde and
Joseph Swernofsky},
title = {d-Galvin Families},
journal = {Electron. J. Comb.},
volume = {27},
number = {1},
pages = {1},
year = {2020},
url = {https://doi.org/10.37236/8432},
doi = {10.37236/8432},
timestamp = {Fri, 10 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/combinatorics/HastadLS20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eatcs/KwiatkowskaTH20,
author = {Marta Kwiatkowska and
{\'{E}}va Tardos and
Johan H{\aa}stad},
title = {The {EATCS} Award 2021 - Call for Nominations},
journal = {Bull. {EATCS}},
volume = {132},
year = {2020},
url = {http://eatcs.org/beatcs/index.php/beatcs/article/view/637},
timestamp = {Wed, 10 Mar 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/eatcs/KwiatkowskaTH20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2007-10592,
author = {Venkatesan Guruswami and
Johan H{\aa}stad},
title = {Explicit two-deletion codes with redundancy matching the existential
bound},
journal = {CoRR},
volume = {abs/2007.10592},
year = {2020},
url = {https://arxiv.org/abs/2007.10592},
eprinttype = {arXiv},
eprint = {2007.10592},
timestamp = {Tue, 28 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2007-10592.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toct/BoppanaHLV19,
author = {Ravi B. Boppana and
Johan H{\aa}stad and
Chin Ho Lee and
Emanuele Viola},
title = {Bounded Independence versus Symmetric Tests},
journal = {{ACM} Trans. Comput. Theory},
volume = {11},
number = {4},
pages = {21:1--21:27},
year = {2019},
url = {https://doi.org/10.1145/3337783},
doi = {10.1145/3337783},
timestamp = {Mon, 08 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toct/BoppanaHLV19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@incollection{DBLP:books/acm/19/Hastad19,
author = {Johan H{\aa}stad},
editor = {Oded Goldreich},
title = {Following a tangent of proofs},
booktitle = {Providing Sound Foundations for Cryptography: On the Work of Shafi
Goldwasser and Silvio Micali},
pages = {599--622},
publisher = {{ACM}},
year = {2019},
url = {https://doi.org/10.1145/3335741.3335764},
doi = {10.1145/3335741.3335764},
timestamp = {Tue, 05 Nov 2019 15:40:16 +0100},
biburl = {https://dblp.org/rec/books/acm/19/Hastad19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AustrinBH19,
author = {Per Austrin and
Jonah Brown{-}Cohen and
Johan H{\aa}stad},
title = {Optimal Inapproximability with Universal Factor Graphs},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR19-151}},
year = {2019},
url = {https://eccc.weizmann.ac.il/report/2019/151},
eprinttype = {ECCC},
eprint = {TR19-151},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AustrinBH19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Hastad18,
author = {Johan H{\aa}stad},
editor = {Mikkel Thorup},
title = {Knuth Prize Lecture: On the Difficulty of Approximating Boolean Max-CSPs},
booktitle = {59th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2018, Paris, France, October 7-9, 2018},
pages = {602},
publisher = {{IEEE} Computer Society},
year = {2018},
url = {https://doi.org/10.1109/FOCS.2018.00063},
doi = {10.1109/FOCS.2018.00063},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Hastad18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/HastadRST17,
author = {Johan H{\aa}stad and
Benjamin Rossman and
Rocco A. Servedio and
Li{-}Yang Tan},
title = {An Average-Case Depth Hierarchy Theorem for Boolean Circuits},
journal = {J. {ACM}},
volume = {64},
number = {5},
pages = {35:1--35:27},
year = {2017},
url = {https://doi.org/10.1145/3095799},
doi = {10.1145/3095799},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jacm/HastadRST17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/GuruswamiHHSV17,
author = {Venkatesan Guruswami and
Prahladh Harsha and
Johan H{\aa}stad and
Srikanth Srinivasan and
Girish Varma},
title = {Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree
Long Codes},
journal = {{SIAM} J. Comput.},
volume = {46},
number = {1},
pages = {132--159},
year = {2017},
url = {https://doi.org/10.1137/140995520},
doi = {10.1137/140995520},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/GuruswamiHHSV17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/AustrinGH17,
author = {Per Austrin and
Venkatesan Guruswami and
Johan H{\aa}stad},
title = {(2+{\(\epsilon\)})-Sat Is NP-hard},
journal = {{SIAM} J. Comput.},
volume = {46},
number = {5},
pages = {1554--1573},
year = {2017},
url = {https://doi.org/10.1137/15M1006507},
doi = {10.1137/15M1006507},
timestamp = {Mon, 20 Nov 2017 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/siamcomp/AustrinGH17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tit/BukhGH17,
author = {Boris Bukh and
Venkatesan Guruswami and
Johan H{\aa}stad},
title = {An Improved Bound on the Fraction of Correctable Deletions},
journal = {{IEEE} Trans. Inf. Theory},
volume = {63},
number = {1},
pages = {93--103},
year = {2017},
url = {https://doi.org/10.1109/TIT.2016.2621044},
doi = {10.1109/TIT.2016.2621044},
timestamp = {Tue, 10 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tit/BukhGH17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/HastadHMOW17,
author = {Johan H{\aa}stad and
Sangxia Huang and
Rajsekar Manokaran and
Ryan O'Donnell and
John Wright},
title = {Improved NP-Inapproximability for 2-Variable Linear Equations},
journal = {Theory Comput.},
volume = {13},
number = {1},
pages = {1--51},
year = {2017},
url = {https://doi.org/10.4086/toc.2017.v013a019},
doi = {10.4086/TOC.2017.V013A019},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/HastadHMOW17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/HastadM17,
author = {Johan H{\aa}stad and
Rajsekar Manokaran},
title = {On the Hardness of Approximating Balanced Homogenous 3-Lin},
journal = {Theory Comput.},
volume = {13},
number = {1},
pages = {1--19},
year = {2017},
url = {https://doi.org/10.4086/toc.2017.v013a010},
doi = {10.4086/TOC.2017.V013A010},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/HastadM17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Hastad17,
author = {Johan H{\aa}stad},
editor = {Chris Umans},
title = {On Small-Depth Frege Proofs for Tseitin for Grids},
booktitle = {58th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2017, Berkeley, CA, USA, October 15-17, 2017},
pages = {97--108},
publisher = {{IEEE} Computer Society},
year = {2017},
url = {https://doi.org/10.1109/FOCS.2017.18},
doi = {10.1109/FOCS.2017.18},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Hastad17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/pqcrypto/EkeraH17,
author = {Martin Eker{\aa} and
Johan H{\aa}stad},
editor = {Tanja Lange and
Tsuyoshi Takagi},
title = {Quantum Algorithms for Computing Short Discrete Logarithms and Factoring
{RSA} Integers},
booktitle = {Post-Quantum Cryptography - 8th International Workshop, PQCrypto 2017,
Utrecht, The Netherlands, June 26-28, 2017, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {10346},
pages = {347--363},
publisher = {Springer},
year = {2017},
url = {https://doi.org/10.1007/978-3-319-59879-6\_20},
doi = {10.1007/978-3-319-59879-6\_20},
timestamp = {Tue, 14 May 2019 10:00:42 +0200},
biburl = {https://dblp.org/rec/conf/pqcrypto/EkeraH17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/EkeraH17,
author = {Martin Eker{\aa} and
Johan H{\aa}stad},
title = {Quantum algorithms for computing short discrete logarithms and factoring
{RSA} integers},
journal = {CoRR},
volume = {abs/1702.00249},
year = {2017},
url = {http://arxiv.org/abs/1702.00249},
eprinttype = {arXiv},
eprint = {1702.00249},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/EkeraH17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Hastad17,
author = {Johan H{\aa}stad},
title = {On small-depth Frege proofs for Tseitin for grids},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR17-142}},
year = {2017},
url = {https://eccc.weizmann.ac.il/report/2017/142},
eprinttype = {ECCC},
eprint = {TR17-142},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Hastad17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/iacr/EkeraH17,
author = {Martin Eker{\aa} and
Johan H{\aa}stad},
title = {Quantum algorithms for computing short discrete logarithms and factoring
{RSA} integers},
journal = {{IACR} Cryptol. ePrint Arch.},
pages = {77},
year = {2017},
url = {http://eprint.iacr.org/2017/077},
timestamp = {Mon, 11 May 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/iacr/EkeraH17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/rsa/Hastad16,
author = {Johan H{\aa}stad},
title = {The square lattice shuffle, correction},
journal = {Random Struct. Algorithms},
volume = {48},
number = {1},
pages = {213},
year = {2016},
url = {https://doi.org/10.1002/rsa.20620},
doi = {10.1002/RSA.20620},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/rsa/Hastad16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/BoppanaHLV16,
author = {Ravi B. Boppana and
Johan H{\aa}stad and
Chin Ho Lee and
Emanuele Viola},
editor = {Klaus Jansen and
Claire Mathieu and
Jos{\'{e}} D. P. Rolim and
Chris Umans},
title = {Bounded Independence vs. Moduli},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2016, September 7-9, 2016, Paris,
France},
series = {LIPIcs},
volume = {60},
pages = {24:1--24:9},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2016},
url = {https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.24},
doi = {10.4230/LIPICS.APPROX-RANDOM.2016.24},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/BoppanaHLV16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Hastad16,
author = {Johan H{\aa}stad},
editor = {Irit Dinur},
title = {An Average-Case Depth Hierarchy Theorem for Higher Depth},
booktitle = {{IEEE} 57th Annual Symposium on Foundations of Computer Science, {FOCS}
2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey,
{USA}},
pages = {79--88},
publisher = {{IEEE} Computer Society},
year = {2016},
url = {https://doi.org/10.1109/FOCS.2016.18},
doi = {10.1109/FOCS.2016.18},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Hastad16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BoppanaHLV16,
author = {Ravi B. Boppana and
Johan H{\aa}stad and
Chin Ho Lee and
Emanuele Viola},
title = {Bounded independence vs. moduli},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR16-102}},
year = {2016},
url = {https://eccc.weizmann.ac.il/report/2016/102},
eprinttype = {ECCC},
eprint = {TR16-102},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BoppanaHLV16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Hastad16,
author = {Johan H{\aa}stad},
title = {An average-case depth hierarchy theorem for higher depth},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR16-041}},
year = {2016},
url = {https://eccc.weizmann.ac.il/report/2016/041},
eprinttype = {ECCC},
eprint = {TR16-041},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Hastad16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/BarakGHMRS15,
author = {Boaz Barak and
Parikshit Gopalan and
Johan H{\aa}stad and
Raghu Meka and
Prasad Raghavendra and
David Steurer},
title = {Making the Long Code Shorter},
journal = {{SIAM} J. Comput.},
volume = {44},
number = {5},
pages = {1287--1324},
year = {2015},
url = {https://doi.org/10.1137/130929394},
doi = {10.1137/130929394},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/siamcomp/BarakGHMRS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/HastadHMOW15,
author = {Johan H{\aa}stad and
Sangxia Huang and
Rajsekar Manokaran and
Ryan O'Donnell and
John Wright},
editor = {Naveen Garg and
Klaus Jansen and
Anup Rao and
Jos{\'{e}} D. P. Rolim},
title = {Improved NP-Inapproximability for 2-Variable Linear Equations},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2015, August 24-26, 2015, Princeton,
NJ, {USA}},
series = {LIPIcs},
volume = {40},
pages = {341--360},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2015},
url = {https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.341},
doi = {10.4230/LIPICS.APPROX-RANDOM.2015.341},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/HastadHMOW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/Hastad14,
author = {Johan H{\aa}stad},
title = {On the NP-Hardness of Max-Not-2},
journal = {{SIAM} J. Comput.},
volume = {43},
number = {1},
pages = {179--193},
year = {2014},
url = {https://doi.org/10.1137/120882718},
doi = {10.1137/120882718},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/siamcomp/Hastad14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/HastadJLS14,
author = {Johan H{\aa}stad and
Bettina Just and
J. C. Lagarias and
Claus{-}Peter Schnorr},
title = {Erratum: Polynomial Time Algorithms for Finding Integer Relations
Among Real Numbers},
journal = {{SIAM} J. Comput.},
volume = {43},
number = {1},
pages = {254},
year = {2014},
url = {https://doi.org/10.1137/130947799},
doi = {10.1137/130947799},
timestamp = {Tue, 23 Mar 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/siamcomp/HastadJLS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/Hastad14a,
author = {Johan H{\aa}stad},
title = {On the Correlation of Parity and Small-Depth Circuits},
journal = {{SIAM} J. Comput.},
volume = {43},
number = {5},
pages = {1699--1708},
year = {2014},
url = {https://doi.org/10.1137/120897432},
doi = {10.1137/120897432},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/siamcomp/Hastad14a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AustrinHG14,
author = {Per Austrin and
Johan H{\aa}stad and
Venkatesan Guruswami},
title = {{(2} + epsilon)-Sat Is NP-Hard},
booktitle = {55th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2014, Philadelphia, PA, USA, October 18-21, 2014},
pages = {1--10},
publisher = {{IEEE} Computer Society},
year = {2014},
url = {https://doi.org/10.1109/FOCS.2014.9},
doi = {10.1109/FOCS.2014.9},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AustrinHG14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/BlaisHST14,
author = {Eric Blais and
Johan H{\aa}stad and
Rocco A. Servedio and
Li{-}Yang Tan},
editor = {Javier Esparza and
Pierre Fraigniaud and
Thore Husfeldt and
Elias Koutsoupias},
title = {On {DNF} Approximators for Monotone Boolean Functions},
booktitle = {Automata, Languages, and Programming - 41st International Colloquium,
{ICALP} 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part
{I}},
series = {Lecture Notes in Computer Science},
volume = {8572},
pages = {235--246},
publisher = {Springer},
year = {2014},
url = {https://doi.org/10.1007/978-3-662-43948-7\_20},
doi = {10.1007/978-3-662-43948-7\_20},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/BlaisHST14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GuruswamiHHSV14,
author = {Venkatesan Guruswami and
Prahladh Harsha and
Johan H{\aa}stad and
Srikanth Srinivasan and
Girish Varma},
editor = {David B. Shmoys},
title = {Super-polylogarithmic hypergraph coloring hardness via low-degree
long codes},
booktitle = {Symposium on Theory of Computing, {STOC} 2014, New York, NY, USA,
May 31 - June 03, 2014},
pages = {614--623},
publisher = {{ACM}},
year = {2014},
url = {https://doi.org/10.1145/2591796.2591882},
doi = {10.1145/2591796.2591882},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/GuruswamiHHSV14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/NordstromH13,
author = {Jakob Nordstr{\"{o}}m and
Johan H{\aa}stad},
title = {Towards an Optimal Separation of Space and Length in Resolution},
journal = {Theory Comput.},
volume = {9},
pages = {471--557},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a014},
doi = {10.4086/TOC.2013.V009A014},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/NordstromH13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/Hastad13,
author = {Johan H{\aa}stad},
title = {Satisfying Degree-d Equations over GF[2]\({}^{\mbox{n}}\)},
journal = {Theory Comput.},
volume = {9},
pages = {845--862},
year = {2013},
url = {https://doi.org/10.4086/toc.2013.v009a027},
doi = {10.4086/TOC.2013.V009A027},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/Hastad13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toct/AustrinH13,
author = {Per Austrin and
Johan H{\aa}stad},
title = {On the usefulness of predicates},
journal = {{ACM} Trans. Comput. Theory},
volume = {5},
number = {1},
pages = {1:1--1:24},
year = {2013},
url = {https://doi.org/10.1145/2462896.2462897},
doi = {10.1145/2462896.2462897},
timestamp = {Mon, 08 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toct/AustrinH13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/AustrinHP13,
author = {Per Austrin and
Johan H{\aa}stad and
Rafael Pass},
editor = {Robert D. Kleinberg},
title = {On the power of many one-bit provers},
booktitle = {Innovations in Theoretical Computer Science, {ITCS} '13, Berkeley,
CA, USA, January 9-12, 2013},
pages = {215--220},
publisher = {{ACM}},
year = {2013},
url = {https://doi.org/10.1145/2422436.2422461},
doi = {10.1145/2422436.2422461},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/innovations/AustrinHP13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1301-2729,
author = {Per Austrin and
Johan H{\aa}stad and
Rafael Pass},
title = {On the Power of Many One-Bit Provers},
journal = {CoRR},
volume = {abs/1301.2729},
year = {2013},
url = {http://arxiv.org/abs/1301.2729},
eprinttype = {arXiv},
eprint = {1301.2729},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1301-2729.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/GuruswamiHHSV13,
author = {Venkatesan Guruswami and
Johan H{\aa}stad and
Prahladh Harsha and
Srikanth Srinivasan and
Girish Varma},
title = {Super-polylogarithmic hypergraph coloring hardness via low-degree
long codes},
journal = {CoRR},
volume = {abs/1311.7407},
year = {2013},
url = {http://arxiv.org/abs/1311.7407},
eprinttype = {arXiv},
eprint = {1311.7407},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/GuruswamiHHSV13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AustrinGH13,
author = {Per Austrin and
Venkatesan Guruswami and
Johan H{\aa}stad},
title = {(2+{\(\epsilon\)})-SAT is NP-hard},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR13-159}},
year = {2013},
url = {https://eccc.weizmann.ac.il/report/2013/159},
eprinttype = {ECCC},
eprint = {TR13-159},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AustrinGH13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GuruswamiHHSV13,
author = {Venkatesan Guruswami and
Prahladh Harsha and
Johan H{\aa}stad and
Srikanth Srinivasan and
Girish Varma},
title = {Super-polylogarithmic hypergraph coloring hardness via low-degree
long codes},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR13-167}},
year = {2013},
url = {https://eccc.weizmann.ac.il/report/2013/167},
eprinttype = {ECCC},
eprint = {TR13-167},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GuruswamiHHSV13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toct/CheraghchiHIS12,
author = {Mahdi Cheraghchi and
Johan H{\aa}stad and
Marcus Isaksson and
Ola Svensson},
title = {Approximating Linear Threshold Predicates},
journal = {{ACM} Trans. Comput. Theory},
volume = {4},
number = {1},
pages = {2:1--2:31},
year = {2012},
url = {https://doi.org/10.1145/2141938.2141940},
doi = {10.1145/2141938.2141940},
timestamp = {Mon, 08 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toct/CheraghchiHIS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/Hastad12,
author = {Johan H{\aa}stad},
editor = {Anupam Gupta and
Klaus Jansen and
Jos{\'{e}} D. P. Rolim and
Rocco A. Servedio},
title = {On the NP-Hardness of Max-Not-2},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques - 15th International Workshop, {APPROX} 2012, and 16th
International Workshop, {RANDOM} 2012, Cambridge, MA, USA, August
15-17, 2012. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {7408},
pages = {170--181},
publisher = {Springer},
year = {2012},
url = {https://doi.org/10.1007/978-3-642-32512-0\_15},
doi = {10.1007/978-3-642-32512-0\_15},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/Hastad12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/AustrinH12,
author = {Per Austrin and
Johan H{\aa}stad},
title = {On the Usefulness of Predicates},
booktitle = {Proceedings of the 27th Conference on Computational Complexity, {CCC}
2012, Porto, Portugal, June 26-29, 2012},
pages = {53--63},
publisher = {{IEEE} Computer Society},
year = {2012},
url = {https://doi.org/10.1109/CCC.2012.18},
doi = {10.1109/CCC.2012.18},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/AustrinH12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BarakGHMRS12,
author = {Boaz Barak and
Parikshit Gopalan and
Johan H{\aa}stad and
Raghu Meka and
Prasad Raghavendra and
David Steurer},
title = {Making the Long Code Shorter},
booktitle = {53rd Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2012, New Brunswick, NJ, USA, October 20-23, 2012},
pages = {370--379},
publisher = {{IEEE} Computer Society},
year = {2012},
url = {https://doi.org/10.1109/FOCS.2012.83},
doi = {10.1109/FOCS.2012.83},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BarakGHMRS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1204-5662,
author = {Per Austrin and
Johan H{\aa}stad},
title = {On the Usefulness of Predicates},
journal = {CoRR},
volume = {abs/1204.5662},
year = {2012},
url = {http://arxiv.org/abs/1204.5662},
eprinttype = {arXiv},
eprint = {1204.5662},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1204-5662.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/dagstuhl-reports/HastadKM12,
author = {Johan H{\aa}stad and
Andrei A. Krokhin and
D{\'{a}}niel Marx},
title = {The Constraint Satisfaction Problem: Complexity and Approximability
(Dagstuhl Seminar 12451)},
journal = {Dagstuhl Reports},
volume = {2},
number = {11},
pages = {1--19},
year = {2012},
url = {https://doi.org/10.4230/DagRep.2.11.1},
doi = {10.4230/DAGREP.2.11.1},
timestamp = {Wed, 07 Jun 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/dagstuhl-reports/HastadKM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Hastad12,
author = {Johan H{\aa}stad},
title = {On the correlation of parity and small-depth circuits},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-137}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/137},
eprinttype = {ECCC},
eprint = {TR12-137},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Hastad12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/AustrinH11,
author = {Per Austrin and
Johan H{\aa}stad},
title = {Randomly Supported Independence and Resistance},
journal = {{SIAM} J. Comput.},
volume = {40},
number = {1},
pages = {1--27},
year = {2011},
url = {https://doi.org/10.1137/100783534},
doi = {10.1137/100783534},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/siamcomp/AustrinH11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/GuruswamiHMRC11,
author = {Venkatesan Guruswami and
Johan H{\aa}stad and
Rajsekar Manokaran and
Prasad Raghavendra and
Moses Charikar},
title = {Beating the Random Ordering Is Hard: Every Ordering {CSP} Is Approximation
Resistant},
journal = {{SIAM} J. Comput.},
volume = {40},
number = {3},
pages = {878--914},
year = {2011},
url = {https://doi.org/10.1137/090756144},
doi = {10.1137/090756144},
timestamp = {Sun, 12 Nov 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/siamcomp/GuruswamiHMRC11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tit/GuruswamiHK11,
author = {Venkatesan Guruswami and
Johan H{\aa}stad and
Swastik Kopparty},
title = {On the List-Decodability of Random Linear Codes},
journal = {{IEEE} Trans. Inf. Theory},
volume = {57},
number = {2},
pages = {718--725},
year = {2011},
url = {https://doi.org/10.1109/TIT.2010.2095170},
doi = {10.1109/TIT.2010.2095170},
timestamp = {Tue, 10 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tit/GuruswamiHK11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/Hastad11,
author = {Johan H{\aa}stad},
editor = {Leslie Ann Goldberg and
Klaus Jansen and
R. Ravi and
Jos{\'{e}} D. P. Rolim},
title = {Satisfying Degree-d Equations over {GF[2]} n},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques - 14th International Workshop, {APPROX} 2011, and 15th
International Workshop, {RANDOM} 2011, Princeton, NJ, USA, August
17-19, 2011. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {6845},
pages = {242--253},
publisher = {Springer},
year = {2011},
url = {https://doi.org/10.1007/978-3-642-22935-0\_21},
doi = {10.1007/978-3-642-22935-0\_21},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/Hastad11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1111-0405,
author = {Boaz Barak and
Parikshit Gopalan and
Johan H{\aa}stad and
Raghu Meka and
Prasad Raghavendra and
David Steurer},
title = {Making the long code shorter, with applications to the Unique Games
Conjecture},
journal = {CoRR},
volume = {abs/1111.0405},
year = {2011},
url = {http://arxiv.org/abs/1111.0405},
eprinttype = {arXiv},
eprint = {1111.0405},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1111-0405.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BarakGHMRS11,
author = {Boaz Barak and
Parikshit Gopalan and
Johan H{\aa}stad and
Raghu Meka and
Prasad Raghavendra and
David Steurer},
title = {Making the long code shorter, with applications to the Unique Games
Conjecture},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR11-142}},
year = {2011},
url = {https://eccc.weizmann.ac.il/report/2011/142},
eprinttype = {ECCC},
eprint = {TR11-142},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BarakGHMRS11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GuruswamiHMRC11,
author = {Venkatesan Guruswami and
Johan H{\aa}stad and
Rajsekar Manokaran and
Prasad Raghavendra and
Moses Charikar},
title = {Beating the Random Ordering is Hard: Every ordering {CSP} is approximation
resistant},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR11-027}},
year = {2011},
url = {https://eccc.weizmann.ac.il/report/2011/027},
eprinttype = {ECCC},
eprint = {TR11-027},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GuruswamiHMRC11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/Hastad10,
author = {Johan H{\aa}stad},
title = {Special Issue "Conference on Computational Complexity 2009"
Guest Editor's Foreword},
journal = {Comput. Complex.},
volume = {19},
number = {2},
pages = {151--152},
year = {2010},
url = {https://doi.org/10.1007/s00037-010-0289-x},
doi = {10.1007/S00037-010-0289-X},
timestamp = {Sun, 15 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cc/Hastad10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/CheraghchiHIS10,
author = {Mahdi Cheraghchi and
Johan H{\aa}stad and
Marcus Isaksson and
Ola Svensson},
editor = {Maria J. Serna and
Ronen Shaltiel and
Klaus Jansen and
Jos{\'{e}} D. P. Rolim},
title = {Approximating Linear Threshold Predicates},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, 13th International Workshop, {APPROX} 2010, and 14th
International Workshop, {RANDOM} 2010, Barcelona, Spain, September
1-3, 2010. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {6302},
pages = {110--123},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-15369-3\_9},
doi = {10.1007/978-3-642-15369-3\_9},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/CheraghchiHIS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GuruswamiHK10,
author = {Venkatesan Guruswami and
Johan H{\aa}stad and
Swastik Kopparty},
editor = {Leonard J. Schulman},
title = {On the list-decodability of random linear codes},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {409--416},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806747},
doi = {10.1145/1806689.1806747},
timestamp = {Sun, 02 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/GuruswamiHK10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/tcc/HastadPWP10,
author = {Johan H{\aa}stad and
Rafael Pass and
Douglas Wikstr{\"{o}}m and
Krzysztof Pietrzak},
editor = {Daniele Micciancio},
title = {An Efficient Parallel Repetition Theorem},
booktitle = {Theory of Cryptography, 7th Theory of Cryptography Conference, {TCC}
2010, Zurich, Switzerland, February 9-11, 2010. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {5978},
pages = {1--18},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-11799-2\_1},
doi = {10.1007/978-3-642-11799-2\_1},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/tcc/HastadPWP10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1001-1386,
author = {Venkatesan Guruswami and
Johan H{\aa}stad and
Swastik Kopparty},
title = {On the List-Decodability of Random Linear Codes},
journal = {CoRR},
volume = {abs/1001.1386},
year = {2010},
url = {http://arxiv.org/abs/1001.1386},
eprinttype = {arXiv},
eprint = {1001.1386},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1001-1386.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/CheraghchiHIS10,
author = {Mahdi Cheraghchi and
Johan H{\aa}stad and
Marcus Isaksson and
Ola Svensson},
title = {Approximating Linear Threshold Predicates},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR10-132}},
year = {2010},
url = {https://eccc.weizmann.ac.il/report/2010/132},
eprinttype = {ECCC},
eprint = {TR10-132},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/CheraghchiHIS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GuruswamiHK10,
author = {Venkatesan Guruswami and
Johan H{\aa}stad and
Swastik Kopparty},
title = {On the List-Decodability of Random Linear Codes},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR10-003}},
year = {2010},
url = {https://eccc.weizmann.ac.il/report/2010/003},
eprinttype = {ECCC},
eprint = {TR10-003},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GuruswamiHK10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/Hastad09,
author = {Johan H{\aa}stad},
title = {On the Approximation Resistance of a Random Predicate},
journal = {Comput. Complex.},
volume = {18},
number = {3},
pages = {413--434},
year = {2009},
url = {https://doi.org/10.1007/s00037-009-0262-8},
doi = {10.1007/S00037-009-0262-8},
timestamp = {Sun, 15 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cc/Hastad09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/AustrinH09,
author = {Per Austrin and
Johan H{\aa}stad},
editor = {Michael Mitzenmacher},
title = {Randomly supported independence and resistance},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {483--492},
publisher = {{ACM}},
year = {2009},
url = {https://doi.org/10.1145/1536414.1536481},
doi = {10.1145/1536414.1536481},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/AustrinH09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/Hastad08,
author = {Johan H{\aa}stad},
title = {Every 2-csp Allows Nontrivial Approximation},
journal = {Comput. Complex.},
volume = {17},
number = {4},
pages = {549--566},
year = {2008},
url = {https://doi.org/10.1007/s00037-008-0256-y},
doi = {10.1007/S00037-008-0256-Y},
timestamp = {Sun, 15 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cc/Hastad08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/joc/HastadN08,
author = {Johan H{\aa}stad and
Mats N{\"{a}}slund},
title = {Practical Construction and Analysis of Pseudo-Randomness Primitives},
journal = {J. Cryptol.},
volume = {21},
number = {1},
pages = {1--26},
year = {2008},
url = {https://doi.org/10.1007/s00145-007-9009-3},
doi = {10.1007/S00145-007-9009-3},
timestamp = {Fri, 18 Sep 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/joc/HastadN08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/NordstromH08,
author = {Jakob Nordstr{\"{o}}m and
Johan H{\aa}stad},
editor = {Cynthia Dwork},
title = {Towards an optimal separation of space and length in resolution},
booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing,
Victoria, British Columbia, Canada, May 17-20, 2008},
pages = {701--710},
publisher = {{ACM}},
year = {2008},
url = {https://doi.org/10.1145/1374376.1374478},
doi = {10.1145/1374376.1374478},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/NordstromH08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-0803-0661,
author = {Jakob Nordstr{\"{o}}m and
Johan H{\aa}stad},
title = {Towards an Optimal Separation of Space and Length in Resolution},
journal = {CoRR},
volume = {abs/0803.0661},
year = {2008},
url = {http://arxiv.org/abs/0803.0661},
eprinttype = {arXiv},
eprint = {0803.0661},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0803-0661.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/NordstromH08,
author = {Jakob Nordstr{\"{o}}m and
Johan H{\aa}stad},
title = {Towards an Optimal Separation of Space and Length in Resolution},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR08-026}},
year = {2008},
url = {https://eccc.weizmann.ac.il/eccc-reports/2008/TR08-026/index.html},
eprinttype = {ECCC},
eprint = {TR08-026},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/NordstromH08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/dcg/HastadLW07,
author = {Johan H{\aa}stad and
Svante Linusson and
Johan W{\"{a}}stlund},
title = {A Smaller Sleeping Bag for a Baby Snake},
journal = {Discret. Comput. Geom.},
volume = {38},
number = {1},
pages = {171},
year = {2007},
url = {https://doi.org/10.1007/s00454-007-0381-4},
doi = {10.1007/S00454-007-0381-4},
timestamp = {Thu, 12 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/dcg/HastadLW07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/joc/Hastad07,
author = {Johan H{\aa}stad},
title = {The Security of the {IAPM} and {IACBC} Modes},
journal = {J. Cryptol.},
volume = {20},
number = {2},
pages = {153--163},
year = {2007},
url = {https://doi.org/10.1007/s00145-006-0225-z},
doi = {10.1007/S00145-006-0225-Z},
timestamp = {Fri, 18 Sep 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/joc/Hastad07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/HastadW07,
author = {Johan H{\aa}stad and
Avi Wigderson},
title = {The Randomized Communication Complexity of Set Disjointness},
journal = {Theory Comput.},
volume = {3},
number = {1},
pages = {211--219},
year = {2007},
url = {https://doi.org/10.4086/toc.2007.v003a011},
doi = {10.4086/TOC.2007.V003A011},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/HastadW07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/Hastad07,
author = {Johan H{\aa}stad},
editor = {Moses Charikar and
Klaus Jansen and
Omer Reingold and
Jos{\'{e}} D. P. Rolim},
title = {On the Approximation Resistance of a Random Predicate},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, 10th International Workshop, {APPROX} 2007, and 11th
International Workshop, {RANDOM} 2007, Princeton, NJ, USA, August
20-22, 2007, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4627},
pages = {149--163},
publisher = {Springer},
year = {2007},
url = {https://doi.org/10.1007/978-3-540-74208-1\_11},
doi = {10.1007/978-3-540-74208-1\_11},
timestamp = {Sat, 30 Sep 2023 09:34:32 +0200},
biburl = {https://dblp.org/rec/conf/approx/Hastad07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/rsa/Hastad06,
author = {Johan H{\aa}stad},
title = {The square lattice shuffle},
journal = {Random Struct. Algorithms},
volume = {29},
number = {4},
pages = {466--474},
year = {2006},
url = {https://doi.org/10.1002/rsa.20131},
doi = {10.1002/RSA.20131},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/rsa/Hastad06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/Hastad06,
author = {Johan H{\aa}stad},
editor = {Josep D{\'{\i}}az and
Klaus Jansen and
Jos{\'{e}} D. P. Rolim and
Uri Zwick},
title = {On Nontrivial Approximation of CSPs},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, 9th International Workshop on Approximation Algorithms
for Combinatorial Optimization Problems, {APPROX} 2006 and 10th International
Workshop on Randomization and Computation, {RANDOM} 2006, Barcelona,
Spain, August 28-30 2006, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4110},
pages = {1},
publisher = {Springer},
year = {2006},
url = {https://doi.org/10.1007/11830924\_1},
doi = {10.1007/11830924\_1},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/Hastad06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/HastadK05,
author = {Johan H{\aa}stad and
Subhash Khot},
title = {Query Efficient PCPs with Perfect Completeness},
journal = {Theory Comput.},
volume = {1},
number = {1},
pages = {119--148},
year = {2005},
url = {https://doi.org/10.4086/toc.2005.v001a007},
doi = {10.4086/TOC.2005.V001A007},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/HastadK05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Hastad05,
author = {Johan H{\aa}stad},
editor = {Harold N. Gabow and
Ronald Fagin},
title = {Every 2-CSP allows nontrivial approximation},
booktitle = {Proceedings of the 37th Annual {ACM} Symposium on Theory of Computing,
Baltimore, MD, USA, May 22-24, 2005},
pages = {740--746},
publisher = {{ACM}},
year = {2005},
url = {https://doi.org/10.1145/1060590.1060700},
doi = {10.1145/1060590.1060700},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Hastad05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/HastadN04,
author = {Johan H{\aa}stad and
Mats N{\"{a}}slund},
title = {The security of all {RSA} and discrete log bits},
journal = {J. {ACM}},
volume = {51},
number = {2},
pages = {187--230},
year = {2004},
url = {https://doi.org/10.1145/972639.972642},
doi = {10.1145/972639.972642},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jacm/HastadN04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/rsa/HastadV04,
author = {Johan H{\aa}stad and
Srinivasan Venkatesh},
title = {On the advantage over a random assignment},
journal = {Random Struct. Algorithms},
volume = {25},
number = {2},
pages = {117--149},
year = {2004},
url = {https://doi.org/10.1002/rsa.20031},
doi = {10.1002/RSA.20031},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/rsa/HastadV04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/crypto/DodisGHKR04,
author = {Yevgeniy Dodis and
Rosario Gennaro and
Johan H{\aa}stad and
Hugo Krawczyk and
Tal Rabin},
editor = {Matthew K. Franklin},
title = {Randomness Extraction and Key Derivation Using the CBC, Cascade and
{HMAC} Modes},
booktitle = {Advances in Cryptology - {CRYPTO} 2004, 24th Annual International
CryptologyConference, Santa Barbara, California, USA, August 15-19,
2004, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3152},
pages = {494--510},
publisher = {Springer},
year = {2004},
url = {https://doi.org/10.1007/978-3-540-28628-8\_30},
doi = {10.1007/978-3-540-28628-8\_30},
timestamp = {Tue, 14 May 2019 10:00:48 +0200},
biburl = {https://dblp.org/rec/conf/crypto/DodisGHKR04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jal/HastadIL03,
author = {Johan H{\aa}stad and
Lars Ivansson and
Jens Lagergren},
title = {Fitting points on the real line and its application to {RH} mapping},
journal = {J. Algorithms},
volume = {49},
number = {1},
pages = {42--62},
year = {2003},
url = {https://doi.org/10.1016/S0196-6774(03)00083-X},
doi = {10.1016/S0196-6774(03)00083-X},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jal/HastadIL03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/rsa/HastadW03,
author = {Johan H{\aa}stad and
Avi Wigderson},
title = {Simple analysis of graph tests for linearity and {PCP}},
journal = {Random Struct. Algorithms},
volume = {22},
number = {2},
pages = {139--160},
year = {2003},
url = {https://doi.org/10.1002/rsa.10068},
doi = {10.1002/RSA.10068},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/rsa/HastadW03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/Hastad03,
author = {Johan H{\aa}stad},
title = {Inapproximability Some history and some open problems},
booktitle = {18th Annual {IEEE} Conference on Computational Complexity (Complexity
2003), 7-10 July 2003, Aarhus, Denmark},
pages = {265},
publisher = {{IEEE} Computer Society},
year = {2003},
url = {https://doi.org/10.1109/CCC.2003.1214426},
doi = {10.1109/CCC.2003.1214426},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/Hastad03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/GuruswamiHS02,
author = {Venkatesan Guruswami and
Johan H{\aa}stad and
Madhu Sudan},
title = {Hardness of Approximate Hypergraph Coloring},
journal = {{SIAM} J. Comput.},
volume = {31},
number = {6},
pages = {1663--1686},
year = {2002},
url = {https://doi.org/10.1137/S0097539700377165},
doi = {10.1137/S0097539700377165},
timestamp = {Tue, 14 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/GuruswamiHS02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tit/GuruswamiHSZ02,
author = {Venkatesan Guruswami and
Johan H{\aa}stad and
Madhu Sudan and
David Zuckerman},
title = {Combinatorial bounds for list decoding},
journal = {{IEEE} Trans. Inf. Theory},
volume = {48},
number = {5},
pages = {1021--1034},
year = {2002},
url = {https://doi.org/10.1109/18.995539},
doi = {10.1109/18.995539},
timestamp = {Tue, 14 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/tit/GuruswamiHSZ02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/HastadV02,
author = {Johan H{\aa}stad and
Srinivasan Venkatesh},
editor = {John H. Reif},
title = {On the advantage over a random assignment},
booktitle = {Proceedings on 34th Annual {ACM} Symposium on Theory of Computing,
May 19-21, 2002, Montr{\'{e}}al, Qu{\'{e}}bec, Canada},
pages = {43--52},
publisher = {{ACM}},
year = {2002},
url = {https://doi.org/10.1145/509907.509916},
doi = {10.1145/509907.509916},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/HastadV02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/dcg/HastadLW01,
author = {Johan H{\aa}stad and
Svante Linusson and
Johan W{\"{a}}stlund},
title = {A Smaller Sleeping Bag for a Baby Snake},
journal = {Discret. Comput. Geom.},
volume = {26},
number = {1},
pages = {173--181},
year = {2001},
url = {https://doi.org/10.1007/s00454-001-0011-5},
doi = {10.1007/S00454-001-0011-5},
timestamp = {Thu, 12 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/dcg/HastadLW01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/Hastad01,
author = {Johan H{\aa}stad},
title = {Some optimal inapproximability results},
journal = {J. {ACM}},
volume = {48},
number = {4},
pages = {798--859},
year = {2001},
url = {https://doi.org/10.1145/502090.502098},
doi = {10.1145/502090.502098},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jacm/Hastad01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jal/AnderssonEH01,
author = {Gunnar Andersson and
Lars Engebretsen and
Johan H{\aa}stad},
title = {A New Way of Using Semidefinite Programming with Applications to Linear
Equations mod p},
journal = {J. Algorithms},
volume = {39},
number = {2},
pages = {162--204},
year = {2001},
url = {https://doi.org/10.1006/jagm.2000.1154},
doi = {10.1006/JAGM.2000.1154},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jal/AnderssonEH01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/AumannHRS01,
author = {Yonatan Aumann and
Johan H{\aa}stad and
Michael O. Rabin and
Madhu Sudan},
title = {Linear-Consistency Testing},
journal = {J. Comput. Syst. Sci.},
volume = {62},
number = {4},
pages = {589--607},
year = {2001},
url = {https://doi.org/10.1006/jcss.2001.1747},
doi = {10.1006/JCSS.2001.1747},
timestamp = {Tue, 14 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jcss/AumannHRS01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/Hastad01,
author = {Johan H{\aa}stad},
title = {A Slight Sharpening of {LMN}},
journal = {J. Comput. Syst. Sci.},
volume = {63},
number = {3},
pages = {498--508},
year = {2001},
url = {https://doi.org/10.1006/jcss.2001.1803},
doi = {10.1006/JCSS.2001.1803},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/Hastad01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamdm/DorHUZ01,
author = {Dorit Dor and
Johan H{\aa}stad and
Staffan Ulfberg and
Uri Zwick},
title = {On Lower Bounds for Selecting the Median},
journal = {{SIAM} J. Discret. Math.},
volume = {14},
number = {3},
pages = {299--311},
year = {2001},
url = {https://doi.org/10.1137/S0895480196309481},
doi = {10.1137/S0895480196309481},
timestamp = {Sat, 25 Apr 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamdm/DorHUZ01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/asiacrypt/HastadN01,
author = {Johan H{\aa}stad and
Mats N{\"{a}}slund},
editor = {Colin Boyd},
title = {Practical Construction and Analysis of Pseudo-Randomness Primitives},
booktitle = {Advances in Cryptology - {ASIACRYPT} 2001, 7th International Conference
on the Theory and Application of Cryptology and Information Security,
Gold Coast, Australia, December 9-13, 2001, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {2248},
pages = {442--459},
publisher = {Springer},
year = {2001},
url = {https://doi.org/10.1007/3-540-45682-1\_26},
doi = {10.1007/3-540-45682-1\_26},
timestamp = {Tue, 01 Jun 2021 15:22:33 +0200},
biburl = {https://dblp.org/rec/conf/asiacrypt/HastadN01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/HastadW01,
author = {Johan H{\aa}stad and
Avi Wigderson},
title = {Simple Analysis of Graph Tests for Linearity and {PCP}},
booktitle = {Proceedings of the 16th Annual {IEEE} Conference on Computational
Complexity, Chicago, Illinois, USA, June 18-21, 2001},
pages = {244--254},
publisher = {{IEEE} Computer Society},
year = {2001},
url = {https://doi.org/10.1109/CCC.2001.933891},
doi = {10.1109/CCC.2001.933891},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/HastadW01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/HastadK01,
author = {Johan H{\aa}stad and
Subhash Khot},
title = {Query Efficient PCPs with Perfect Completeness},
booktitle = {42nd Annual Symposium on Foundations of Computer Science, {FOCS} 2001,
14-17 October 2001, Las Vegas, Nevada, {USA}},
pages = {610--619},
publisher = {{IEEE} Computer Society},
year = {2001},
url = {https://doi.org/10.1109/SFCS.2001.959937},
doi = {10.1109/SFCS.2001.959937},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/HastadK01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ipl/Hastad00,
author = {Johan H{\aa}stad},
title = {On bounded occurrence constraint satisfaction},
journal = {Inf. Process. Lett.},
volume = {74},
number = {1-2},
pages = {1--6},
year = {2000},
url = {https://doi.org/10.1016/S0020-0190(00)00032-6},
doi = {10.1016/S0020-0190(00)00032-6},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/ipl/Hastad00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/AnderssonHHP00,
author = {Arne Andersson and
Torben Hagerup and
Johan H{\aa}stad and
Ola Petersson},
title = {Tight Bounds for Searching a Sorted Array of Strings},
journal = {{SIAM} J. Comput.},
volume = {30},
number = {5},
pages = {1552--1578},
year = {2000},
url = {https://doi.org/10.1137/S0097539797329889},
doi = {10.1137/S0097539797329889},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/siamcomp/AnderssonHHP00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/ccs/HastadJJY00,
author = {Johan H{\aa}stad and
Jakob Jonsson and
Ari Juels and
Moti Yung},
editor = {Dimitris Gritzalis and
Sushil Jajodia and
Pierangela Samarati},
title = {Funkspiel schemes: an alternative to conventional tamper resistance},
booktitle = {{CCS} 2000, Proceedings of the 7th {ACM} Conference on Computer and
Communications Security, Athens, Greece, November 1-4, 2000},
pages = {125--133},
publisher = {{ACM}},
year = {2000},
url = {https://doi.org/10.1145/352600.352619},
doi = {10.1145/352600.352619},
timestamp = {Tue, 10 Nov 2020 20:00:15 +0100},
biburl = {https://dblp.org/rec/conf/ccs/HastadJJY00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/GuruswamiHS00,
author = {Venkatesan Guruswami and
Johan H{\aa}stad and
Madhu Sudan},
title = {Hardness of Approximate Hypergraph Coloring},
booktitle = {41st Annual Symposium on Foundations of Computer Science, {FOCS} 2000,
12-14 November 2000, Redondo Beach, California, {USA}},
pages = {149--158},
publisher = {{IEEE} Computer Society},
year = {2000},
url = {https://doi.org/10.1109/SFCS.2000.892074},
doi = {10.1109/SFCS.2000.892074},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/GuruswamiHS00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/Hastad00,
author = {Johan H{\aa}stad},
editor = {Ugo Montanari and
Jos{\'{e}} D. P. Rolim and
Emo Welzl},
title = {Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation
Algorithms?},
booktitle = {Automata, Languages and Programming, 27th International Colloquium,
{ICALP} 2000, Geneva, Switzerland, July 9-15, 2000, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {1853},
pages = {235},
publisher = {Springer},
year = {2000},
url = {https://doi.org/10.1007/3-540-45022-X\_20},
doi = {10.1007/3-540-45022-X\_20},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/Hastad00.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR00-062,
author = {Venkatesan Guruswami and
Johan H{\aa}stad and
Madhu Sudan},
title = {Hardness of approximate hypergraph coloring},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR00-062}},
year = {2000},
url = {https://eccc.weizmann.ac.il/eccc-reports/2000/TR00-062/index.html},
eprinttype = {ECCC},
eprint = {TR00-062},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR00-062.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/HastadILL99,
author = {Johan H{\aa}stad and
Russell Impagliazzo and
Leonid A. Levin and
Michael Luby},
title = {A Pseudorandom Generator from any One-way Function},
journal = {{SIAM} J. Comput.},
volume = {28},
number = {4},
pages = {1364--1396},
year = {1999},
url = {https://doi.org/10.1137/S0097539793244708},
doi = {10.1137/S0097539793244708},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/HastadILL99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/random/AumannHRS99,
author = {Yonatan Aumann and
Johan H{\aa}stad and
Michael O. Rabin and
Madhu Sudan},
editor = {Dorit S. Hochbaum and
Klaus Jansen and
Jos{\'{e}} D. P. Rolim and
Alistair Sinclair},
title = {Linear Consistency Testing},
booktitle = {Randomization, Approximation, and Combinatorial Algorithms and Techniques,
Third International Workshop on Randomization and Approximation Techniques
in Computer Science, and Second International Workshop on Approximation
Algorithms for Combinatorial Optimization Problems RANDOM-APPROX'99,
Berkeley, CA, USA, August 8-11, 1999, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {1671},
pages = {109--120},
publisher = {Springer},
year = {1999},
url = {https://doi.org/10.1007/978-3-540-48413-4\_11},
doi = {10.1007/978-3-540-48413-4\_11},
timestamp = {Tue, 14 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/random/AumannHRS99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/AnderssonEH99,
author = {Gunnar Andersson and
Lars Engebretsen and
Johan H{\aa}stad},
editor = {Robert Endre Tarjan and
Tandy J. Warnow},
title = {A New Way to Use Semidefinite Programming with Applications to Linear
Equations mod \emph{p}},
booktitle = {Proceedings of the Tenth Annual {ACM-SIAM} Symposium on Discrete Algorithms,
17-19 January 1999, Baltimore, Maryland, {USA}},
pages = {41--50},
publisher = {{ACM/SIAM}},
year = {1999},
url = {http://dl.acm.org/citation.cfm?id=314500.314529},
timestamp = {Thu, 05 Jul 2018 07:29:57 +0200},
biburl = {https://dblp.org/rec/conf/soda/AnderssonEH99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR99-025,
author = {Yonatan Aumann and
Johan H{\aa}stad and
Michael O. Rabin and
Madhu Sudan},
title = {Linear Consistency Testing},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR99-025}},
year = {1999},
url = {https://eccc.weizmann.ac.il/eccc-reports/1999/TR99-025/index.html},
eprinttype = {ECCC},
eprint = {TR99-025},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR99-025.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR99-037,
author = {Johan H{\aa}stad and
Mats N{\"{a}}slund},
title = {The Security of all {RSA} and Discrete Log Bits},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR99-037}},
year = {1999},
url = {https://eccc.weizmann.ac.il/eccc-reports/1999/TR99-037/index.html},
eprinttype = {ECCC},
eprint = {TR99-037},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR99-037.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR99-039,
author = {Johan H{\aa}stad},
title = {On approximating {CSP-B}},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR99-039}},
year = {1999},
url = {https://eccc.weizmann.ac.il/eccc-reports/1999/TR99-039/index.html},
eprinttype = {ECCC},
eprint = {TR99-039},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR99-039.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/iacr/HastadN99,
author = {Johan H{\aa}stad and
Mats N{\"{a}}slund},
title = {Security of all {RSA} and Discrete Log Bits},
journal = {{IACR} Cryptol. ePrint Arch.},
pages = {19},
year = {1999},
url = {http://eprint.iacr.org/1999/019},
timestamp = {Mon, 11 May 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/iacr/HastadN99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ipl/GoldreichH98,
author = {Oded Goldreich and
Johan H{\aa}stad},
title = {On the Complexity of Interactive Proofs with Bounded Communication},
journal = {Inf. Process. Lett.},
volume = {67},
number = {4},
pages = {205--214},
year = {1998},
url = {https://doi.org/10.1016/S0020-0190(98)00116-1},
doi = {10.1016/S0020-0190(98)00116-1},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/ipl/GoldreichH98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/Hastad98,
author = {Johan H{\aa}stad},
title = {The Shrinkage Exponent of de Morgan Formulas is 2},
journal = {{SIAM} J. Comput.},
volume = {27},
number = {1},
pages = {48--64},
year = {1998},
url = {https://doi.org/10.1137/S0097539794261556},
doi = {10.1137/S0097539794261556},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/Hastad98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/CaiCH98,
author = {Liming Cai and
Jianer Chen and
Johan H{\aa}stad},
title = {Circuit Bottom Fan-In and Computational Power},
journal = {{SIAM} J. Comput.},
volume = {27},
number = {2},
pages = {341--355},
year = {1998},
url = {https://doi.org/10.1137/S0097539795282432},
doi = {10.1137/S0097539795282432},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/siamcomp/CaiCH98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/GoldmannH98,
author = {Mikael Goldmann and
Johan H{\aa}stad},
title = {Monotone Circuits for Connectivity Have Depth (log \emph{n})\({}^{\mbox{2-\emph{o}(1)}}\)},
journal = {{SIAM} J. Comput.},
volume = {27},
number = {5},
pages = {1283--1294},
year = {1998},
url = {https://doi.org/10.1137/S0097539795285631},
doi = {10.1137/S0097539795285631},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/siamcomp/GoldmannH98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/esa/HastdIL98,
author = {Johan H{\aa}stad and
Lars Ivansson and
Jens Lagergren},
editor = {Gianfranco Bilardi and
Giuseppe F. Italiano and
Andrea Pietracaprina and
Geppino Pucci},
title = {Fitting Points on the Real Line and Its Application to {RH} Mapping},
booktitle = {Algorithms - {ESA} '98, 6th Annual European Symposium, Venice, Italy,
August 24-26, 1998, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {1461},
pages = {465--476},
publisher = {Springer},
year = {1998},
url = {https://doi.org/10.1007/3-540-68530-8\_39},
doi = {10.1007/3-540-68530-8\_39},
timestamp = {Tue, 14 May 2019 10:00:54 +0200},
biburl = {https://dblp.org/rec/conf/esa/HastdIL98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/HastadN98,
author = {Johan H{\aa}stad and
Mats N{\"{a}}slund},
title = {The Security of Individual {RSA} Bits},
booktitle = {39th Annual Symposium on Foundations of Computer Science, {FOCS} '98,
November 8-11, 1998, Palo Alto, California, {USA}},
pages = {510--521},
publisher = {{IEEE} Computer Society},
year = {1998},
url = {https://doi.org/10.1109/SFCS.1998.743502},
doi = {10.1109/SFCS.1998.743502},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/HastadN98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/swat/Hastad98,
author = {Johan H{\aa}stad},
editor = {Stefan Arnborg and
Lars Ivansson},
title = {Some Recent Strong Inapproximability Results},
booktitle = {Algorithm Theory - {SWAT} '98, 6th Scandinavian Workshop on Algorithm
Theory, Stockholm, Sweden, July, 8-10, 1998, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {1432},
pages = {205--209},
publisher = {Springer},
year = {1998},
url = {https://doi.org/10.1007/BFb0054368},
doi = {10.1007/BFB0054368},
timestamp = {Tue, 14 May 2019 10:00:39 +0200},
biburl = {https://dblp.org/rec/conf/swat/Hastad98.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/CaiCH97,
author = {Liming Cai and
Jianer Chen and
Johan H{\aa}stad},
title = {Circuit Bottom Fan-in and Computational Power},
booktitle = {Proceedings of the Twelfth Annual {IEEE} Conference on Computational
Complexity, Ulm, Germany, June 24-27, 1997},
pages = {158--164},
publisher = {{IEEE} Computer Society},
year = {1997},
url = {https://doi.org/10.1109/CCC.1997.612311},
doi = {10.1109/CCC.1997.612311},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/CaiCH97.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Hastad97,
author = {Johan H{\aa}stad},
editor = {Frank Thomson Leighton and
Peter W. Shor},
title = {Some Optimal Inapproximability Results},
booktitle = {Proceedings of the Twenty-Ninth Annual {ACM} Symposium on the Theory
of Computing, El Paso, Texas, USA, May 4-6, 1997},
pages = {1--10},
publisher = {{ACM}},
year = {1997},
url = {https://doi.org/10.1145/258533.258536},
doi = {10.1145/258533.258536},
timestamp = {Mon, 26 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Hastad97.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR97-037,
author = {Johan H{\aa}stad},
title = {Some optimal inapproximability results},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR97-037}},
year = {1997},
url = {https://eccc.weizmann.ac.il/eccc-reports/1997/TR97-037/index.html},
eprinttype = {ECCC},
eprint = {TR97-037},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR97-037.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR97-038,
author = {Johan H{\aa}stad},
title = {Clique is hard to approximate within n\({}^{\mbox{1-epsilon}}\)},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR97-038}},
year = {1997},
url = {https://eccc.weizmann.ac.il/eccc-reports/1997/TR97-038/index.html},
eprinttype = {ECCC},
eprint = {TR97-038},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR97-038.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/HastadLR96,
author = {Johan H{\aa}stad and
Frank Thomson Leighton and
Brian Rogoff},
title = {Analysis of Backoff Protocols for Multiple Access Channels},
journal = {{SIAM} J. Comput.},
volume = {25},
number = {4},
pages = {740--774},
year = {1996},
url = {https://doi.org/10.1137/S0097539792233828},
doi = {10.1137/S0097539792233828},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/HastadLR96.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tit/BellareCHKS96,
author = {Mihir Bellare and
Don Coppersmith and
Johan H{\aa}stad and
Marcos A. Kiwi and
Madhu Sudan},
title = {Linearity testing in characteristic two},
journal = {{IEEE} Trans. Inf. Theory},
volume = {42},
number = {6},
pages = {1781--1795},
year = {1996},
url = {https://doi.org/10.1109/18.556674},
doi = {10.1109/18.556674},
timestamp = {Tue, 14 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/tit/BellareCHKS96.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Hastad96,
author = {Johan H{\aa}stad},
title = {Clique is Hard to Approximate Within n\({}^{\mbox{1-epsilon}}\)},
booktitle = {37th Annual Symposium on Foundations of Computer Science, {FOCS} '96,
Burlington, Vermont, USA, 14-16 October, 1996},
pages = {627--636},
publisher = {{IEEE} Computer Society},
year = {1996},
url = {https://doi.org/10.1109/SFCS.1996.548522},
doi = {10.1109/SFCS.1996.548522},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Hastad96.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Hastad96,
author = {Johan H{\aa}stad},
editor = {Gary L. Miller},
title = {Testing of the Long Code and Hardness for Clique},
booktitle = {Proceedings of the Twenty-Eighth Annual {ACM} Symposium on the Theory
of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996},
pages = {11--19},
publisher = {{ACM}},
year = {1996},
url = {https://doi.org/10.1145/237814.237820},
doi = {10.1145/237814.237820},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Hastad96.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR96-018,
author = {Oded Goldreich and
Johan H{\aa}stad},
title = {On the Message Complexity of Interactive Proof Systems},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR96-018}},
year = {1996},
url = {https://eccc.weizmann.ac.il/eccc-reports/1996/TR96-018/index.html},
eprinttype = {ECCC},
eprint = {TR96-018},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR96-018.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/HastadJP95,
author = {Johan H{\aa}stad and
Stasys Jukna and
Pavel Pudl{\'{a}}k},
title = {Top-Down Lower Bounds for Depth-Three Circuits},
journal = {Comput. Complex.},
volume = {5},
number = {2},
pages = {99--112},
year = {1995},
url = {https://doi.org/10.1007/BF01268140},
doi = {10.1007/BF01268140},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/cc/HastadJP95.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/HastadRY95,
author = {Johan H{\aa}stad and
Alexander A. Razborov and
Andrew Chi{-}Chih Yao},
title = {On the Shrinkage Exponent for Read-Once Formulae},
journal = {Theor. Comput. Sci.},
volume = {141},
number = {1{\&}2},
pages = {269--282},
year = {1995},
url = {https://doi.org/10.1016/0304-3975(94)00081-S},
doi = {10.1016/0304-3975(94)00081-S},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/HastadRY95.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BellareCHKS95,
author = {Mihir Bellare and
Don Coppersmith and
Johan H{\aa}stad and
Marcos A. Kiwi and
Madhu Sudan},
title = {Linearity Testing in Characteristic Two},
booktitle = {36th Annual Symposium on Foundations of Computer Science, Milwaukee,
Wisconsin, USA, 23-25 October 1995},
pages = {432--441},
publisher = {{IEEE} Computer Society},
year = {1995},
url = {https://doi.org/10.1109/SFCS.1995.492574},
doi = {10.1109/SFCS.1995.492574},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BellareCHKS95.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/AnderssonHP95,
author = {Arne Andersson and
Johan H{\aa}stad and
Ola Petersson},
editor = {Frank Thomson Leighton and
Allan Borodin},
title = {A tight lower bound for searching a sorted array},
booktitle = {Proceedings of the Twenty-Seventh Annual {ACM} Symposium on Theory
of Computing, 29 May-1 June 1995, Las Vegas, Nevada, {USA}},
pages = {417--426},
publisher = {{ACM}},
year = {1995},
url = {https://doi.org/10.1145/225058.225171},
doi = {10.1145/225058.225171},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/AnderssonHP95.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GoldmannH95,
author = {Mikael Goldmann and
Johan H{\aa}stad},
editor = {Frank Thomson Leighton and
Allan Borodin},
title = {Monotone circuits for connectivity have depth (log n)\({}^{\mbox{2-o(1)}}\)
(Extended Abstract)},
booktitle = {Proceedings of the Twenty-Seventh Annual {ACM} Symposium on Theory
of Computing, 29 May-1 June 1995, Las Vegas, Nevada, {USA}},
pages = {569--574},
publisher = {{ACM}},
year = {1995},
url = {https://doi.org/10.1145/225058.225274},
doi = {10.1145/225058.225274},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/GoldmannH95.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/iandc/HaastadWWY94,
author = {Johan H{\aa}stad and
Ingo Wegener and
Norbert Wurm and
Sang{-}Zin Yi},
title = {Optimal Depth, Very Small Size Circuits for Symmetric Functions in
AC\({}^{\mbox{0}}\)},
journal = {Inf. Comput.},
volume = {108},
number = {2},
pages = {200--211},
year = {1994},
url = {https://doi.org/10.1006/inco.1994.1008},
doi = {10.1006/INCO.1994.1008},
timestamp = {Fri, 12 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/iandc/HaastadWWY94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ipl/GoldmannGH94,
author = {Mikael Goldmann and
Per Grape and
Johan H{\aa}stad},
title = {On Average Time Hierarchies},
journal = {Inf. Process. Lett.},
volume = {49},
number = {1},
pages = {15--20},
year = {1994},
url = {https://doi.org/10.1016/0020-0190(94)90048-5},
doi = {10.1016/0020-0190(94)90048-5},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/ipl/GoldmannGH94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/ChangCGHHRR94,
author = {Richard Chang and
Benny Chor and
Oded Goldreich and
Juris Hartmanis and
Johan H{\aa}stad and
Desh Ranjan and
Pankaj Rohatgi},
title = {The Random Oracle Hypothesis Is False},
journal = {J. Comput. Syst. Sci.},
volume = {49},
number = {1},
pages = {24--39},
year = {1994},
url = {https://doi.org/10.1016/S0022-0000(05)80084-4},
doi = {10.1016/S0022-0000(05)80084-4},
timestamp = {Tue, 14 Dec 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/ChangCGHHRR94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamdm/Hastad94,
author = {Johan H{\aa}stad},
title = {On the Size of Weights for Threshold Gates},
journal = {{SIAM} J. Discret. Math.},
volume = {7},
number = {3},
pages = {484--492},
year = {1994},
url = {https://doi.org/10.1137/S0895480192235878},
doi = {10.1137/S0895480192235878},
timestamp = {Sat, 25 Apr 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamdm/Hastad94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/AnderssonHHP94,
author = {Arne Andersson and
Torben Hagerup and
Johan H{\aa}stad and
Ola Petersson},
editor = {Frank Thomson Leighton and
Michael T. Goodrich},
title = {The complexity of searching a sorted array of strings},
booktitle = {Proceedings of the Twenty-Sixth Annual {ACM} Symposium on Theory of
Computing, 23-25 May 1994, Montr{\'{e}}al, Qu{\'{e}}bec,
Canada},
pages = {317--325},
publisher = {{ACM}},
year = {1994},
url = {https://doi.org/10.1145/195058.195175},
doi = {10.1145/195058.195175},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/AnderssonHHP94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/swat/Hastad94,
author = {Johan H{\aa}stad},
editor = {Erik Meineche Schmidt and
Sven Skyum},
title = {Recent Results in Hardness of Approximation},
booktitle = {Algorithm Theory - {SWAT} '94, 4th Scandinavian Workshop on Algorithm
Theory, Aarhus, Denmark, July 6-8, 1994, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {824},
pages = {231--239},
publisher = {Springer},
year = {1994},
url = {https://doi.org/10.1007/3-540-58218-5\_21},
doi = {10.1007/3-540-58218-5\_21},
timestamp = {Tue, 14 May 2019 10:00:39 +0200},
biburl = {https://dblp.org/rec/conf/swat/Hastad94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ipl/HastadPS93,
author = {Johan H{\aa}stad and
Steven J. Phillips and
Shmuel Safra},
title = {A Well-Characterized Approximation Problem},
journal = {Inf. Process. Lett.},
volume = {47},
number = {6},
pages = {301--305},
year = {1993},
url = {https://doi.org/10.1016/0020-0190(93)90076-L},
doi = {10.1016/0020-0190(93)90076-L},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ipl/HastadPS93.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/HastadSS93,
author = {Johan H{\aa}stad and
A. W. Schrift and
Adi Shamir},
title = {The Discrete Logarithm Modulo a Composite Hides O(n) Bits},
journal = {J. Comput. Syst. Sci.},
volume = {47},
number = {3},
pages = {376--404},
year = {1993},
url = {https://doi.org/10.1016/0022-0000(93)90038-X},
doi = {10.1016/0022-0000(93)90038-X},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/HastadSS93.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/rsa/AlonGHP93,
author = {Noga Alon and
Oded Goldreich and
Johan H{\aa}stad and
Ren{\'{e}} Peralta},
title = {Addendum to "Simple Construction of Almost k-wise Independent
Random Variables"},
journal = {Random Struct. Algorithms},
volume = {4},
number = {1},
pages = {119--120},
year = {1993},
url = {https://doi.org/10.1002/rsa.3240040109},
doi = {10.1002/RSA.3240040109},
timestamp = {Fri, 03 Feb 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/rsa/AlonGHP93.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Hastad93,
author = {Johan H{\aa}stad},
title = {The shrinkage exponent is 2},
booktitle = {34th Annual Symposium on Foundations of Computer Science, Palo Alto,
California, USA, 3-5 November 1993},
pages = {114--123},
publisher = {{IEEE} Computer Society},
year = {1993},
url = {https://doi.org/10.1109/SFCS.1993.366876},
doi = {10.1109/SFCS.1993.366876},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Hastad93.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/HastadJP93,
author = {Johan H{\aa}stad and
Stasys Jukna and
Pavel Pudl{\'{a}}k},
title = {Top-Down Lower Bounds for Depth 3 Circuits},
booktitle = {34th Annual Symposium on Foundations of Computer Science, Palo Alto,
California, USA, 3-5 November 1993},
pages = {124--129},
publisher = {{IEEE} Computer Society},
year = {1993},
url = {https://doi.org/10.1109/SFCS.1993.366875},
doi = {10.1109/SFCS.1993.366875},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/HastadJP93.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/istcs/HastadPS93,
author = {Johan H{\aa}stad and
Steven J. Phillips and
Shmuel Safra},
title = {A Well-Characterized Approximation Problem},
booktitle = {Second Israel Symposium on Theory of Computing Systems, {ISTCS} 1993,
Natanya, Israel, June 7-9, 1993, Proceedings},
pages = {261--265},
publisher = {{IEEE} Computer Society},
year = {1993},
url = {https://doi.org/10.1109/ISTCS.1993.253463},
doi = {10.1109/ISTCS.1993.253463},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/istcs/HastadPS93.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/GoldmannHR92,
author = {Mikael Goldmann and
Johan H{\aa}stad and
Alexander A. Razborov},
title = {Majority Gates {VS.} General Weighted Threshold Gates},
journal = {Comput. Complex.},
volume = {2},
pages = {277--300},
year = {1992},
url = {https://doi.org/10.1007/BF01200426},
doi = {10.1007/BF01200426},
timestamp = {Sun, 15 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cc/GoldmannHR92.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ipl/GoldmannH92,
author = {Mikael Goldmann and
Johan H{\aa}stad},
title = {A Simple Lower Bound for Monotone Clique Using a Communication Game},
journal = {Inf. Process. Lett.},
volume = {41},
number = {4},
pages = {221--226},
year = {1992},
url = {https://doi.org/10.1016/0020-0190(92)90184-W},
doi = {10.1016/0020-0190(92)90184-W},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/ipl/GoldmannH92.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/rsa/AlonGHP92,
author = {Noga Alon and
Oded Goldreich and
Johan H{\aa}stad and
Ren{\'{e}} Peralta},
title = {Simple Construction of Almost k-wise Independent Random Variables},
journal = {Random Struct. Algorithms},
volume = {3},
number = {3},
pages = {289--304},
year = {1992},
url = {https://doi.org/10.1002/rsa.3240030308},
doi = {10.1002/RSA.3240030308},
timestamp = {Fri, 03 Feb 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/rsa/AlonGHP92.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/GoldmannHR92,
author = {Mikael Goldmann and
Johan H{\aa}stad and
Alexander A. Razborov},
title = {Majority Gates vs. General Weighted Threshold Gates},
booktitle = {Proceedings of the Seventh Annual Structure in Complexity Theory Conference,
Boston, Massachusetts, USA, June 22-25, 1992},
pages = {2--13},
publisher = {{IEEE} Computer Society},
year = {1992},
url = {https://doi.org/10.1109/SCT.1992.215375},
doi = {10.1109/SCT.1992.215375},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/GoldmannHR92.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/HastadG91,
author = {Johan H{\aa}stad and
Mikael Goldmann},
title = {On the Power of Small-Depth Threshold Circuits},
journal = {Comput. Complex.},
volume = {1},
pages = {113--129},
year = {1991},
url = {https://doi.org/10.1007/BF01272517},
doi = {10.1007/BF01272517},
timestamp = {Sun, 15 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cc/HastadG91.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/iandc/AielloH91,
author = {William Aiello and
Johan H{\aa}stad},
title = {Relativized Perfect Zero Knowledge Is Not {BPP}},
journal = {Inf. Comput.},
volume = {93},
number = {2},
pages = {223--240},
year = {1991},
url = {https://doi.org/10.1016/0890-5401(91)90024-V},
doi = {10.1016/0890-5401(91)90024-V},
timestamp = {Fri, 12 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/iandc/AielloH91.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jcss/AielloH91,
author = {William Aiello and
Johan H{\aa}stad},
title = {Statistical Zero-Knowledge Languages can be Recognized in Two Rounds},
journal = {J. Comput. Syst. Sci.},
volume = {42},
number = {3},
pages = {327--345},
year = {1991},
url = {https://doi.org/10.1016/0022-0000(91)90006-Q},
doi = {10.1016/0022-0000(91)90006-Q},
timestamp = {Tue, 16 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jcss/AielloH91.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/combinatorica/AielloGH90,
author = {William Aiello and
Shafi Goldwasser and
Johan H{\aa}stad},
title = {On the power of interaction},
journal = {Comb.},
volume = {10},
number = {1},
pages = {3--25},
year = {1990},
url = {https://doi.org/10.1007/BF02122692},
doi = {10.1007/BF02122692},
timestamp = {Wed, 22 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/combinatorica/AielloGH90.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jal/Hastad90,
author = {Johan H{\aa}stad},
title = {Tensor Rank is NP-Complete},
journal = {J. Algorithms},
volume = {11},
number = {4},
pages = {644--654},
year = {1990},
url = {https://doi.org/10.1016/0196-6774(90)90014-6},
doi = {10.1016/0196-6774(90)90014-6},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jal/Hastad90.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dimacs/HastadW90,
author = {Johan H{\aa}stad and
Avi Wigderson},
editor = {Jin{-}Yi Cai},
title = {Composition of the Universal Relation},
booktitle = {Advances In Computational Complexity Theory, Proceedings of a {DIMACS}
Workshop, New Jersey, USA, December 3-7, 1990},
series = {{DIMACS} Series in Discrete Mathematics and Theoretical Computer Science},
volume = {13},
pages = {119--134},
publisher = {{DIMACS/AMS}},
year = {1990},
url = {https://doi.org/10.1090/dimacs/013/07},
doi = {10.1090/DIMACS/013/07},
timestamp = {Mon, 22 May 2023 16:07:35 +0200},
biburl = {https://dblp.org/rec/conf/dimacs/HastadW90.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AlonGHP90,
author = {Noga Alon and
Oded Goldreich and
Johan H{\aa}stad and
Ren{\'{e}} Peralta},
title = {Simple Constructions of Almost k-Wise Independent Random Variables},
booktitle = {31st Annual Symposium on Foundations of Computer Science, St. Louis,
Missouri, USA, October 22-24, 1990, Volume {II}},
pages = {544--553},
publisher = {{IEEE} Computer Society},
year = {1990},
url = {https://doi.org/10.1109/FSCS.1990.89575},
doi = {10.1109/FSCS.1990.89575},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AlonGHP90.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/HastadG90,
author = {Johan H{\aa}stad and
Mikael Goldmann},
title = {On the Power of Small-Depth Threshold Circuits},
booktitle = {31st Annual Symposium on Foundations of Computer Science, St. Louis,
Missouri, USA, October 22-24, 1990, Volume {II}},
pages = {610--618},
publisher = {{IEEE} Computer Society},
year = {1990},
url = {https://doi.org/10.1109/FSCS.1990.89582},
doi = {10.1109/FSCS.1990.89582},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/HastadG90.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Hastad90,
author = {Johan H{\aa}stad},
editor = {Harriet Ortiz},
title = {Pseudo-Random Generators under Uniform Assumptions},
booktitle = {Proceedings of the 22nd Annual {ACM} Symposium on Theory of Computing,
May 13-17, 1990, Baltimore, Maryland, {USA}},
pages = {395--404},
publisher = {{ACM}},
year = {1990},
url = {https://doi.org/10.1145/100216.100270},
doi = {10.1145/100216.100270},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Hastad90.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/BeameH89,
author = {Paul Beame and
Johan H{\aa}stad},
title = {Optimal bounds for decision problems on the {CRCW} {PRAM}},
journal = {J. {ACM}},
volume = {36},
number = {3},
pages = {643--670},
year = {1989},
url = {https://doi.org/10.1145/65950.65958},
doi = {10.1145/65950.65958},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jacm/BeameH89.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/HastadJLS89,
author = {Johan H{\aa}stad and
Bettina Just and
J. C. Lagarias and
Claus{-}Peter Schnorr},
title = {Polynomial Time Algorithms for Finding Integer Relations among Real
Numbers},
journal = {{SIAM} J. Comput.},
volume = {18},
number = {5},
pages = {859--881},
year = {1989},
url = {https://doi.org/10.1137/0218059},
doi = {10.1137/0218059},
timestamp = {Tue, 23 Mar 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/siamcomp/HastadJLS89.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/Hastad89,
author = {Johan H{\aa}stad},
editor = {Giorgio Ausiello and
Mariangiola Dezani{-}Ciancaglini and
Simona Ronchi Della Rocca},
title = {Tensor Rank is NP-Complete},
booktitle = {Automata, Languages and Programming, 16th International Colloquium,
ICALP89, Stresa, Italy, July 11-15, 1989, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {372},
pages = {451--460},
publisher = {Springer},
year = {1989},
url = {https://doi.org/10.1007/BFb0035776},
doi = {10.1007/BFB0035776},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/Hastad89.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/HastadLN89,
author = {Johan H{\aa}stad and
Frank Thomson Leighton and
Mark Newman},
editor = {David S. Johnson},
title = {Fast Computation Using Faulty Hypercubes (Extended Abstract)},
booktitle = {Proceedings of the 21st Annual {ACM} Symposium on Theory of Computing,
May 14-17, 1989, Seattle, Washington, {USA}},
pages = {251--263},
publisher = {{ACM}},
year = {1989},
url = {https://doi.org/10.1145/73007.73031},
doi = {10.1145/73007.73031},
timestamp = {Wed, 24 Nov 2021 12:15:31 +0100},
biburl = {https://dblp.org/rec/conf/stoc/HastadLN89.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/combinatorica/Hastad88,
author = {Johan H{\aa}stad},
title = {Dual vectors and lower bounds for the nearest lattice point problem},
journal = {Comb.},
volume = {8},
number = {1},
pages = {75--81},
year = {1988},
url = {https://doi.org/10.1007/BF02122554},
doi = {10.1007/BF02122554},
timestamp = {Wed, 22 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/combinatorica/Hastad88.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/FriezeHKLS88,
author = {Alan M. Frieze and
Johan H{\aa}stad and
Ravi Kannan and
J. C. Lagarias and
Adi Shamir},
title = {Reconstructing Truncated Integer Variables Satisfying Linear Congruences},
journal = {{SIAM} J. Comput.},
volume = {17},
number = {2},
pages = {262--280},
year = {1988},
url = {https://doi.org/10.1137/0217016},
doi = {10.1137/0217016},
timestamp = {Tue, 23 Mar 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/siamcomp/FriezeHKLS88.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/Hastad88,
author = {Johan H{\aa}stad},
title = {Solving Simultaneous Modular Equations of Low Degree},
journal = {{SIAM} J. Comput.},
volume = {17},
number = {2},
pages = {336--341},
year = {1988},
url = {https://doi.org/10.1137/0217019},
doi = {10.1137/0217019},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/siamcomp/Hastad88.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/crypto/Ben-OrGGHKMR88,
author = {Michael Ben{-}Or and
Oded Goldreich and
Shafi Goldwasser and
Johan H{\aa}stad and
Joe Kilian and
Silvio Micali and
Phillip Rogaway},
editor = {Shafi Goldwasser},
title = {Everything Provable is Provable in Zero-Knowledge},
booktitle = {Advances in Cryptology - {CRYPTO} '88, 8th Annual International Cryptology
Conference, Santa Barbara, California, USA, August 21-25, 1988, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {403},
pages = {37--56},
publisher = {Springer},
year = {1988},
url = {https://doi.org/10.1007/0-387-34799-2\_4},
doi = {10.1007/0-387-34799-2\_4},
timestamp = {Sun, 25 Oct 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/crypto/Ben-OrGGHKMR88.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ipl/BoppanaHZ87,
author = {Ravi B. Boppana and
Johan H{\aa}stad and
Stathis Zachos},
title = {Does co-NP Have Short Interactive Proofs?},
journal = {Inf. Process. Lett.},
volume = {25},
number = {2},
pages = {127--132},
year = {1987},
url = {https://doi.org/10.1016/0020-0190(87)90232-8},
doi = {10.1016/0020-0190(87)90232-8},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/ipl/BoppanaHZ87.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ipl/Hastad87,
author = {Johan H{\aa}stad},
title = {One-Way Permutations in {NC0}},
journal = {Inf. Process. Lett.},
volume = {26},
number = {3},
pages = {153--155},
year = {1987},
url = {https://doi.org/10.1016/0020-0190(87)90053-6},
doi = {10.1016/0020-0190(87)90053-6},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/ipl/Hastad87.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AielloH87,
author = {William Aiello and
Johan H{\aa}stad},
title = {Perfect Zero-Knowledge Languages Can Be Recognized in Two Rounds},
booktitle = {28th Annual Symposium on Foundations of Computer Science, Los Angeles,
California, USA, 27-29 October 1987},
pages = {439--448},
publisher = {{IEEE} Computer Society},
year = {1987},
url = {https://doi.org/10.1109/SFCS.1987.47},
doi = {10.1109/SFCS.1987.47},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AielloH87.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BeameH87,
author = {Paul Beame and
Johan H{\aa}stad},
editor = {Alfred V. Aho},
title = {Optimal Bounds for Decision Problems on the {CRCW} {PRAM}},
booktitle = {Proceedings of the 19th Annual {ACM} Symposium on Theory of Computing,
1987, New York, New York, {USA}},
pages = {83--93},
publisher = {{ACM}},
year = {1987},
url = {https://doi.org/10.1145/28395.28405},
doi = {10.1145/28395.28405},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/BeameH87.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/HastadLR87,
author = {Johan H{\aa}stad and
Frank Thomson Leighton and
Brian Rogoff},
editor = {Alfred V. Aho},
title = {Analysis of Backoff Protocols for Multiple Access Channels (Extended
Abstract)},
booktitle = {Proceedings of the 19th Annual {ACM} Symposium on Theory of Computing,
1987, New York, New York, {USA}},
pages = {241--253},
publisher = {{ACM}},
year = {1987},
url = {https://doi.org/10.1145/28395.28422},
doi = {10.1145/28395.28422},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/HastadLR87.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/HastadLN87,
author = {Johan H{\aa}stad and
Frank Thomson Leighton and
Mark Newman},
editor = {Alfred V. Aho},
title = {Reconfiguring a Hypercube in the Presence of Faults (Extended Abstract)},
booktitle = {Proceedings of the 19th Annual {ACM} Symposium on Theory of Computing,
1987, New York, New York, {USA}},
pages = {274--284},
publisher = {{ACM}},
year = {1987},
url = {https://doi.org/10.1145/28395.28425},
doi = {10.1145/28395.28425},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/HastadLN87.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AielloGH86,
author = {William Aiello and
Shafi Goldwasser and
Johan H{\aa}stad},
title = {On the Power of Interaction},
booktitle = {27th Annual Symposium on Foundations of Computer Science, Toronto,
Canada, 27-29 October 1986},
pages = {368--379},
publisher = {{IEEE} Computer Society},
year = {1986},
url = {https://doi.org/10.1109/SFCS.1986.36},
doi = {10.1109/SFCS.1986.36},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AielloGH86.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/HastadHLS86,
author = {Johan H{\aa}stad and
Bettina Helfrich and
J. C. Lagarias and
Claus{-}Peter Schnorr},
editor = {Burkhard Monien and
Guy Vidal{-}Naquet},
title = {Polynomial Time Algorithms for Finding Integer Relations Among Real
Numbers},
booktitle = {{STACS} 86, 3rd Annual Symposium on Theoretical Aspects of Computer
Science, Orsay, France, January 16-18, 1986, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {210},
pages = {105--118},
publisher = {Springer},
year = {1986},
url = {https://doi.org/10.1007/3-540-16078-7\_69},
doi = {10.1007/3-540-16078-7\_69},
timestamp = {Tue, 23 Mar 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stacs/HastadHLS86.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Hastad86,
author = {Johan H{\aa}stad},
editor = {Juris Hartmanis},
title = {Almost Optimal Lower Bounds for Small Depth Circuits},
booktitle = {Proceedings of the 18th Annual {ACM} Symposium on Theory of Computing,
May 28-30, 1986, Berkeley, California, {USA}},
pages = {6--20},
publisher = {{ACM}},
year = {1986},
url = {https://doi.org/10.1145/12130.12132},
doi = {10.1145/12130.12132},
timestamp = {Sun, 02 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/Hastad86.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/crypto/Hastad85,
author = {Johan H{\aa}stad},
editor = {Hugh C. Williams},
title = {On Using {RSA} with Low Exponent in a Public Key Network},
booktitle = {Advances in Cryptology - {CRYPTO} '85, Santa Barbara, California,
USA, August 18-22, 1985, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {218},
pages = {403--408},
publisher = {Springer},
year = {1985},
url = {https://doi.org/10.1007/3-540-39799-X\_29},
doi = {10.1007/3-540-39799-X\_29},
timestamp = {Tue, 14 May 2019 10:00:48 +0200},
biburl = {https://dblp.org/rec/conf/crypto/Hastad85.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChorGHFRS85,
author = {Benny Chor and
Oded Goldreich and
Johan H{\aa}stad and
Joel Friedman and
Steven Rudich and
Roman Smolensky},
title = {The Bit Extraction Problem of t-Resilient Functions (Preliminary Version)},
booktitle = {26th Annual Symposium on Foundations of Computer Science, Portland,
Oregon, USA, 21-23 October 1985},
pages = {396--407},
publisher = {{IEEE} Computer Society},
year = {1985},
url = {https://doi.org/10.1109/SFCS.1985.55},
doi = {10.1109/SFCS.1985.55},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChorGHFRS85.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/HastadS85,
author = {Johan H{\aa}stad and
Adi Shamir},
editor = {Robert Sedgewick},
title = {The Cryptographic Security of Truncated Linearly Related Variables},
booktitle = {Proceedings of the 17th Annual {ACM} Symposium on Theory of Computing,
May 6-8, 1985, Providence, Rhode Island, {USA}},
pages = {356--362},
publisher = {{ACM}},
year = {1985},
url = {https://doi.org/10.1145/22145.22184},
doi = {10.1145/22145.22184},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/HastadS85.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
a service of 
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-02-07 23:04 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
