Conferences & Workshops

2023
  1. Alexander Shleyfman, Daniel Gnad, and Peter Jonsson: Structurally Restricted Fragments of Numeric Planning - A Complexity Analysis. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI-2023), Washington, DC, USA, Feb, 2023. To appear.

  2. Konrad Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, and Magnus Wahlström: Almost Consistent Systems of Linear Equations. In Proceedings of the 34th ACM-SIAM Symposium on Discrete Algorithms (SODA-2023), Firenze, Italy, Jan, 2023. To appear.
2022
  1. Alexander Shleyfman, Daniel Gnad, and Peter Jonsson: New Complexity Results for Structurally Restricted Numeric Planning. In Proceedings of the 2022 Workshop on Heuristics and Search for Domain-independent Planning, virtual event, 2022. To appear.

  2. Konrad Dabrowski, Peter Jonsson, Sebastian Ordyniak, and George Osipov: Resolving Inconsistencies in Simple Temporal Problems: A Parameterized Approach. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI-2022), Vancouver, Canada, Feb-Mar, 2022. To appear.
2021
  1. Peter Jonsson, Victor Lagerkvist, and Sebastian Ordyniak: Reasoning Short Cuts in Infinite Domain Constraint Satisfaction: Algorithms and Lower Bounds for Backdoors. In Proceedings of the 27th International Conference on Principles and Practice of Constraint Programming (CP-2021), pp: 32:1-32:20, virtual event, Oct, 2021.

  2. Konrad Dabrowski, Peter Jonsson, Sebastian Ordyniak, and George Osipov: Solving Infinite-Domain CSPs Using the Patchwork Property. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI-2021), pp. 3715-3723, virtual event, Feb, 2021. temporary link

  3. Konrad Dabrowski, Peter Jonsson, Sebastian Ordyniak, and George Osipov: Disjunctive Temporal Problems under Structural Restrictions. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI-2021), pp. 3724-3732, virtual event, Feb, 2021. temporary link
2020
  1. Konrad Dabrowski, Peter Jonsson, Sebastian Ordyniak, and George Osipov: Fine-Grained Complexity of Temporal Problems. In Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning (KR-2020), pp. 284-293, Rhodes, Greece, Sep, 2020. link

  2. Peter Jonsson and Victor Lagerkvist: Lower Bounds and Faster Algorithms for Equality Constraints. In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI-2020), pp. 1784-1790, Yokohama, Japan, 2020. link
2019
  1. Christer Bäckström, Peter Jonsson, and Sebastian Ordyniak: A Refined Understanding of Cost-optimal Planning with Polytree Causal Graphs. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI-2019), pp. 6126-6130, Macao, China, Aug, 2019. link
2018
  1. Peter Jonsson and Victor Lagerkvist: Why are CSPs Based on Partition Schemes Computationally Hard? In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS-2018), pp. 43:1-43:15. Liverpool, UK, Aug, 2018. link

  2. Christer Bäckström, Peter Jonsson, and Sebastian Ordyniak: A Refined Understanding of Cost-optimal Planning with Polytree Causal Graphs. In Proceedings of the 11th Annual Symposium on Combinatorial Search (SoCS-2018), pp. 19-27. Stockholm, Sweden, Jul, 2018. link

  3. Christer Bäckström, Peter Jonsson, and Sebastian Ordyniak: Novel Structural Parameters for Acyclic Planning Using Tree Embeddings. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI-2018), pp. 4653-4659. Stockholm, Sweden, Jul, 2018. link

  4. Manuel Bodirsky, Peter Jonsson, Barnaby Martin, and Antoine Mottet: Classification Transfer for Qualitative Reasoning Problems. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI-2018), pp. 1256-1262. Stockholm, Sweden, Jul, 2018. pdf (report version)

2017
  1. Peter Jonsson, Victor Lagerkvist, and Biman Roy: Time Complexity of Constraint Satisfaction via Universal Algebra. In Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS-2017), pp. 17:1-17:15. Aalborg, Denmark, Aug, 2017. pdf (report version)

