Jakob Nordström
Professor
- 2014
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
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
- 2013
Some trade-off results for polynomial calculus
Beck, C., Nordström, Jakob & Tang, B., 2013, STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing. p. 813-822 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Towards an understanding of polynomial calculus: New separations and lower bounds (extended abstract)
Filmus, Y., Lauria, M., Mikša, M., Nordström, Jakob & Vinyals, M., 2013, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings. PART 1 ed. p. 437-448 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); No. PART 1, Vol. 7965 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Pebble games, proof complexity, and time-space trade-offs
Nordström, Jakob, 13 Sep 2013, In: Logical Methods in Computer Science. 9, 3, 15.Research output: Contribution to journal › Journal article › Research › peer-review
- 2012
Space complexity in polynomial calculus
Filmus, Y., Lauria, M., Nordström, Jakob, Thapen, N. & Ron-Zewi, N., 2012, Proceedings - 2012 IEEE 27th Conference on Computational Complexity, CCC 2012. p. 334-344 11 p. 6243410. (Proceedings of the Annual IEEE Conference on Computational Complexity).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
On the Virtue of Succinct Proofs: Amplifying Communication Complexity Hardness to Time-Space Trade-offs in Proof Complexity (Extended Abstract)
Huynh, T. & Nordström, Jakob, 1 May 2012, Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC '12). Association for Computing Machinery, Inc., p. 233-248 16 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Relating proof complexity measures and practical hardness of SAT
Järvisalo, M., Matsliah, A., Nordström, Jakob & Živný, S., 2012, Principles and Practice of Constraint Programming - 18th International Conference, CP 2012, Proceedings. p. 316-331 16 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 7514 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
On the relative strength of pebbling and resolution
Nordström, Jakob, Apr 2012, In: ACM Transactions on Computational Logic. 13, 2, a16.Research output: Contribution to journal › Journal article › Research › peer-review
- 2011
- Published
On minimal unsatisfiability and time-space trade-offs for k-DNF resolution
Nordström, Jakob & Razborov, A., 2011, Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings. PART 1 ed. p. 642-653 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); No. PART 1, Vol. 6755 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