This projected ended on Sep 30, 2020

Funded by    

  ERC_banner.jpg       EC-H2020-banner.jpg

Description of the project

AUTAR: A Unified Theory of Algorithmic Relaxations is an ERC CoG (Consolidator Grant) action led by Albert Atserias at Universitat Politècnica de Catalunya. This is a project funded by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement ERC-2014-CoG 648276 AUTAR) for the period June 2015 - May 2020 (extended until September 2020 due to COVID-19 outbreak).

Summary: For a large family of computational problems collectively known as constrained optimization and satisfaction problems (CSPs), four decades of research in algorithms and computational complexity have led to a theory that tries to classify them as algorithmically tractable vs. intractable, i.e. polynomial-time solvable vs. NP-hard. However, there remains an important gap in our knowledge in that many CSPs of interest resist classification by this theory. Some such problems of practical relevance include fundamental partition problems in graph theory, isomorphism problems in combinatorics, and strategy-design problems in mathematical game theory. To tackle this gap in our knowledge, the research of the last decade has been driven either by finding hard instances for algorithms that solve tighter and tighter relaxations of the original problem, or by formulating new hardness-hypotheses that are stronger but admittedly less robust than NP-hardness. The ultimate goal of this project is closing the gap between the partial progress that these approaches represent and the original classification project into tractable vs. intractable problems. Our thesis is that the field has reached a point where, in many cases of interest, the analysis of the current candidate algorithms that appear to solve all instances could suffice to classify the problem one way or the other, without the need for alternative hardness-hypotheses. The novelty in our approach is a program to develop our recent discovery that, in some cases of interest, two methods from different areas match in strength: indistinguishability pebble games from mathematical logic, and hierarchies of convex relaxations from mathematical programming. Thus, we aim at making significant advances in the status of important algorithmic problems by looking for a general theory that unifies and goes beyond the current understanding of its components.

Team

  • Albert Atserias - Principal Investigator (PI)
  • Moritz Müller - Researcher (Jan 2018 - Sep 2020)
  • Szymon Toruńczyk - Researcher (Oct 2015 - Apr 2016)
  • Albert Oliveras - Researcher (Jun 2015 - Sep 2018)
  • Antoni Lozano - Researcher (Oct 2018 - May 2020)
  • Joanna Ochremiak - Postdoctoral researcher (Jan 2016 - Dec 2016)
  • Massimo Lauria - Postdoctoral researcher (Jan 2016 - Feb 2017)
  • Michal Garlik - Postdoctoral researcher (Mar 2017 - Sep 2020)
  • Ilario Bonacina - Postdoctoral researcher (Sep 2017 - Sep 2020)
  • Tuomas Hakoniemi - Research assistant, PhD student (Sep 2016 - Dec 2019)
  • Alberto Larrauri - Research assistant, PhD student (Sep 2019 - Sep 2020)
  • Ely Piceno - Research assistant, PhD student (Oct 2019 - Sep 2020)
  • Gabriel Verdejo - IT staff (Jun 2015 - Sep 2020)
  • Ivan Couto - IT staff (Jun 2015 - Sep 2020)

