Jakob Nordström
Titel
Zitiert von
Zitiert von
Jahr
Pebble games, proof complexity and time-space trade-offs
J Nordström
Logical Methods in Computer Science 9 (3), 2013
802013
Narrow proofs may be spacious: Separating space and width in resolution
J Nordström
SIAM Journal on Computing 39 (1), 59-121, 2009
752009
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
742008
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
712011
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
602012
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
552015
On the interplay between proof complexity and SAT solving
J Nordström
ACM SIGLOG News 2 (3), 19-44, 2015
542015
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
482013
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
472008
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
45*2016
Narrow proofs may be maximally long
A Atserias, M Lauria, J Nordström
29th IEEE Conference on Computational Complexity (CCC '14), 286-297, 2014
442014
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
442012
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
42*2020
A simplified way of proving trade-off results for resolution
J Nordström
Information Processing Letters 109 (18), 1030-1035, 2009
302009
Divide and Conquer: Towards Faster Pseudo-Boolean Solving.
J Elffers, J Nordström
27th International Joint Conference on Artificial Intelligence (IJCAI '18 …, 2018
282018
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
262015
Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds (Extended Abstract)
Y Filmus, M Lauria, M Mikša, J Nordström, M Vinyals
Proceedings of the 40th International Colloquium on Automata, Languages and …, 2013
26*2013
From small space to small width in resolution
Y Filmus, M Lauria, M Mikša, J Nordström, M Vinyals
ACM Transactions on Computational Logic 16 (4), 2015
242015
Long proofs of (seemingly) simple formulas
M Mikša, J Nordström
Proceedings of the 17th International Conference on Theory and Applications …, 2014
242014
Understanding space in resolution: Optimal lower bounds and exponential trade-offs
E Ben-Sasson, J Nordström
Dagstuhl Seminar Proceedings, 2008
232008
Das System kann den Vorgang jetzt nicht ausführen. Versuchen Sie es später erneut.
Artikel 1–20