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.
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)
 Albert Oliveras  Researcher (June 2015  )
 Szymon Torunczyk  Postdoctoral researcher (October 2015  April 2016)
 Joanna Ochremiak  Postdoctoral researcher (January 2016  December 2016)
 Massimo Lauria  Postdoctoral researcher (January 2016  February 2017)
 Tuomas Hakoniemi  PhD student (September 2016  )
 Michal Garlik  Postdoctoral researcher (March 2017  )

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 Paris Diderot  Paris 7, France (Jan
29  Feb 11, 2017)
 Mozhgan Pourmoradnasseri, University of
Tartu, Estonia (April 3  April 4, 2017)
 Joanna Ochremiak, University Paris Diderot
 Paris 7, France (Jun 26 Jul 7, 2017)
 Stephan Kreutzer, Technische Universität
Berlin (Jul 20  Jul 31, 2017)

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 Toruczyk, 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.
Both visitors and members of the team also participate regularly
in the reading group organized
by Juanjo
Rué on topics of interest for the project. In the Fall of
2016 the topic was expander
graphs. See here
for the full list of sessions. 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.

Publications
 Bartek Klin, Slawomir Lasota, Joanna Ochremiak, and Szymon
Torunczyk. Homomorphism problems for firstorder definable
structures. In 36th IARCS Annual Conference on Foundations of Software
Technology and Theoretical Computer Science, FSTTCS 2016, December
1315, 2016, Chennai, India, pages 14:1– 14:15, 2016.
 Albert Atserias and Joanna Ochremiak. Proof Complexity Meets Algebra,
in Proceedings of 44th International Colloquium on Automata, Languages,
and Programming (ICALP), LIPIcs 80, 110:1110:14, 2017.

Recruiting
Calls for job applications were announced at
the PI's 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 posdoctoral research positions. March 2017.
