Jakob Nordström
Professor
- 2020
- Published
Exponential resolution lower bounds for weak pigeonhole principle and perfect matching formulas over sparse graphs
de Rezende, S. F., Nordström, Jakob, Risse, K. & Sokolov, D., 1 Jul 2020, 35th Computational Complexity Conference, CCC 2020. Saraf, S. (ed.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 1-24 28. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 169).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
de Rezende, S. F., Meir, O., Nordström, Jakob, Pitassi, T., Robere, R. & Vinyals, M., 1 Nov 2020, Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS '20). IEEE, p. 24-30Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- 2019
- Published
On division versus saturation in pseudo-boolean solving
Gocht, S., Nordström, Jakob & Yehudayoff, A., 2019, Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI 2019. Kraus, S. (ed.). International Joint Conferences on Artificial Intelligence, p. 1711-1718Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
de Rezende, S. F., Nordström, Jakob, Meir, O. & Robere, R., 2019, 34th Computational Complexity Conference (CCC 2019), Proceedings. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Vol. 137. p. 1-16 18. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 137).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- 2018
Clique is hard on average for regular resolution
Atserias, A., Lauria, M., Bonacina, I., Nordström, Jakob, De Rezende, S. F. & Razborov, A., 20 Jun 2018, STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Henzinger, M., Kempe, D. & Diakonikolas, I. (eds.). ACM Association for Computing Machinery, p. 646-659 14 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
Divide and conquer: Towards faster pseudo-boolean solving
Elffers, J. & Nordström, Jakob, 2018, Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018. Lang, J. (ed.). International Joint Conferences on Artificial Intelligence, p. 1291-1299 9 p. (IJCAI International Joint Conference on Artificial Intelligence, Vol. 2018-July).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Seeking practical CDCL insights from theoretical SAT benchmarks
Elffers, J., Cru, J. G., Gocht, S., Nordström, Jakob & Simon, L., 2018, Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018. Lang, J. (ed.). International Joint Conferences on Artificial Intelligence, p. 1300-1308 9 p. (IJCAI International Joint Conference on Artificial Intelligence, Vol. 2018-July).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Using combinatorial benchmarks to probe the reasoning power of pseudo-boolean solvers
Elffers, J., Giráldez-Cru, J., Nordström, Jakob & Vinyals, M., 2018, Theory and Applications of Satisfiability Testing – SAT 2018 - 21st International Conference, SAT 2018, Held as Part of the Federated Logic Conference, FloC 2018, Proceedings. Beyersdorff, O. & Wintersteiger, C. M. (eds.). Springer Verlag, p. 75-93 19 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 10929 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
In between resolution and cutting planes: A study of proof systems for pseudo-boolean SAT solving
Vinyals, M., Elffers, J., Giráldez-Cru, J., Gocht, S. & Nordström, Jakob, 2018, Theory and Applications of Satisfiability Testing – SAT 2018 - 21st International Conference, SAT 2018, Held as Part of the Federated Logic Conference, FloC 2018, Proceedings. Beyersdorff, O. & Wintersteiger, C. M. (eds.). Springer Verlag, p. 292-310 19 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 10929 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- 2017
Cumulative space in black-white pebbling and resolution
Alwen, J., De Rezende, S. F., Nordström, Jakob & Vinyals, M., 1 Nov 2017, 8th Innovations in Theoretical Computer Science Conference, ITCS 2017. Papadimitriou, C. H. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 67).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