2016
  1. Peter Jonsson: Finite Unary Relations and Qualitative Constraint Satisfaction. In Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI-2016), pp. 37-45. The Hague, Holland, Aug-Sep, 2016. link

  2. Meysam Aghighi, Christer Bäckström, Peter Jonsson, and Simon Ståhlberg: Analysing Approximability and Heuristics in Planning Using the Exponential-time Hypothesis. In Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI-2016), pp. 184-192. The Hague, Holland, Aug-Sep, 2016. link

  3. Christer Bäckström and Peter Jonsson: Upper and Lower Time and Space Bounds for Planning. In Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI-2016), pp. 716-724. The Hague, Holland, Aug-Sep, 2016. link

  4. Christian Glaßer, Peter Jonsson, and Barnaby Martin: Circuit Satisfiability and Constraint Satisfaction Problems around Skolem Arithmetic. In Proceedings of the 12th Conference on Computability in Europe (CiE-2016), pp. 323-332. Paris, France, Jul, 2016. pdf

  5. Manuel Bodirsky, Peter Jonsson, and Trung Van Pham: The Complexity of Phylogeny Constraint Satisfaction. In Proceedings of the 33rd International Symposium on Theoretical Aspects of Computer Science (STACS-2016), pp. 20:1-20:13. Orléans, France, Feb, 2016. pdf

2015
  1. Peter Jonsson and Victor Lagerkvist: Upper and Lower Bounds on the Time Complexity of Infinite-domain CSPs. In Proceedings of the 21st International Conference on Principles and Practice of Constraint Programming (CP-2015), pp. 183-199. Cork, Ireland, Aug-Sep, 2015. pdf

  2. Meysam Aghighi, Peter Jonsson, and Simon Ståhlberg: Tractable Cost-optimal Planning over Restricted Polytree Causal Graphs. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI-2015), pp. 3225-3231. Austin, Texas, USA, Jan, 2015. link
2014
  1. Peter Jonsson, Victor Lagerkvist, Johannes Schmidt, and Hannes Uppman: Relating the Time Complexity of Optimization Problems in Light of the Exponential-time Hypothesis. In Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS-2014), pp. 408-419. Budapest, Hungary, Aug, 2014. pdf

  2. Peter Jonsson and Johan Thapper: Affine Consistency and the Complexity of Semilinear Constraints. In Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS-2014), pp. 420-431. Budapest, Hungary, Aug, 2014. pdf

  3. Meysam Aghighi and Peter Jonsson: Oversubscription Planning: Complexity and Compilability. In Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI-2014), pp. 2221-2227. Quebéc City, Quebéc, Canada, Jul, 2014. link

2013
  1. Peter Jonsson, Victor Lagerkvist, and Gustav Nordh: Blowing Holes in Various Aspects of Computational Problems, with Applications to Constraint Satisfaction. In Proceedings of the 19th International Conference on Principles and Practice of Constraint Programming (CP-2013), pp. 398-414. Uppsala, Sweden, Sep, 2013. pdf

  2. Christer Bäckström and Peter Jonsson: Bridging the Gap Between Refinement and Heuristics in Abstraction. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI-2013), pp. 2261-2267. Beijing, China, Aug, 2013. pdf

  3. Christer Bäckström, Peter Jonsson, and Simon Ståhlberg: Fast Detection of Unsolvable Planning Instances Using Local Consistency. In Proceedings of the 6th Annual Symposium on Combinatorial Search (SoCS-2013), 29-37. Leavenworth, WA, USA, Jul, 2013. pdf

  4. Anders Jonsson, Peter Jonsson, and Tomas Lööw: When Acyclicity is Not Enough: Limitations of the Causal Graph. In Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS-2013). Rome, Italy, Jun, 2013. pdf

  5. Christer Bäckström, Peter Jonsson, Sebastian Ordyniak, and Stefan Szeider: Parameterized Complexity and Kernel Bounds for Hard Planning Problems. In Proceedings of the 8th International Conference on Algorithms and Complexity (CIAC-2013), pp. 13-24. Barcelona, Spain, May, 2013. pdf

  6. Peter Jonsson, Victor Lagerkvist, Gustav Nordh, and Bruno Zanuttini: Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2013), pp. 1264-1277. New Orleans, LA, USA, Jan, 2013. pdf