Visitors (past, current and planned)

  • Alexandra Kolla, University of Illinois at Urbana-Champaign, US (Jun 20-23, 2015)
  • Ilario Bonacina, University of Rome, Italy (Sep 28 - Oct 9, 2015)
  • Michal Garlik, Charles University, Czech Republic (Jun 26 - Jul 3, 2016)
  • Dieter van Melkebeek, University of Wisconsin - Madison, US [on sabbatical leave from UWisc] (Jan 9 - Jun 30, 2017)
  • Ilario Bonacina, KTH Royal Institute of Technology, Sweden (Jan 29 - Feb 18, 2017)
  • Jakob Nordström, KTH Royal Institute of Technology, Sweden (Jan 29 - Feb 4, 2017)
  • Joanna Ochremiak, University Paris-Diderot, France (Jan 29 - Feb 11, 2017)
  • Mozhgan Pourmoradnasseri, University of Tartu, Estonia (April 3 - April 4, 2017)
  • Joanna Ochremiak, University Paris-Diderot, France (Jun 26 - Jul 7, 2017)
  • Stephan Kreutzer, Technische Universität Berlin (Jul 20 - Jul 31, 2017)
  • Phokion Kolaitis, UCSC & IBM Research - Almaden (Nov 12 - Nov 19, 2017)
  • Joanna Ochremiak, University Paris-Diderot, France (Jun 26 - Jul 7, 2017)
  • Joanna Ochremiak, University Paris-Diderot, France (Jan 14 - Jan 24, 2018)
  • Igor Carboni Oliveira, University of Oxford, UK (May 7 - May 18, 2018)
  • Massimo Lauria, University of Rome, Italy (May 28 - Jun 8, 2018)
  • Joanna Ochremiak, University of Cambridge, UK (Oct 29 - Nov 9, 2018)
  • Luca Trevisan, University of California, Berkeley, USA (Nov 16 - Nov 25, 2018)
  • Navid Talebanfard, Czech Academy of Sciences, Prague, Czech Republic (Dec 9 - Dec 16, 2018)
  • Massimo Lauria, University of Rome, Italy (May 9 - May 28, 2019)
  • Yijia Chen, Fudan University, China (Jul 1 - Jul 13, 2019)
  • Kousha Etessami, University of Edinburgh, Scotland (Jul 10 - Jul 19, 2019)
  • Marc Vinyals, Tata Institute for Research, Mumbai, India (Sep 16 - Sep 20, 2019)
  • Joanna Ochremiak, Univesity of Bordeaux and CNRS, France (Jan 25 - Apr 30, 2020)
  • Nathanaël Fijalkow, Univesity of Bordeaux and CNRS, France (Jan 25 - Apr 30, 2020)

Local Public Activities

Visitors funded by the AUTAR project usually contribute a talk on a topic of their expertise and of interest for the project at the ALBCOM Seminar on Algorithms and Theory of Computation of the ALBCOM Research Group. Some of these talks are also announced at the LIMDA Joint Seminar that, besides the ALBCOM Seminar, also includes the COMBGRAPH Seminar on Combinatorics, Graph Theory and Applications, and the DCCG Seminar on Computational Geometry.

  • Talk at ALBCOM Seminar by Alexandra Kolla, Towards Refuting the Unique Games Conjecture, Jun 22, 2015.
  • Talk at LIMDA Joint Seminar by Ilario Bonacina, Strong Size Lower Bounds in Resolution via Games, Oct 1, 2015.
  • Talk at LIMDA Joint Seminar by Szymon Toruńczyk, CSPs with infinite instances, Dec 2, 2015.
  • Talk at LIMDA Joint Seminar by Jakob Nordström, How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity, Jan 30, 2017.
  • Talk at LIMDA Joint Seminar by Ilario Bonacina, Total space in Resolution is at least width squared, Feb 6, 2017.
  • Talk at LIMDA Joint Seminar by Dieter van Melkebeek, Derandomizing Isolation in the Space-Bounded Setting>, Feb 14, 2017.
  • Talk at LIMDA Joint Seminar by Mozhgan Pourmoradnasseri, The (minimum) rank of typical fooling-set matrices, April 3, 2017.
  • Talk at LIMDA Joint Seminar by Dieter van Melkebeek, Kernelization lower bounds from AP(3)-free sets, Jun 15, 2017.
  • Talk at Workshop on Graph Theory and Combinatorics, Foundations of Computational Mathematics 2017 by Albert Atserias, Gaps Between Classical Satisfiability Problem and Their Quantum Relaxations, July 14, 2017.
  • Talk at ALBCOM Seminar joint with Barcelona Logic Seminar by Phokion Kolaitis, Schema Mappings: Structural Propertiers and Limits, Nov 15, 2017.
  • Talk at Workshop JCALM 2018 by Albert Atserias, Two applications of Ramsey theory to finite model theory, Jan 18, 2017.
  • Talk at Workshop JCALM 2018 by Moritz Müller, KPT duality for finite Ramsey degrees, Jan 18, 2017.
  • Talk at LIMDA Joint Seminar by Igor Carboni Oliveira, Hardness Magnification for Natural Problems, May 9, 2018.
  • Talk at LIMDA Joint Seminar by Luca Trevisan, A Theory of Spectral Clustering, Nov 21, 2018.
  • Talk at LIMDA Joint Seminar by Yijia Chen, Shrub-depth, First-order Logic, and Craig's Interpolation Theorem, Jul 11, 2019.
  • Talk at LIMDA Joint Seminar by Marc Vinyals, Equality Alone Does not Simulate Randomness, Sep 18, 2019.
  • Talk at LIMDA Joint Seminar by Or Zamir, Faster k-SAT algorithms using biased-PPSZ, Jun 25, 2020.

