eng flag In English
bild
Skolan för
elektroteknik
och datavetenskap
KTH / EECS / TCS / Jakob Nordström / MIAO-gruppen

Vårt arbetsspråk är engelska, och denna sida finns därför enbart i engelsk version.

I have moved to the Department of Computer Science (DIKU) at the University of Copenhagen and also have a part-time affiliation with the Department of Computer Science at Lund University. For now, my webpages still reside at KTH, and are being updated here, but this should change during 2020.

MIAO group logo

Mathematical Insights into Algorithms for Optimization (MIAO) Group

Latest News

That 2020 has been a thrilling year is somewhat of an understatement, but for the MIAO group the first academic year at the University of Copenhagen and Lund University has been filled with excitement for all the right reasons!

Our works on designing state-of-the-art algorithms for combinatorial optimization problems, and making sure not only that such algorithms run fast but that we also understand how they perform and can prove that they produce correct results, have appeared in the premier AI conferences AAAI and IJCAI (3 papers), as well as in more specialized high-profile conferences on combinatorial optimization such as CP, CPAIOR, and SAT (6 papers), and on formal verification such as CAV and FMCAD (2 papers). On the flip side, research contributions focusing on understanding the limitations of such optimization algorithms, or of efficient computation in general, from a rigorous, mathematical point of view have been accepted to top theoretical computer science conferences such as STOC, FOCS, CCC, and ITCS (5 papers).

After this veritable explosion of 16 conference papers during 2020 (not counting journal papers and technical reports), we are not quite sure what to expect going forward, but so far it sure seems like the MIAO kitten is indeed enjoying life in the company of the big, friendly BARC dog

Briefly About the MIAO Research Group

The Mathematical Insights into Algorithms for Optimization (MIAO) research group is based on both sides of the Öresund Bridge at Lund University and the University of Copenhagen (where we are friendly neighbours with BARC).

Much of the activities of the group revolve around gaining a better theoretical understanding of powerful algorithmic paradigms such as, e.g., Boolean satisfiability (SAT) solving, Gröbner basis computations, integer linear programming, and/or semidefinite programming. This leads to classic questions in computational complexity theory — though often with new, interesting twists — but also involves work on designing new algorithms that can exploit the power of such paradigms in practice.

On the theory side, we focus on proof complexity, i.e., the study of formal systems for reasoning about logic formulas and other types of problems. Proof complexity has connections to foundational questions in computational complexity theory, but another important motivation is algorithm analysis. All algorithms use some kind of method of reasoning to compute solutions to problems, and proof complexity can be used to analyse the potential and limitations of such methods (and thereby of the algorithms using them). As often happens in theoretical computer science, our research on proof complexity has revealed deep, and often quite surprising, connections to other areas such as, e.g., circuit complexity, communication complexity, and hardness of approximation, and so we are also interested in such areas.

On the practical side, one problem of interest is to gain a better understanding of, and improve, the performance of current state-of-the-art SAT solvers based on conflict-driven clause learning (CDCL). We are even more interested in exploring new algebraic or geometric techniques, such as Gröbner bases or 0-1 integer linear programming (also known as pseudo-Boolean solving), that could potentially yield exponential improvements over CDCL. In particular, we are actively working on combining ideas from SAT solving and mixed integer linear programming (MIP) to construct a new 0-1 integer linear programming solver RoundingSat with the ultimate goal of going significantly beyond the current state of the art. In this context there also seems to be ample room for technology transfer with other related areas such as SMT solving and constraint programming (CP).

Quite recently, we have begun investigating how to verify the correctness of state-of-the-art algorithms for combinatorial optimization. Such algorithms are often highly complex, and even mature commercial solvers are known to sometimes produce wrong results. What we are working on is to redesign state-of-the-art combinatorial solvers to output not only solutions but also mathematical proofs that the claimed solutions are correct and optimal — proofs that require low overhead to generate, are very easy to check, and provide 100% formal guarantees.

Principal Investigator

Jakob Nordström

Researchers

BSc and MSc Students

Group Alumni

Long-Term Visitors