2012
  1. Christer Bäckström, Anders Jonsson, and Peter Jonsson: From Macro Plans to Automata Plans. In Proceedings of the 20th European Conference on Artificial Intelligence (ECAI-2012), pp. 91-96. Montpellier, France, Aug, 2012. pdf

  2. Christer Bäckström, Anders Jonsson, and Peter Jonsson: Macros, Reactive Plans and Compact Representations. In Proceedings of the 20th European Conference on Artificial Intelligence (ECAI-2012), pp. 85-90. Montpellier, France, Aug, 2012. pdf

  3. Christer Bäckström and Peter Jonsson: Abstracting Abstraction in Search II: Complexity Analysis. In Proceedings of the 5th Annual Symposium on Combinatorial Search (SoCS-2012), pp. 10-17. Niagara Falls, Canada, Jul, 2012. pdf

  4. Christer Bäckström, Yue Chen, Peter Jonsson, Sebastian Ordyniak, and Stefan Szeider: The Complexity of Planning Revisited - A Parameterized Analysis. In Proceedings of the 26th (US) National Conference on Artificial Intelligence (AAAI-2012), pp. 1735-1741. Toronto, Canada, Jul, 2012. pdf

  5. Christer Bäckström and Peter Jonsson: Abstracting Abstraction in Search with Applications to Planning. In Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR-2012), pp. 446-456. Rome, Italy, Jun, 2012. pdf

2011
  1. Peter Jonsson, Fredrik Kuivinen, and Johan Thapper: Min CSP on Four Elements: Moving Beyond Submodularity. In Proceedings of the 17th International Conference on Principles and Practice of Constraint Programming (CP-2011), pp. 438-453. Perugia, Italy, Sep, 2011. pdf

  2. Christer Bäckström and Peter Jonsson: All PSPACE-complete Planning Problems are Equal but some are more Equal than Others. In Proceedings of the 4th Annual Symposium on Combinatorial Search (SoCS-2011), pp. 10-17. Barcelona, Spain, Jul, 2011. pdf

  3. Peter Jonsson and Tomas Lööw: Discrete-time Temporal Reasoning with Horn DLRs. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI-2011), pp. 931-936. Barcelona, Spain, Jul, 2011. pdf

  4. Christer Bäckström and Peter Jonsson: Limits for Compact Representations of Plans. In Proceedings of the 21st International Conference on Automated Planning and Scheduling (ICAPS-2011), pp. 18-25. Freiburg, Germany, Jun, 2011. pdf

2009
  1. Peter Jonsson and Johan Thapper: Approximability of the Maximum Solution Problem for Certain Families of Algebras. In Proceedings of the 4th International Computer Science Symposium in Russia (CSR-2009), pp. 215-226, Novosibirsk, Russia, Aug, 2009. pdf

  2. Tommy Färnqvist, Peter Jonsson, and Johan Thapper: Approximability Distance in the Space of H-Colourability Problems. In Proceedings of the 4th International Computer Science Symposium in Russia (CSR-2009), pp. 92-104, Novosibirsk, Russia, Aug, 2009. pdf

  3. Manuel Bodirsky, Peter Jonsson, and Timo von Oertzen: Semilinear Program Feasibility. In Proceedings of the 36th International Colloquium on Automata, Languages, and Programming (ICALP-2009), pp. 79-90, Rhodes, Greece, Jul, 2009.

2007
  1. Tommy Färnqvist and Peter Jonsson: Bounded Tree-width and CSP-related Problems. In Proceedings of the 18th International Symposium on Algorithms and Computation (ISAAC-2007), pp. 632-643, Sendai, Japan, Dec, 2007. pdf

  2. Peter Jonsson, Andrei Krokhin, and Fredrik Kuivinen: Ruling out Polynomial-time Approximation Schemes for Hard Constraint Satisfaction Problems. In Proceedings of the 2nd International Computer Science Symposium in Russia (CSR-2007), pp. 182-193, Ekaterinburg, Russia, Sep, 2007. pdf

  3. Peter Jonsson, Gustav Nordh, and Johan Thapper: The Maximum Solution Problem on Graphs. In Proceedings of the 32nd International Symposium on Mathematical Foundations of Computer Science (MFCS-2007), pp. 228-239, Ceský Krumlov, Czech Republic, Aug, 2007. pdf
2006
  1. Peter Jonsson, Fredrik Kuivinen, and Gustav Nordh: Approximability of Integer Programming with Generalised Constraints. In Proceedings of the 12th International Conference on Principles and Practice of Constraint Programming (CP-2006), pp. 256-270, Nantes, France, Sep, 2006. postscript (report version)

  2. Peter Jonsson and Gustav Nordh: Generalised Integer Programming Based on Logically Defined Relations. In Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS-2006), pp. 549-560, Stará Lesná, Slovakia, Aug-Sep, 2006. pdf

