I agree that this site is using cookies. You can find further informations here.
X
Håstad, Johan
102  results:
Search for persons X
?
1

On small-depth Frege proofs for PHP:

, In: 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS),
Hastad, Johan - p. 37-49 , 2023
Link: https://doi.org/10.1109/..
 
?
2

Optimal Inapproximability with Universal Factor Graphs:

Austrin, Per ; Brown-Cohen, Jonah ; Håstad, Johan
ACM Transactions on Algorithms.  , 2023
Link: https://doi.org/10.1145/..
 
?
3

On Bounded Depth Proofs for Tseitin Formulas on the Grid; R..:

, In: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS),
Hastad, Johan ; Risse, Kilian - p. 1138-1149 , 2022
Link: https://doi.org/10.1109/..
 
?
4

Optimal inapproximability with universal factor graphs:

, In: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms,
Austrin, Per ; Brown-Cohen, Jonah ; Håstad, Johan - p. 434-453 , 2021
Link: https://dl.acm.org/doi/1..
 
?
5

Explicit two-deletion codes with redundancy matching the ex..:

, In: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms,
Guruswami, Venkatesan ; Håstad, Johan - p. 21-32 , 2021
Link: https://dl.acm.org/doi/1..
 
?
6

Optimal Inapproximability with Universal Factor Graphs:

, In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA),
Austrin, Per ; Brown-Cohen, Jonah ; Håstad, Johan - p. 434-453 , 2021
Link: https://doi.org/10.1137/..
 
?
7

Explicit two-deletion codes with redundancy matching the ex..:

, In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA),
Guruswami, Venkatesan ; Håstad, Johan - p. 21-32 , 2021
Link: https://doi.org/10.1137/..
 
?
8

On Small-depth Frege Proofs for Tseitin for Grids:

Håstad, Johan
Journal of the ACM.  68 (2020)  1 - p. 1-31 , 2020
Link: https://doi.org/10.1145/..
 
?
9

On Small-depth Frege Proofs for Tseitin for Grids:

Håstad, Johan
Journal of the ACM (JACM).  68 (2020)  1 - p. 1-31 , 2020
Link: https://dl.acm.org/doi/1..
 
?
10

Bounded Independence versus Symmetric Tests:

Boppana, Ravi ; Håstad, Johan ; Lee, Chin Ho.
ACM Transactions on Computation Theory (TOCT).  11 (2019)  4 - p. 1-27 , 2019
Link: https://dl.acm.org/doi/1..
 
?
11

Bounded Independence versus Symmetric Tests:

Boppana, Ravi ; Håstad, Johan ; Lee, Chin Ho.
ACM Transactions on Computation Theory.  11 (2019)  4 - p. 1-27 , 2019
Link: https://doi.org/10.1145/..
 
?
12

$(2+\varepsilon)$-Sat Is NP-hard:

Austrin, Per ; Guruswami, Venkatesan ; Håstad, Johan
SIAM Journal on Computing.  46 (2017)  5 - p. 1554-1573 , 2017
Link: https://doi.org/10.1137/..
 
?
13

An Average-Case Depth Hierarchy Theorem for Boolean Circuit:

Håstad, Johan ; Rossman, Benjamin ; Servedio, Rocco A..
Journal of the ACM.  64 (2017)  5 - p. 1-27 , 2017
Link: https://doi.org/10.1145/..
 
?
14

An Average-Case Depth Hierarchy Theorem for Boolean Circuit:

Håstad, Johan ; Rossman, Benjamin ; Servedio, Rocco A..
Journal of the ACM (JACM).  64 (2017)  5 - p. 1-27 , 2017
Link: https://dl.acm.org/doi/1..
 
?
15

Super-Polylogarithmic Hypergraph Coloring Hardness via Low-..:

Guruswami, Venkatesan ; Harsha, Prahladh ; Håstad, Johan..
SIAM Journal on Computing.  46 (2017)  1 - p. 132-159 , 2017
Link: https://doi.org/10.1137/..
 
1-15