Jakob Nordström
Professor
- Udgivet
Proof Complexity and SAT Solving
Buss, S. & Nordström, Jakob, 2021, Handbook of Satisfiability. Biere, A., Heule, M. J. H., van Maaren, H. & Walsh, T. (red.). 2 udg. IMIA and IOS Press, s. 233 - 350 (Frontiers in Artificial Intelligence and Applications, Bind 336).Publikation: Bidrag til bog/antologi/rapport › Bidrag til bog/antologi › Forskning › fagfællebedømt
Pebble games, proof complexity, and time-space trade-offs
Nordström, Jakob, 13 sep. 2013, I: Logical Methods in Computer Science. 9, 3, 15.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
On the relative strength of pebbling and resolution
Nordström, Jakob, apr. 2012, I: ACM Transactions on Computational Logic. 13, 2, a16.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
- Udgivet
On the relative strength of pebbling and resolution
Nordström, Jakob, 2010, Proceedings - 25th Annual IEEE Conference on Computational Complexity, CCC 2010. s. 151-162 12 s. 5497889. (Proceedings of the Annual IEEE Conference on Computational Complexity).Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
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 maj 2012, Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC '12). Association for Computing Machinery, Inc., s. 233-248 16 s.Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
On the Interplay Between Proof Complexity and SAT Solving
Nordström, Jakob, 1 jul. 2015, I: ACM SIGLOG News. 2, 3, s. 19-44 26 s.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
- Udgivet
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 udg. s. 642-653 12 s. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Nr. PART 1, Bind 6755 LNCS).Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
- Udgivet
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. (red.). International Joint Conferences on Artificial Intelligence, s. 1711-1718Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
- Udgivet
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, Bind 137. s. 1-16 18. (Leibniz International Proceedings in Informatics, LIPIcs, Bind 137).Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
- Udgivet
Near-optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps
Berkholz, C. & Nordström, Jakob, 2023, I: Journal of the ACM. 70, 5, s. 1-32 32.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
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., s. 267-276 10 s. (Proceedings - Symposium on Logic in Computer Science, Bind 05-08-July-2016).Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
- Udgivet
Narrow proofs may be spacious: Separating space and width in resolution
Nordström, Jakob, 2009, I: SIAM Journal on Computing. 39, 1, s. 59-121 63 s.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
- Udgivet
Narrow proofs may be spacious: Separating space and width in resolution
Nordström, Jakob, 2006, STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing. s. 507-516 10 s. (Proceedings of the Annual ACM Symposium on Theory of Computing, Bind 2006).Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Narrow proofs may be maximally long
Atserias, A., Lauria, M. & Nordström, Jakob, feb. 2016, I: ACM Transactions on Computational Logic. 17, 3, 19.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Narrow proofs may be maximally long
Atserias, A., Lauria, M. & Nordström, Jakob, 2014, Proceedings - IEEE 29th Conference on Computational Complexity, CCC 2014. IEEE Computer Society Press, s. 286-297 12 s. 6875497. (Proceedings of the Annual IEEE Conference on Computational Complexity).Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
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, s. 121-137 17 s. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bind 8561 LNCS).Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
- Udgivet
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, s. 24-30Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
- Udgivet
Learn to Relax: Integrating 0-1 Integer Linear Programming with Pseudo-Boolean Conflict-Driven Search
Devriendt, J., Gleixner, A. & Nordström, Jakob, 2021, I: Constraints. 26, s. 26–55 30 s.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
- Udgivet
KRW Composition Theorems via Lifting
de Rezende, S., Meir, O., Nordström, Jakob, Pitassi, T. & Robere, R., 1 nov. 2020, Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS '20). IEEE, s. 4149Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
- Udgivet
Justifying All Differences Using Pseudo-Boolean Reasoning
Elffers, J., Gocht, S., McCreesh, C. & Nordström, Jakob, 1 feb. 2020, Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI '20). AAAI Press, s. 1486-1494 9 s.Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
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. (red.). Springer Verlag, s. 292-310 19 s. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bind 10929 LNCS).Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
- Udgivet
Improving Conflict Analysis in MIP Solvers by Pseudo-Boolean Reasoning
Mexi, G., Berthold, T., Gleixner, A. & Nordström, Jakob, 2023, 29th International Conference on Principles and Practice of Constraint Programming, CP 2023. Yap, R. H. C. Y. (red.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 19 s. 27. (Leibniz International Proceedings in Informatics, LIPIcs, Bind 280).Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Hardness of Approximation in PSPACE and Separation Results for Pebble Games (Extended Abstract)
Chan, S. M., Lauria, M., Nordström, Jakob & Vinyals, M., 1 okt. 2015, Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS~'15). IEEE, s. 466-485 20 s.Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Graph colouring is hard for algorithms based on hilbert's nullstellensatz and gröbner bases
Lauria, M. & Nordström, Jakob, 1 jul. 2017, 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, Bind 79).Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
- Udgivet
Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
Conneryd, J., de Rezende, S. F., Nordström, Jakob, Pang, Shuo & Risse, K., 2023, Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023. IEEE Computer Society Press, 11 s. 45. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
ID: 209376262
Flest downloads
-
69
downloads
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Udgivet -
33
downloads
Exponential resolution lower bounds for weak pigeonhole principle and perfect matching formulas over sparse graphs
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Udgivet -
25
downloads
Verifying Properties of Bit-vector Multiplication Using Cutting Planes Reasoning
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Udgivet