2005
  1. Vladimir Deineko, Peter Jonsson, Mikael Klasson, and Andrei Krokhin: Supermodularity on Chains and Complexity of Maximum Constraint Satisfaction Problems. In Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroCOMB-2005), pp. 51-56, Berlin, Germany, Sep, 2005. postscript

2004
  1. Gustav Nordh and Peter Jonsson: The Complexity of Counting Solutions to Systems of Equations Over Finite Semigroups. In Proceedings of the 10th Annual International Computing and Combinatorics Conference (COCOON-2004), pp. 370-379, Jeju Island, Korea, Aug, 2004. postscript

  2. Gustav Nordh and Peter Jonsson: An Algebraic Approach to the Complexity of Propositional Circumscription. In Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS-2004), pp. 367-376, Turku, Finland, Jul, 2004. postscript
2003
  1. Ola Angelsmark and Peter Jonsson: Improved Algorithms for Counting Solutions in Constraint Satisfaction Problems. In Proceedings of the 9th International Conference on Principles and Practice of Constraint Programming (CP-2003), pp. 81-95, Kinsale, County Cork, Ireland, Sep-Oct, 2003. postscript
2002
  1. Ola Angelsmark, Peter Jonsson, Svante Linusson, and Johan Thapper: Determining the Number of Solutions to Binary CSP Instances. In Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming (CP-2002), pp. 327-340, Ithaca, NY, USA, Sep, 2002. postscript

  2. Ola Angelsmark, Vilhelm Dahllöf, and Peter Jonsson: Finite Domain Constraint Satisfaction Using Quantum Computation. In Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science (MFCS-2002), pp. 93-103, Warsaw-Otwock, Poland, Aug, 2002. postscript

  3. Vilhelm Dahllöf, Peter Jonsson, and Magnus Wahlström: Counting Satisfying Assignments in 2-SAT and 3-SAT. In Proceedings of the 8th Annual International Computing and Combinatorics Conference (COCOON-2002), pp. 535-543, Singapore, Aug, 2002. postscript

  4. Andrei Krokhin and Peter Jonsson: Extending the Point Algebra into the Qualitative Algebra. In Proceedings of the 9th International Symposium on Temporal Representation and Reasoning (TIME-2002), pp. 28-35, Manchester, UK, Jul, 2002. postscript

  5. Andrei Krokhin, Peter Jeavons, and Peter Jonsson: The Complexity of Constraints on Intervals and Lengths. In Proceedings of the 19th International Symposium on Theoretical Aspects of Computer Science (STACS-2002), pp. 443-454, Antibes Juan-les-Pins, France, Mar, 2002. postscript

  6. Vilhelm Dahllöf and Peter Jonsson: An Algorithm for Counting Maximum Weighted Independent Sets and its Applications. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2002), pp. 292-298, San Francisco, CA, USA, Jan, 2002. postscript
2001
  1. Andrei Krokhin, Peter Jeavons, and Peter Jonsson: A Complete Classification of Complexity in Allen's Algebra in the Presence of a Non-Trivial Basic Relation. In Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI-01), pp. 83-88, Seattle, WA, USA, Aug, 2001. postscript

2000
  1. Mathias Broxvall, Peter Jonsson, and Jochen Renz: Refinements and Independence: A Simple Method for Identifying Tractable Disjunctive Constraints. In Proceedings of the 6th International Conference on Principles and Practice of Constraint Programming (CP-2000), pp. 114-127, Singapore, Sep, 2000. postscript

  2. Ola Angelsmark and Peter Jonsson: Some Observations on Durations, Scheduling and Allen's Algebra. In Proceedings of the 6th International Conference on Principles and Practice of Constraint Programming (CP-2000), pp. 484-488, Singapore, Sep, 2000. postscript-long version

  3. Mathias Broxvall and Peter Jonsson: Disjunctive Temporal Reasoning in Partially Ordered Time Structures. In Proceedings of the 17th (US) National Conference on Artificial Intelligence (AAAI-2000), pp. 464-469, Austin, TX, USA, Jul-Aug, 2000. postscript

  4. Patrik Haslum and Peter Jonsson: Planning with Reduced Operator Sets. In Proceedings of the 5th International Conference on Artificial Intelligence Planning and Scheduling (AIPS-2000), pp. 150-158, Breckenridge, CO, USA, Apr, 2000. postscript

