#	Pagina
attuale pagina	/open-h2020/projects/196864/results.html

Report

Teaser, summary, work performed and final results

Periodic Reporting for period 3 - AUTAR (A Unified Theory of Algorithmic Relaxations)

Teaser

Summary

The declared objectives of the project proposal included pushing forward the a priori observation that two methods from different areas for designing algorithms for CSPs match in strength:
1) the hierarchies of relaxations arising from the theory of mathematical programming and
2) the hierarchies of relaxations arising from the theory of definability in mathematical logic.
To what extent can this matching in strength be considered a coincidence or the tip of a deeper unified theory of algorithmic relaxations? The importance of building a unified theory of algorithmic relaxations stems from the general principle that, in applied mathematics, computer science, and the natural sciences at large, unified theories tend to have much deeper predicting and explanation power than a separate collection of unrelated looking techniques. The first 18 months of this action have started implementing a program to contribute in building a theory for algorithmic relaxations.

After 36 months of execution of the project, the main achievement is that we have solved one of the original questions that initiated this research. The starting point for the project was the finding that, for the graph isomorphism problem, the linear programming hierarchy of relaxations matched in strength with the number-of-variables hierarchy of relaxations in mathematical logic. The question we asked was about the exact strength of the semidefinite programming hierarchy in this context: could semidefinite programming techniques be strictly more powerful that linear programming techniques in distinguishing non-isomorphic graphs? In seveal other contexts, such as in approximating solutions to constraint satisfaction problems, semidefinite programming provably beat linear programming. Surprisingly, our main finding is that for the graph isomorphism problem this is not the case; in other words, semidefinite programming collapses to linear programming in the context of isomorphisms. This finding could have impact for the analysis of certain semidefinite programming based algorithms in the context of constraint satisfaction problem, where unlike the linear programming counterparts, their exact strength is not yet well understood.

Work performed

The main achievement of the work performed so far includes a completely satisfactory solution to the first of the main concrete questions that the project was planning to address. It was known before the project started that the method of linear programming hierarchies matched in strength with the tuple-refinement method for graph isomorphism. The question we asked in the project proposal was:

What is the power of the semidefinite programming (SDP) hierarchies for graph isomorphism and how does it compare to the linear programming (LP) hierarchies? While it was known from work preceding the Project proposal that the SDP hierarchies will not make a complete polynomial-time algorithm for graph isomorphism, their exact relationship to the LP hierarchies was unknown. The answer we found is that, surprisingly, the SDP hierarchy collapses to the LP hierarchy, up to small constant factors, in the context of the graph isomorphism problem. This opens the door to the possibility of obtaining stronger SDP integrality gaps from known LP integrality gap constructions for other problems, a question that will be addressed in the rest of the project.

Final results

An interesting outcome of the work performed so far is the opening of a new and unpredicted line of research in which so-called quantum relaxations of CSPs arising from non-local games in quantum physics are studied systematically. One of the outcomes so far is that the method of closure operations (aka polymorphisms) from classical CSPs has an analogue in the context of quantum CSPs. This has already produced novel results of theoretical interest for both quantum information theorists and theoretical computer scientist, and we hope that the rest of the project will round up a more complete theory. While such interdisplinary connections between these areas are not unprecedented, the fact that they arise naturally within the unified theory of algorithmic relaxations that the project puts forward could have far-reaching applications for both areas. Two technical reports including these results are being written at the time this progress report is being produced.