Jakob Nordström

Professor
Fler filtreringsmöjligheter
  1. Cumulative space in black-white pebbling and resolution

    Joël Alwen, Susanna F. De Rezende, Jakob Nordström & Marc Vinyals, 2017 nov 1, 8th Innovations in Theoretical Computer Science Conference, ITCS 2017. Papadimitriou, C. H. (red.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, (Leibniz International Proceedings in Informatics, LIPIcs; vol. 67).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  2. Clique is hard on average for regular resolution

    Albert Atserias, Ilario Bonacina, Susanna F. De Rezende, Massimo Lauria, Jakob Nordström & Alexander Razborov, 2018 jun 20, STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Henzinger, M., Kempe, D. & Diakonikolas, I. (red.). Association for Computing Machinery (ACM), s. 646-659 14 s. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  3. Narrow proofs may be maximally long

    Albert Atserias, Massimo Lauria & Jakob Nordström, 2016 feb, I: ACM Transactions on Computational Logic. 17, 3, 19.

    Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskrift

  4. Narrow proofs may be maximally long

    Albert Atserias, Massimo Lauria & Jakob Nordström, 2014, Proceedings - IEEE 29th Conference on Computational Complexity, CCC 2014. IEEE - Institute of Electrical and Electronics Engineers Inc., s. 286-297 12 s. 6875497. (Proceedings of the Annual IEEE Conference on Computational Complexity).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  5. Some trade-off results for polynomial calculus

    Chris Beck, Jakob Nordström & Bangsheng Tang, 2013, STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing. Association for Computing Machinery (ACM), s. 813-822 10 s. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  6. Short proofs may be spacious: An optimal separation of space and length in resolution

    Eli Ben-Sasson & Jakob Nordström, 2008, Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008. IEEE - Institute of Electrical and Electronics Engineers Inc., s. 709-718 10 s. 4691003. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  7. Supercritical space-width trade-offs for resolution

    Christoph Berkholz & Jakob Nordström, 2020, I: SIAM Journal on Computing. 49, 1, s. 98-118 21 s.

    Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskrift

  8. Supercritical space-width trade-offs for resolution

    Christoph Berkholz & Jakob Nordström, 2016 aug 1, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016. Rabani, Y., Chatzigiannakis, I., Sangiorgi, D. & Mitzenmacher, M. (red.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 57. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 55).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  9. Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler - Leman Refinement Steps

    Christoph Berkholz & Jakob Nordström, 2016 jul 5, Proceedings of the 31st Annual ACM-IEEE Symposium on Logic in Computer Science, LICS 2016. Association for Computing Machinery (ACM), s. 267-276 10 s. (Proceedings - Symposium on Logic in Computer Science; vol. 05-08-July-2016).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  10. Hardness of Approximation in PSPACE and Separation Results for Pebble Games

    Siu Man Chan, Massimo Lauria, Jakob Nordstrom & Marc Vinyals, 2015 dec 11, Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015. IEEE - Institute of Electrical and Electronics Engineers Inc., s. 466-485 20 s. 7354410. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2015-December).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  11. Exponential resolution lower bounds for weak pigeonhole principle and perfect matching formulas over sparse graphs

    Susanna F. de Rezende, Jakob Nordström, Kilian Risse & Dmitry Sokolov, 2020 jul 1, CCC '20: Proceedings of the 35th Computational Complexity Conference 2020. Saraf, S. (red.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 28. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 169).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  12. Nullstellensatz size-degree trade-offs from reversible pebbling

    Susanna F. De Rezende, Jakob Nordström, Or Meir & Robert Robere, 2019 jul 1, 34th Computational Complexity Conference, CCC 2019. Shpilka, A. (red.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, (Leibniz International Proceedings in Informatics, LIPIcs; vol. 137).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  13. How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity)

    Susanna F. De Rezende, Jakob Nordstrom & Marc Vinyals, 2016 dec 14, Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016. IEEE - Institute of Electrical and Electronics Engineers Inc., s. 295-304 10 s. 7782943. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2016-December).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  14. Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling

    Susanna F. De Rezende, Or Meir, Jakob Nordström & Robert Robere, 2021, I: Computational Complexity. 30, 1, 4.

    Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskrift

  15. Learn to relax: Integrating 0-1 integer linear programming with pseudo-Boolean conflict-driven search

    Jo Devriendt, Ambros Gleixner & Jakob Nordström, 2021 jan 18, I: Constraints.

    Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskrift

  16. Seeking practical CDCL insights from theoretical SAT benchmarks

    Jan Elffers, Jesús Giráldez Cru, Stephan Gocht, Jakob Nordström & Laurent Simon, 2018, Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018. Lang, J. (red.). International Joint Conferences on Artificial Intelligence, s. 1300-1308 9 s. (IJCAI International Joint Conference on Artificial Intelligence; vol. 2018-July).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  17. Divide and conquer: Towards faster pseudo-boolean solving

    Jan Elffers & Jakob Nordström, 2018, Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018. Lang, J. (red.). International Joint Conferences on Artificial Intelligence, s. 1291-1299 9 s. (IJCAI International Joint Conference on Artificial Intelligence; vol. 2018-July).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  18. Using combinatorial benchmarks to probe the reasoning power of pseudo-boolean solvers

    Jan Elffers, Jesús Giráldez-Cru, Jakob Nordström & Marc Vinyals, 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. (red.). Springer, s. 75-93 19 s. (Lecture Notes in Computer Science; vol. 10929).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  19. Trade-offs between time and memory in a tighter model of CDCL SAT solvers

    Jan Elffers, Jan Johannsen, Massimo Lauria, Thomas Magnard, Jakob Nordström & Marc Vinyals, 2016, Theory and Applications of Satisfiability Testing – SAT 2016: 19th International Conference, Proceedings. Le Berre, D. & Creignou, N. (red.). Springer, s. 160-176 17 s. (Lecture Notes in Computer Science; vol. 9710).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  20. From small space to small width in resolution

    Yuval Filmus, Massimo Lauria, Mladen Mikša, Jakob Nordström & Marc Vinyals, 2015 aug 1, I: ACM Transactions on Computational Logic. 16, 4, 28.

    Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskrift

  21. Space complexity in polynomial calculus

    Yuval Filmus, Massimo Lauria, Jakob Nordström, Noga Ron-Zewi & Neil Thapen, 2015, I: SIAM Journal on Computing. 44, 4, s. 1119-1153 35 s.

    Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskrift

  22. From small space to small width in resolution

    Yuval Filmus, Massimo Lauria, Mladen Mikša, Jakob Nordström & Marc Vinyals, 2014 mar 1, 31st International Symposium on Theoretical Aspects of Computer Science, STACS 2014. Portier, N. & Mayr, E. W. (red.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Vol. 25. s. 300-311 12 s. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 25).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  23. Towards an understanding of polynomial calculus: New separations and lower bounds (extended abstract)

    Yuval Filmus, Massimo Lauria, Mladen Mikša, Jakob Nordström & Marc Vinyals, 2013, Automata, Languages, and Programming: 40th International Colloquium, ICALP 2013, Proceedings. PART 1 uppl. Springer, s. 437-448 12 s. (Lecture Notes in Computer Science; vol. 7965, nr. PART 1).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  24. Space complexity in polynomial calculus

    Yuval Filmus, Massimo Lauria, Jakob Nordström, Neil Thapen & Noga Ron-Zewi, 2012, Proceedings - 2012 IEEE 27th Conference on Computational Complexity, CCC 2012. IEEE - Institute of Electrical and Electronics Engineers Inc., s. 334-344 11 s. 6243410. (Proceedings of the Annual IEEE Conference on Computational Complexity).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  25. Certifying Solvers for Clique and Maximum Common (Connected) Subgraph Problems

    Stephan Gocht, Ross McBride, Ciaran McCreesh, Jakob Nordström, Patrick Prosser & James Trimble, 2020, Principles and Practice of Constraint Programming - 26th International Conference, CP 2020, Proceedings. Simonis, H. (red.). Springer, s. 338-357 20 s. (Lecture Notes in Computer Science; vol. 12333).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  26. On division versus saturation in pseudo-boolean solving

    Stephan Gocht, Jakob Nordström & Amir Yehudayoff, 2019, Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI 2019. Kraus, S. (red.). International Joint Conferences on Artificial Intelligence, s. 1711-1718 8 s. (IJCAI International Joint Conference on Artificial Intelligence; vol. 2019-August).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  27. On the virtue of succinct proofs: Amplifying communication complexity hardness to time-space trade-offs in proof complexity

    Trinh Huynh & Jakob Nordstrom, 2012, STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing. Association for Computing Machinery (ACM), s. 233-247 15 s. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  28. Relating proof complexity measures and practical hardness of SAT

    Matti Järvisalo, Arie Matsliah, Jakob Nordström & Stanislav Živný, 2012, Principles and Practice of Constraint Programming : 18th International Conference, CP 2012, Proceedings. Springer, s. 316-331 16 s. (Lecture Notes in Computer Science; vol. 7514).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  29. Using Resolution Proofs to Analyse CDCL Solvers

    Janne I. Kokkala & Jakob Nordström, 2020, Principles and Practice of Constraint Programming - 26th International Conference, CP 2020, Proceedings. Simonis, H. (red.). Springer, s. 427-444 18 s. (Lecture Notes in Computer Science; vol. 12333).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  30. Trade-offs between size and degree in polynomial calculus

    Guillaume Lagarde, Jakob Nordström, Dmitry Sokolov & Joseph Swernofsky, 2020 jan, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020. Vidick, T. (red.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 72. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 151).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  31. Graph colouring is hard for algorithms based on hilbert's nullstellensatz and gröbner bases

    Massimo Lauria & Jakob Nordström, 2017 jul 1, 32nd Computational Complexity Conference, CCC 2017. O'Donnell, R. (red.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 79).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  32. CNFgen: A generator of crafted benchmarks

    Massimo Lauria, Jan Elffers, Jakob Nordström & Marc Vinyals, 2017, Theory and Applications of Satisfiability Testing – SAT 2017: 20th International Conference, Proceedings. Gaspers, S. & Walsh, T. (red.). Springer, s. 464-473 10 s. (Lecture Notes in Computer Science; vol. 10491).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  33. Tight Size-Degree Bounds for Sums-of-Squares Proofs

    Massimo Lauria & Jakob Nordström, 2017 dec 1, I: Computational Complexity. 26, 4, s. 911-948 38 s.

    Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskrift

  34. Tight size-degree bounds for sums-of-squares proofs

    Massimo Lauria & Jakob Nordström, 2015 jun 1, 30th Conference on Computational Complexity, CCC 2015. Zuckerman, D. (red.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, s. 448-466 19 s. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 33).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  35. Verifying Properties of Bit-vector Multiplication Using Cutting Planes Reasoning

    Vincent Liew, Paul Beame, Jo Devriendt, Jan Elffers & Jakob Nordstrom, 2020, Proceedings of the 20th Conference on Formal Methods in Computer-Aided Design, FMCAD 2020. Ivrii, A., Strichman, O., Hunt, W. A. & Weissenbacher, G. (red.). Institute of Electrical and Electronics Engineers Inc., s. 194-204 11 s. 9283622. (Proceedings of the 20th Conference on Formal Methods in Computer-Aided Design, FMCAD 2020).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  36. A generalized method for proving polynomial calculus degree lower bounds

    Mladen Mikša & Jakob Nordström, 2015 jun 1, 30th Conference on Computational Complexity, CCC 2015. Zuckerman, D. (red.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, s. 467-487 21 s. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 33).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  37. Long Proofs of (Seemingly) Simple Formulas

    Mladen Mikša & Jakob Nordström, 2014, Theory and Applications of Satisfiability Testing, SAT 2014: 17th International Conference, Held as Part of theVienna Summer of Logic, VSL 2014, Proceedings. Springer, s. 121-137 17 s. (Lecture Notes in Computer Science; vol. 8561).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  38. A (biased) proof complexity survey for SAT practitioners

    Jakob Nordström, 2014, Theory and Applications of Satisfiability Testing, SAT 2014: 17th International Conference, Held as Part of theVienna Summer of Logic, VSL 2014, Proceedings. Springer, s. 1-6 6 s. (Lecture Notes in Computer Science; vol. 8561).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  39. Pebble games, proof complexity, and time-space trade-offs

    Jakob Nordström, 2013 sep 13, I: Logical Methods in Computer Science. 9, 3, 15.

    Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskrift

  40. On the relative strength of pebbling and resolution

    Jakob Nordström, 2012 apr, I: ACM Transactions on Computational Logic. 13, 2, a16.

    Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskrift

  41. On minimal unsatisfiability and time-space trade-offs for k-DNF resolution

    Jakob Nordström & Alexander Razborov, 2011, Automata, Languages and Programming: 38th International Colloquium, ICALP 2011, Proceedings. PART 1 uppl. Springer, s. 642-653 12 s. (Lecture Notes in Computer Science; vol. 6755, nr. PART 1).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  42. On the relative strength of pebbling and resolution

    Jakob Nordström, 2010, Proceedings - 25th Annual IEEE Conference on Computational Complexity, CCC 2010. IEEE - Institute of Electrical and Electronics Engineers Inc., s. 151-162 12 s. 5497889. (Proceedings of the Annual IEEE Conference on Computational Complexity).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  43. A simplified way of proving trade-off results for resolution

    Jakob Nordström, 2009 aug 31, I: Information Processing Letters. 109, 18, s. 1030-1035 6 s.

    Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskrift

  44. Narrow proofs may be spacious: Separating space and width in resolution

    Jakob Nordström, 2009, I: SIAM Journal on Computing. 39, 1, s. 59-121 63 s.

    Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskrift

  45. Towards an optimal separation of space and length in resolution

    Jakob Nordström & Johan Håstad, 2008, STOC'08: Proceedings of the 2008 ACM Symposium on Theory of Computing. Association for Computing Machinery (ACM), s. 701-710 10 s. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  46. Narrow proofs may be spacious: Separating space and width in resolution

    Jakob Nordström, 2006, STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery (ACM), s. 507-516 10 s. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. 2006).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  47. Theoretical and Experimental Results for Planning with Learned Binarized Neural Network Transition Models

    Buser Say, Jo Devriendt, Jakob Nordström & Peter J. Stuckey, 2020, Principles and Practice of Constraint Programming - 26th International Conference, CP 2020, Proceedings. Simonis, H. (red.). Springer, s. 917-934 18 s. (Lecture Notes in Computer Science; vol. 12333).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  48. Simplified and Improved Separations Between Regular and General Resolution by Lifting

    Marc Vinyals, Jan Elffers, Jan Johannsen & Jakob Nordström, 2020, Theory and Applications of Satisfiability Testing – SAT 2020: 23rd International Conference, Proceedings. Pulina, L. & Seidl, M. (red.). Springer, s. 182-200 19 s. (Lecture Notes in Computer Science; vol. 12178).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

  49. In between resolution and cutting planes: A study of proof systems for pseudo-boolean SAT solving

    Marc Vinyals, Jan Elffers, Jesús Giráldez-Cru, Stephan Gocht & Jakob Nordströ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. (red.). Springer, s. 292-310 19 s. (Lecture Notes in Computer Science; vol. 10929).

    Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding