Jakob Nordström
Professor
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. (red.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, (Leibniz International Proceedings in Informatics, LIPIcs, Bind 67).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, 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
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
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. (red.). ACM Association for Computing Machinery, s. 646-659 14 s. (Proceedings of the Annual ACM Symposium on Theory of Computing).Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
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. s. 813-822 10 s. (Proceedings of the Annual ACM Symposium on Theory of Computing).Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
- Udgivet
Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions
Ben-Sasson, E. & Nordström, Jakob, 1 aug. 2010.Publikation: Working paper › Forskning
- Udgivet
A Space Hierarchy for $k$-DNF Resolution
Ben-Sasson, E. & Nordström, Jakob, 1 apr. 2009.Publikation: Working paper › Forskning
- Udgivet
Short proofs may be spacious: An optimal separation of space and length in resolution
Ben-Sasson, E. & Nordström, Jakob, 2008, Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008. s. 709-718 10 s. 4691003. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
- E-pub ahead of print
Certified Core-Guided MaxSAT Solving
Berg, J., Bogaerts, B., Nordström, Jakob, Oertel, A. & Vandesande, D., 2023, (E-pub ahead of print) Automated Deduction – CADE 29 - 29th International Conference on Automated Deduction, Proceedings. Pientka, B. & Tinelli, C. (red.). Springer Science and Business Media Deutschland GmbH, s. 1-22 22 s. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bind 14132 LNAI).Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › 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
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. (red.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 57. (Leibniz International Proceedings in Informatics, LIPIcs, Bind 55).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
- Udgivet
Supercritical space-width trade-offs for resolution
Berkholz, C. & Nordström, Jakob, 2020, I: SIAM Journal on Computing. 49, 1, s. 98-118Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
- Udgivet
Separations of Matroid Freeness Properties
Bhattacharyya, A., Grigorescu, E., Nordström, Jakob & Xie, N., 1 aug. 2010.Publikation: Working paper › Forskning
- Udgivet
Certified Dominance and Symmetry Breaking for Combinatorial Optimisation
Bogaerts, B., Gocht, S., McCreesh, C. & Nordström, Jakob, 2023, I: Journal of Artificial Intelligence Research. 77, s. 1539-1589 51 s.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
- 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
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
- 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
- Udgivet
Automating algebraic proof systems is NP-hard
De Rezende, S. F., Göös, M., Nordström, Jakob, Pitassi, T., Robere, R. & Sokolov, D., 2021, STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Khuller, S. & Williams, V. V. (red.). Association for Computing Machinery, Inc., s. 209-222Publikation: 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
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. (red.). Springer Verlag, s. 160-176 17 s. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bind 9710).Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
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. (red.). International Joint Conferences on Artificial Intelligence, s. 1300-1308 9 s. (IJCAI International Joint Conference on Artificial Intelligence, Bind 2018-July).Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
- Udgivet
A Cardinal Improvement to Pseudo-Boolean Solving
Elffers, J. & Nordström, Jakob, 1 feb. 2020, Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI '20). AAAI Press, s. 1495-1503 9 s.Publikation: 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
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. (red.). Springer Verlag, s. 75-93 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
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