1999
  1. Mathias Broxvall and Peter Jonsson: Towards a Complete Classification of Tractability in Point Algebras for Nonlinear Time. In Proceedings of the 5th International Conference on Principles and Practice of Constraint Programming (CP-99), pp. 129-143, Alexandria, VA, USA, Oct, 1999. postscript

  2. Marcus Bjäreland and Peter Jonsson: Exploiting Bipartiteness to Identify Yet Another Tractable Subclass of CSP. In Proceedings of the 5th International Conference on Principles and Practice of Constraint Programming (CP-99), pp. 118-128, Alexandria, VA, USA, Oct, 1999. postscript

  3. Patrik Haslum and Peter Jonsson: Some Results on the Complexity of Planning with Incomplete Information. In Proceedings of the 5th European Conference on Planning (ECP-99), Durham, UK, Sep, 1999. postscript

1997


  1. Thomas Drakengren and Peter Jonsson: Towards a Complete Classification of Tractability in Allen's Algebra. In Proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI-97), pp. 1466-1471, Nagoya, Japan, Aug, 1997. postscript

1996
  1. Inger Klein, Peter Jonsson, and Christer Bäckström: Automatic Synthesis of Control Programs in Polynomial Time for an Assembly Line. In Proceedings of the IEEE Conference on Decision and Control (CDC-96), Kobe, Japan, Dec, 1996. postscript

  2. Peter Jonsson, Thomas Drakengren, and Christer Bäckström: Tractable Subclasses of the Point-Interval Algebra: A Complete Classification. In Proceedings of the 5th International Conference on Principles on Knowledge Representation and Reasoning (KR-96), pp. 352-363, Cambridge, MA, USA, Oct, 1996. note

  3. Thomas Drakengren and Peter Jonsson: Tractable Subclasses of Allen's Interval Algebra: Preliminary Report. In Proceedings of the 13th (US) National Conference on Artificial Intelligence (AAAI-96), pp. 389-394, Portland, OR, USA, Aug, 1996. postscript

  4. Peter Jonsson and Christer Bäckström: A Linear-Programming Approach to Temporal Reasoning. In Proceedings of the 13th (US) National Conference on Artificial Intelligence (AAAI-96), pp. 1235-1240, Portland, OR, USA, Aug, 1996. postscript

  5. Peter Jonsson and Christer Bäckström: On the Size of Reactive Plans. In Proceedings of the 13th (US) National Conference on Artificial Intelligence (AAAI-96), pp. 1182-1187, Portland, OR, USA, Aug, 1996. postscript

  6. Peter Jonsson and Christer Bäckström: Tractable Plan Existence Does Not Imply Tractable Plan Generation. In 4th International Symposium of AI and Mathematics, Ft. Lauderdale, FL, USA, Jan., 1996. postscript

1995
  1. Peter Jonsson and Christer Bäckström: Incremental Planning. In New Directions in AI Planning: EWSP'95-3rd European Workshop on Planning, pp. 79-90, Assisi, Italy, Sep, 1995. postscript

  2. Inger Klein, Peter Jonsson, and Christer Bäckström: Tractable Planning for an Assembly Line. In New Directions in AI Planning: EWSP'95-3rd European Workshop on Planning, pp. 313-324, Assisi, Italy, Sep, 1995. postscript

  3. Christer Bäckström and Peter Jonsson: Planning with Abstraction Hierarchies can be Exponentially Less Efficient. In Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI-95), Montreal, PQ, Canada, Aug, 1995. postscript

1994
  1. Peter Jonsson and Christer Bäckström: Complexity Results for State-Variable Planning under Mixed Syntactical and Structural Restrictions. In Proceedings of the 6th International Conference on Artificial Intelligence: Methodology, Systems, Applications (AIMSA-94), Sofia, Bulgaria, Sep, 1994. postscript

  2. Peter Jonsson and Christer Bäckström: Tractable Planning with State Variables by Exploiting Structural Restrictions. In Proceedings of the 12th (US) National Conference on Artificial Intelligence (AAAI-94), pp. 998-1003, Seattle, WA, USA, Jul-Aug, 1994. postscript