(Visitors for one month or more.)

  • Massimo Lauria, Universitat Politècnica de Catalunya, August-October 2016
  • Alexander Razborov, University of Chicago, March-April 2015
  • Ilario Bonacina, Sapienza – Università di Roma, January-May 2014
  • Navid Talebanfard, Aarhus University, January-March 2014
  • Yuval Filmus, University of Toronto, November-December 2012
  • Bangsheng Tang, Tsinghua University, January-February 2012
  • Chris Beck, Princeton University, January-February 2012
  • Trinh Huynh, University of Washington and ETH Zurich, August-September 2011

Short-Term Visitors

(Visitors since August 2019 received in Copenhagen and/or Lund. Visits planned for 2020 have so far been cancelled due to the Covid-19 pandemic.)

Funding

Our research have at different stages been generously funded by

  • a Junior Researcher Position Grant from the Swedish Research Council,
  • a Starting Independent Researcher Grant from the European Research Council,
  • a Breakthrough Research Grant from the Swedish Research Council,
  • a Grant for Research Projects with High Scientific Potential from the Knut and Alice Wallenberg Foundation (co-PI),
  • a Consolidator Grant from the Swedish Research Council,
  • a Postdoctoral Scholarship Program in Mathematics Grant from the Knut and Alice Wallenberg Foundation,
  • a Research project 2 grant from the Independent Research Fund Denmark.

Workshops

Workshops, seminar weeks, et cetera co-organized by Jakob Nordström:

Publications

Below follows a list of publications, sorted in reverse chronological order, emanating from the MIAO research group. As a general rule, these papers are copyright by their respective publishers but are free for personal use.

Please note that the list below is updated at somewhat irregular intervals and is currently seriously out-of-date. See www.csc.kth.se/~jakobn/research/ for a full list of Jakob Nordström's publications (which is updated much more frequently, but does not contain papers by other members of the group on which Jakob Nordström is not a co-author).