Visitors and members of the team also participate regularly in the reading group organized by Juanjo Rué o topics of interest for the project. In the Fall of 2016 the topic was expander graphs. See here. In the Spring of 2017 the topic was graph limits. See here. In the Fall of 2017 the topics were heterogeneous. See here. In the Fall of 2018 the topic was non-standard methods for finite combinatorics. See here. In the Fall of 2019 the topic was random walks over groups. See here. The contributions by the members of our team follow:

Publications

  • Albert Atserias and Szymon Toruńczyk. Non-homogenizable classes of finite structures. In Proceedings of 25th EACSL Annual Conference on Computer Science Logic (CSL 2016), Marseille, France, LIPIcs 62, pages 16:1–16:16, Aug 2016.
  • Bartek Klin, Slawomir Lasota, Joanna Ochremiak, and Szymon Toruńczyk. Homomorphism problems for first-order definable structures. In Proceedings of 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016), Chennai, India, LIPIcs 65, pages 14:1– 14:15, Dec 2016.
  • Albert Atserias and Joanna Ochremiak. Proof Complexity Meets Algebra, ACM Transactions on Computational Logic, 20(1), pages 1:1--1:46, 2019. Open access version. A preliminary version appeared in Proceedings of 44th International Colloquium on Automata, Languages, and Programming (ICALP), LIPIcs 80, 110:1--110:14, 2017.
  • Albert Atserias, Phokion G. Kolaitis, and Simone Severini. Generalized Satisfiability Problems via Operator Assignments. Journal of Computer and System Sciences, 105, pages 171--198, 2019}. A preliminary version appeared in proceedings of 21st International Symposium on Fundamentals of Computation Theory (FCT 2017), Lecture Notes in Computer Science, 10472, pages 56-68, 2017. Best Paper Award.
  • 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 50th Annual ACM Symposium on the Theory of Computing (STOC), pp. 866-877, Los Angeles, CA, USA, June 2018. Open access version.
  • Albert Atserias and Moritz Müller. Automating Resolution is NP-Hard. Journal of the ACM, Vol. 67, No. 5, Article No. 31, September 2020. Preliminary version in Proceedings of 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2019), pages 498-509, 2019. Co-winner of Best paper award. Open access version.
  • Albert Atserias, Anuj Dawar, and Joanna Ochremiak. On the Power of Symmetric Linear Programs. In Proceedings of 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2019), Vancouver, BC, Canada, pages 1-13, Jun 2019. Open access version.
  • Albert Atserias and Massimo Lauria. Circular (Yet Sound) Proofs. In Proceedings of 22nd International Conference on Theory and Applications of Satisfiability Testing (SAT 2019), Lisbon, Portugal, pages 1-18, Jul 2019. Open access version.

Recruiting

Calls for job applications were announced at the PI's institutional homepage, the Barcelona Graduate School of Mathematics (BGSMath) homepage, the jobs portal of the European Commission EURAXESS, and the projects management and contracting office of UPC CTT.

  • 3 postdoctoral researcher positions, 2 research assistant positions (with PhD scholarships). May 2015.
  • 1 research assistant position (with PhD scholarship). September 2016.
  • 1 postdoctoral research position. December 2016.
  • 2 postdoctoral research positions. March 2017.
  • 2 postdoctoral research positions. October 2017.
  • 2 research assistant positions (with PhD scholarships). June 2019.