Jakob Nordström
Professor
- 2017
CNFgen: A generator of crafted benchmarks
Lauria, M., Elffers, J., Nordström, Jakob & Vinyals, M., 2017, Theory and Applications of Satisfiability Testing – SAT 2017 - 20th International Conference, Proceedings. Gaspers, S. & Walsh, T. (eds.). Springer Verlag, p. 464-473 10 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 10491 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- 2016
Supercritical space-width trade-offs for resolution
Berkholz, C. & Nordström, Jakob, 1 Aug 2016, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016. Rabani, Y., Chatzigiannakis, I., Sangiorgi, D. & Mitzenmacher, M. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 57. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 55).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler - Leman Refinement Steps
Berkholz, C. & Nordström, Jakob, 5 Jul 2016, Proceedings of the 31st Annual ACM-IEEE Symposium on Logic in Computer Science, LICS 2016. Institute of Electrical and Electronics Engineers Inc., p. 267-276 10 p. (Proceedings - Symposium on Logic in Computer Science, Vol. 05-08-July-2016).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Trade-offs between time and memory in a tighter model of CDCL SAT solvers
Elffers, J., Johannsen, J., Lauria, M., Magnard, T., Nordström, Jakob & Vinyals, M., 2016, Theory and Applications of Satisfiability Testing – SAT 2016 - 19th International Conference, Proceedings. Le Berre, D. & Creignou, N. (eds.). Springer Verlag, p. 160-176 17 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 9710).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- 2015
Hardness of Approximation in PSPACE and Separation Results for Pebble Games (Extended Abstract)
Chan, S. M., Lauria, M., Nordström, Jakob & Vinyals, M., 1 Oct 2015, Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS~'15). IEEE, p. 466-485 20 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
A generalized method for proving polynomial calculus degree lower bounds
Mikša, M. & Nordström, Jakob, 1 Jun 2015, 30th Conference on Computational Complexity, CCC 2015. Zuckerman, D. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 467-487 21 p. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 33).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Tight size-degree bounds for sums-of-squares proofs
Lauria, M. & Nordström, Jakob, 1 Jun 2015, 30th Conference on Computational Complexity, CCC 2015. Zuckerman, D. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 448-466 19 p. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 33).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- 2014
From small space to small width in resolution
Filmus, Y., Lauria, M., Mikša, M., Nordström, Jakob & Vinyals, M., 1 Mar 2014, 31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014. Portier, N. & Mayr, E. W. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Vol. 25. p. 300-311 12 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
A (biased) proof complexity survey for SAT practitioners
Nordström, Jakob, 2014, Theory and Applications of Satisfiability Testing, SAT 2014 - 17th International Conference, Held as Part of theVienna Summer of Logic, VSL 2014, Proceedings. Springer Verlag, p. 1-6 6 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 8561 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Long Proofs of (Seemingly) Simple Formulas
Mikša, M. & Nordström, Jakob, 2014, Theory and Applications of Satisfiability Testing, SAT 2014 - 17th International Conference, Held as Part of theVienna Summer of Logic, VSL 2014, Proceedings. Springer Verlag, p. 121-137 17 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 8561 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
ID: 209376262
Most downloads
-
69
downloads
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Published -
33
downloads
Exponential resolution lower bounds for weak pigeonhole principle and perfect matching formulas over sparse graphs
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Published -
25
downloads
Verifying Properties of Bit-vector Multiplication Using Cutting Planes Reasoning
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Published