This project ended on Sep 30, 2020

Funded by

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 ERC2014CoG
648276 AUTAR) for the period June 2015  May 2020 (extended until
September 2020 due to COVID19 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. polynomialtime solvable vs. NPhard. 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 strategydesign 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 hardnesshypotheses that
are stronger but admittedly less robust than NPhardness. 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 hardnesshypotheses. 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 UrbanaChampaign, US (Jun 2023, 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 ParisDiderot, France (Jan
29  Feb 11, 2017)
 Mozhgan Pourmoradnasseri, University of Tartu, Estonia (April 3  April 4, 2017)
 Joanna Ochremiak, University ParisDiderot, 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 ParisDiderot, France (Jun 26  Jul
7, 2017)
 Joanna Ochremiak, University ParisDiderot, 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 SpaceBounded Setting>, Feb 14, 2017.
 Talk at LIMDA Joint Seminar by Mozhgan Pourmoradnasseri, The (minimum) rank of typical foolingset 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, Shrubdepth, Firstorder
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 kSAT
algorithms using biasedPPSZ, Jun 25, 2020.
Visitors and members of the team also participate regularly
in the reading group organized
by Juanjo
Rué no 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 nonstandard 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:
 Presentation at reading group by Albert Atserias with title Zigzag product (I), Dec 1, 2016.
 Presentation at reading group by Tuomas Hakoniemi with title
Zigzag product (II), Dec 15, 2016.
 Presentation at reading group by Ilario Bonacina with title
Deterministic search for CNF satisfying assignments in almost
polynomial time, by Servedio and Tan, Feb 28, 2018.
 Presentation at reading group by Moritz Müller of Appendix
and Chapters 1 and 2 of Nonstandard Methods in Ramsey
Theory and Combinatorial Number Theory (1/3), Sep 12, 2018.
 Presentation at reading group by Moritz Müller of Appendix
and Chapters 1 and 2 of Nonstandard Methods in Ramsey
Theory and Combinatorial Number Theory (2/3), Sep 19, 2018.
 Presentation at reading group by Moritz Müller of Appendix
and Chapters 1 and 2 of Nonstandard Methods in Ramsey
Theory and Combinatorial Number Theory (3/3), Oct 3, 2018.
 Presentation at reading group by Alberto Larrauri of
the CarneVaropoulos Inequality from Random
walks on Infinite Discrete Groups, Oct 29, 2019.

Organization of events
The PI has been involved into
the organization of several scientific events of relevance to the
topics of the AUTAR project. We list them here:

The Oberwolfach Workshop on Proof Complexity and Beyond
was held in Oberwolfach Research Institute for Mathematics,
OberwolfachWalke, Germany, on August 1319, 2017. The PI was part of the
Organizing and Scientific Committee. The members of the group
Atserias, Lauria, and Ochremiak contributed talks to the workshop.

The Dagstuhl
Seminar on Proof Complexity was held in Schloss Dagstuhl,
LeibnizZentrum für Informatik, on January 28  February 2,
2018. The PI was part of the Organizing and Scientific Committee. The
members of the group Atserias, Bonacina, and Müller (as well as
past members Lauria and Ochremiak) contributed talks at the
workshop.

The Banff
Workshop on Proof Complexity was held in Banff International
Research Center (BIRS), Banff, Alberta, Canada, on January 1924,
2020. The PI was part of the Organizing and Scientific Committee. The
members of the group Atserias, Bonacina, Garlík and Hakoniemi
attended and contributed talks to the workshop.

Publications
 Bartek Klin, Slawomir Lasota, Joanna Ochremiak, and Szymon
Toruńczyk. Homomorphism problems for firstorder 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. Repository version.
 Albert Atserias and Joanna Ochremiak. Proof Complexity Meets Algebra,
ACM Transactions on Computational Logic, 20(1), pages 1:11:46,
2019. A preliminary version appeared in
Proceedings of 44th International Colloquium on Automata, Languages,
and Programming (ICALP), LIPIcs 80, 110:1110:14, 2017. Repository version.
 Albert Atserias, Phokion G. Kolaitis, and Simone Severini. Generalized
Satisfiability Problems via Operator Assignments.
Journal of Computer and System Sciences, 105, pages 171198, 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 5668, 2017. Best
Paper Award. Repository version.
 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. 866877, Los Angeles, CA, USA, June
2018. Repository version.
 Albert Atserias, Stephan Kreutzer, and Marc Noy. On ZeroOne and Convergence Laws for Graphs Embeddable on a Fixed
Surface, in Proceedings of 45th
International Colloquium on Automata, Languages, and Programming
(ICALP), Leibniz International Proceedings in Informatics (LIPIcs),
116:1116:14, Prague, Czech, July 2018. Repository version.
 Albert Atserias and Moritz Müller.
Automating Resolution is NPHard. 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 498509, 2019. Cowinner of Best paper award. Repository 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 113, Jun 2019.
Repository 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 118,
Jul 2019. Repository 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.