2018

  • Mika Göös, Pritish Kamath, Robert Robere, and Dmitry Sokolov. Adventures in Monotone Complexity and TFNP. Technical Report TR18-163, Electronic Colloquium on Computational Complexity (ECCC), September 2018. PDF
  • Jan Elffers and Jakob Nordström. Divide and Conquer: Towards Faster Pseudo-Boolean Solving. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI '18), pages 1291-1299, July 2018. PDF
  • Jan Elffers, Jesús Giráldez-Cru, Stephan Gocht, Jakob Nordström, and Laurent Simon. Seeking Practical CDCL Insights from Theoretical SAT Benchmarks. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI '18), pages 1300-1308, July 2018. PDF
  • Jan Elffers, Jesús Giráldez-Cru, Jakob Nordström, and Marc Vinyals. Using Combinatorial Benchmarks to Probe the Reasoning Power of Pseudo-Boolean Solvers. In Proceedings of the 21st International Conference on Theory and Applications of Satisfiability Testing (SAT '18), Lecture Notes in Computer Science, volume 10929, pages 75-93, July 2018. PDF
  • Marc Vinyals, Jan Elffers, Jesús Giráldez-Cru, Stephan Gocht, and Jakob Nordström. In Between Resolution and Cutting Planes: A Study of Proof Systems for Pseudo-Boolean SAT Solving. In Proceedings of the 21st International Conference on Theory and Applications of Satisfiability Testing (SAT '18), Lecture Notes in Computer Science, volume 10929, pages 292-310, July 2018. PDF
  • Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, and Alexander Razborov. Clique Is Hard on Average for Regular Resolution. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC '18), pages 866-877, June 2018. PDF
  • Ankit Garg, Mika Göös, Pritish Kamath, and Dmitry Sokolov. Monotone circuit lower bounds from resolution. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC '18), pages 902-911, June 2018. PDF
  • Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, and Sagnik Mukhopadhyay. Simulation Beats Richness: New Data-Structure Lower Bounds. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC '18), pages 1013-1020, June 2018. PDF
  • Sam Buss, Dmitry Itsykson, Alexander Knop, and Dmitry Sokolov. Reordering Rule Makes OBDD Proof Systems Stronger. In Proceedings of the 33rd Annual Computational Complexity Conference (CCC '17), Leibniz International Proceedings in Informatics (LIPIcs), volume 102, pages 16:1-16:24, June 2018. PDF

2017

  • Ilario Bonacina. Space in Weak Propositional Proof Systems. Springer, 2017. PDF
  • Massimo Lauria and Jakob Nordström. Tight Size-Degree Bounds for Sums-of-Squares Proofs. Computational Complexity, volume 26, issue 3, pages 911-948, December 2017. PDF
  • Ilario Bonacina and Navid Talebanfard. Strong ETH and Resolution via Games and the Multiplicity of Strategies. Algorithmica, volume 79, issue 1, pages 29-41, September 2017. PDF
  • Carlos Ansótegui, Maria Luisa Bonet, Jesús Giráldez-Cru, and Jordi Levy. Structure Features for SAT Instances Classification Journal of Applied Logic, volume 23, pages 27-39, September 2017. PDF
  • Jesús Giráldez-Cru and Jordi Levy. Locality in Random SAT Instances. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI '17), pages 638-644, August 2017. PDF
  • Massimo Lauria, Jan Elffers, Jakob Nordström, and Marc Vinyals. CNFgen: A Generator of Crafted Benchmarks. In Proceedings of the 20th International Conference on Theory and Applications of Satisfiability Testing (SAT '17), Lecture Notes in Computer Science, volume 10491, pages 464-473, August 2017. PDF
  • Guillaume Baud-Berthier, Jesús Giráldez-Cru, and Laurent Simon. On the Community Structure of Bounded Model Checking SAT Problems. In Proceedings of the 20th International Conference on Theory and Applications of Satisfiability Testing (SAT '17), Lecture Notes in Computer Science, volume 10491, pages 65-82, August 2017. PDF
  • Patrick Bennett, Ilario Bonacina, Nicola Galesi, Tony Huynh, Mike Molloy, and Paul Wollan. Space proof complexity for random 3-CNFs. Information and Computation, volume 255, part 1, pages 165-176, August 2017. PDF
  • Massimo Lauria and Jakob Nordström. Graph Colouring is Hard for Algorithms Based on Hilbert's Nullstellensatz and Gröbner Bases. In Proceedings of the 32nd Annual Computational Complexity Conference (CCC '17), Leibniz International Proceedings in Informatics (LIPIcs), volume 79, pages 2:1-2:20, July 2017. PDF
  • Massimo Lauria, Pavel Pudlák, Vojtěch Rödl and Neil Thapen. The Complexity of Proving That a Graph Is Ramsey. Combinatorica, volume 37, issue 2, pages 253-268, April 2017. PDF
  • Joël Alwen, Susanna F. de Rezende, Jakob Nordström, and Marc Vinyals. Cumulative Space in Black-White Pebbling and Resolution. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS '17), Leibniz International Proceedings in Informatics (LIPIcs), volume 67, pages 38:1-38:21, January 2017. PDF

2016

  • Christoph Berkholz and Jakob Nordström. Supercritical Space-Width Trade-offs for Resolution. Technical Report TR16-203, Electronic Colloquium on Computational Complexity (ECCC), December 2016. PDF
  • Susanna F. de Rezende, Jakob Nordström, and Marc Vinyals. How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity). In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS '16), pages 295-304, October 2016. PDF
  • Ilario Bonacina, Nicola Galesi, and Neil Thapen. Total Space in Resolution. SIAM Journal on Computing, volume 45, issue 5, pages 1894-1909, October 2016. PDF
  • Christoph Berkholz and Jakob Nordström. Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps. Technical Report TR16-135, Electronic Colloquium on Computational Complexity (ECCC), August 2016. PDF
  • Christoph Berkholz and Jakob Nordström. Supercritical Space-Width Trade-offs for Resolution. In Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP '16), Leibniz International Proceedings in Informatics (LIPIcs), volume 55, pages 57:1-57:14, July 2016. PDF
  • Ilario Bonacina. Total Space in Resolution Is at Least Width Squared. In Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP '16), Leibniz International Proceedings in Informatics (LIPIcs), volume 55, pages 56:1-56:13, July 2016. PDF
  • Jan Elffers, Jan Johannsen, Massimo Lauria, Thomas Magnard, Jakob Nordström, and Marc Vinyals. Trade-offs Between Time and Memory in a Tighter Model of CDCL SAT Solvers. In Proceedings of the 19th International Conference on Theory and Applications of Satisfiability Testing (SAT '16), Lecture Notes in Computer Science, volume 9710, pages 160-176, July 2016. PDF
  • Christoph Berkholz and Jakob Nordström. Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS '16), July 2016. PDF
  • Massimo Lauria. A Rank Lower Bound for Cutting Planes Proofs of Ramsey's Theorem. ACM Transactions on Computation Theory, volume 8, issue 4, article 17, June 2016. PDF
  • Albert Atserias, Massimo Lauria, and Jakob Nordström. Narrow Proofs May Be Maximally Long. In ACM Transactions on Computational Logic, volume 17, issue 3, article 19, May 2016. PDF
  • Yuval Filmus, Pavel Hrubeš, and Massimo Lauria. Semantic Versus Syntactic Cutting Planes. In Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS '16), pages 35:1-35:13, February 2016. PDF
  • Ilario Bonacina and Navid Talebanfard. Improving Resolution Width Lower Bounds for k-CNFs with Applications to the Strong Exponential Time Hypothesis. Information Processing Letters, volume 116, issue 2, pages 120-124, February 2016. PDF
  • Olaf Beyersdorff, Ilario Bonacina, and Leroy Chew. Lower Bounds: From Circuits to QBF Proof Systems. In Proceedings of the 7th Innovations in Theoretical Computer Science Conference (ITCS '16), pages 249-260, January 2016. PDF

2015

  • Siu Man Chan, Massimo Lauria, Jakob Nordström, and Marc Vinyals. Hardness of Approximation in PSPACE and Separation Results for Pebble Games (Extended Abstract). In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS '15), pages 466-485, October 2015. PDF
  • Ilario Bonacina and Navid Talebanfard. Strong ETH and Resolution via Games and the Multiplicity of Strategies. In Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC '15), Leibniz International Proceedings in Informatics (LIPIcs), volume 43, pages 248-257, September 2015. PDF
  • Yuval Filmus, Massimo Lauria, Jakob Nordström, Noga Ron-Zewi, and Neil Thapen. Space Complexity in Polynomial Calculus. SIAM Journal on Computing, volume 44, issue 4, pages 1119-1153, August 2015. PDF
  • Yuval Filmus, Massimo Lauria, Mladen Mikša, Jakob Nordström, and Marc Vinyals. From Small Space to Small Width in Resolution. ACM Transactions on Computational Logic, volume 16, issue 4, article 28, July 2015. PDF
  • Jakob Nordström. On the Interplay Between Proof Complexity and SAT Solving. ACM SIGLOG News, volume 2, number 3, pages 19-44, July 2015. PDF (Lightly edited version with some typos fixed.)
  • Massimo Lauria and Jakob Nordström. Tight Size-Degree Bounds for Sums-of-Squares Proofs. In Proceedings of the 30th Annual Computational Complexity Conference (CCC '15), Leibniz International Proceedings in Informatics (LIPIcs), volume 33, pages 448-466, June 2015. PDF
  • Mladen Mikša and Jakob Nordström. A Generalized Method for Proving Polynomial Calculus Degree Lower Bounds. In Proceedings of the 30th Annual Computational Complexity Conference (CCC '15), Leibniz International Proceedings in Informatics (LIPIcs), volume 33, pages 467-487, June 2015. PDF
  • Mladen Mikša and Jakob Nordström. A Generalized Method for Proving Polynomial Calculus Degree Lower Bounds. Technical Report TR15-078, Electronic Colloquium on Computational Complexity (ECCC), May 2015. PDF
  • Massimo Lauria and Jakob Nordström. Tight Size-Degree Bounds for Sums-of-Squares Proofs. Technical Report TR15-053, Electronic Colloquium on Computational Complexity (ECCC), April 2015. PDF

2014

  • Jakob Nordström. A (Biased) Proof Complexity Survey for SAT Practitioners. In Proceedings of the 17th International Conference on Theory and Applications of Satisfiability Testing (SAT '14), Lecture Notes in Computer Science, volume 8561, pages 1-6, July 2014. PDF
  • Mladen Mikša and Jakob Nordström. Long Proofs of (Seemingly) Simple Formulas. In Proceedings of the 17th International Conference on Theory and Applications of Satisfiability Testing (SAT '14), Lecture Notes in Computer Science, volume 8561, pages 121-137, July 2014. PDF
  • Albert Atserias, Massimo Lauria, and Jakob Nordström. Narrow Proofs May Be Maximally Long (Extended Abstract). In Proceedings of the 29th Annual IEEE Conference on Computational Complexity (CCC '14), pages 286-297, June 2014. PDF
  • Yuval Filmus, Massimo Lauria, Mladen Mikša, Jakob Nordström, and Marc Vinyals. From Small Space to Small Width in Resolution. In Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS '14), pages 300-311, March 2014. PDF

2013

  • Jakob Nordström. Pebble Games, Proof Complexity, and Time-Space Trade-offs. Logical Methods in Computer Science, volume 9, issue 3, article 15, September 2013. PDF
  • Olaf Beyersdorff, Nicola Galesi, and Massimo Lauria. A Characterization of Tree-Like Resolution Size. In Information Processing Letters, volume 113, number 18, pages 666-671, September 2013. PDF
  • Olaf Beyersdorff, Nicola Galesi, and Massimo Lauria. Parameterized Complexity of DPLL Search Procedures In ACM Transactions on Computational Logic, volume 14, issue 3, article 23, August 2013. PDF
  • Massimo Lauria. A Rank Lower Bound for Cutting Planes Proofs of Ramsey Theorem. In Proceedings of the 16th International Conference on Theory and Applications of Satisfiability Testing (SAT '13), pages 351-364, July 2013. PDF
  • Yuval Filmus, Massimo Lauria, Mladen Mikša, Jakob Nordström, and Marc Vinyals. Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds (Extended Abstract). In Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP '13), Lecture Notes in Computer Science, volume 7965, pages 437-448, July 2013. PDF
  • Massimo Lauria, Pavel Pudlak, Vojtěch Rödl, and Neil Thapen. The Complexity of Proving That a Graph Is Ramsey. In Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP '13), Lecture Notes in Computer Science, volume 7965, pages 684-695, July 2013. PDF
  • Chris Beck, Jakob Nordström, and Bangsheng Tang. Some Trade-off Results for Polynomial Calculus (Extended Abstract). In Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC '13), pages 813-822, June 2013. PDF
  • Jakob Nordström and Johan Håstad. Towards an Optimal Separation of Space and Length in Resolution. Theory of Computing, volume 9, article 14, pages 471-557, May 2013. PDF

2012

  • Yuval Filmus, Massimo Lauria, Jakob Nordström, Noga Ron-Zewi, and Neil Thapen. Space Complexity in Polynomial Calculus. Technical Report TR12-132, Electronic Colloquium on Computational Complexity (ECCC), October 2012. PDF
  • Matti Järvisalo, Arie Matsliah, Jakob Nordström, and Stanislav Živný. Relating Proof Complexity Measures and Practical Hardness of SAT. In Proceedings of the 18th International Conference on Principles and Practice of Constraint Programming (CP '12), pages 316-331, October 2012. PDF
  • Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, and Alexander A. Razborov. Parameterized Bounded-depth Frege Is Not Optimal. In ACM Transaction on Computational Theory, volume 4, issue 3, article 7, September 2012. PDF
  • Yuval Filmus, Massimo Lauria, Jakob Nordström, Neil Thapen, and Noga Ron-Zewi. Space Complexity in Polynomial Calculus (Extended Abstract). In Proceedings of the 27th Annual IEEE Conference on Computational Complexity (CCC '12), pages 334-344, June 2012. PDF
  • Trinh Huynh and Jakob Nordström. On the Virtue of Succinct Proofs: Amplifying Communication Complexity Hardness to Time-Space Trade-offs in Proof Complexity (Extended Abstract). In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC '12), pages 233-248, May 2012. PDF
  • Jakob Nordström. On the Relative Strength of Pebbling and Resolution. ACM Transactions on Computational Logic, volume 13, issue 2, article 16, April 2012. PDF

2011

  • Jakob Nordström and Alexander Razborov. On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution. In Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP '11), Lecture Notes in Computer Science, volume 6755, pages 642-653, July 2011. PDF
  • Eli Ben-Sasson and Jakob Nordström. Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions (Extended Abstract). In Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS '11), pages 401-416, January 2011. PDF
Sidansvarig: Jakob Nordström <jakobn~at-sign~kth~dot~se>
Uppdaterad 2020-07-20