Obserwuj
Jakob Nordström
Tytuł
Cytowane przez
Cytowane przez
Rok
Pebble games, proof complexity and time-space trade-offs
J Nordström
Logical Methods in Computer Science 9 (3), 2013
872013
On the virtue of succinct proofs: Amplifying communication complexity hardness to time-space trade-offs in proof complexity
T Huynh, J Nordström
Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC …, 2012
832012
Narrow proofs may be spacious: Separating space and width in resolution
J Nordström
Proceedings of the thirty-eighth annual ACM symposium on theory of computing …, 2006
782006
Short proofs may be spacious: An optimal separation of space and length in resolution
E Ben-Sasson, J Nordstrom
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer …, 2008
772008
Divide and Conquer: Towards Faster Pseudo-Boolean Solving.
J Elffers, J Nordström
27th International Joint Conference on Artificial Intelligence (IJCAI '18 …, 2018
752018
Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions.
E Ben-Sasson, J Nordström
Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS '11 …, 2011
752011
On the interplay between proof complexity and SAT solving
J Nordström
ACM SIGLOG News 2 (3), 19-44, 2015
632015
How limited interaction hinders real communication (and what it means for proof and circuit complexity)
F de Rezende, Susanna, J Nordström, M Vinyals
Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer …, 2016
61*2016
Narrow proofs may be maximally long
A Atserias, M Lauria, J Nordström
ACM Transactions on Computational Logic 17 (3), 19:1-19:30, 2016
592016
Space Complexity in Polynomial Calculus
Y Filmus, M Lauria, J Nordström, N Ron-Zewi, N Thapen
SIAM Journal on Computing 44 (4), 1119-1153, 2015
582015
Proof complexity and SAT solving
S Buss, J Nordström
Handbook of Satisfiability, 2nd edition, 233-350, 2021
572021
Some trade-off results for polynomial calculus
C Beck, J Nordström, B Tang
Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC …, 2013
522013
Towards an optimal separation of space and length in resolution
J Nordström, J Håstad
Proceedings of the fortieth annual ACM symposium on Theory of computing, 701-710, 2008
482008
CNFgen: A generator of crafted benchmarks
M Lauria, J Elffers, J Nordström, M Vinyals
Theory and Applications of Satisfiability Testing–SAT 2017: 20th …, 2017
462017
New wine into old wineskins: A survey of some pebbling classics with supplemental results
J Nordström
Manuscript in preparation. Current draft version available at the webpage …, 2020
45*2020
Relating proof complexity measures and practical hardness of SAT
M Järvisalo, A Matsliah, J Nordström, S Živný
Proceedings of the 18th International Conference on Principles and Practice …, 2012
452012
A generalized method for proving polynomial calculus degree lower bounds
M Mikša, J Nordström
Proceedings of the 30th Annual Computational Complexity Conference (CCC '15 …, 2015
422015
Seeking Practical CDCL Insights from Theoretical SAT Benchmarks.
J Elffers, J Giráldez-Cru, S Gocht, J Nordström, L Simon
27th International Joint Conference on Artificial Intelligence (IJCAI '18 …, 2018
362018
A simplified way of proving trade-off results for resolution
J Nordström
Information Processing Letters 109 (18), 1030-1035, 2009
322009
Clique is hard on average for regular resolution
A Atserias, I Bonacina, SF De Rezende, M Lauria, J Nordström, ...
Journal of the ACM (JACM) 68 (4), 1-26, 2021
292021
Nie można teraz wykonać tej operacji. Spróbuj ponownie później.
Prace 1–20