Descriptive Complexity with Algebraic Operators

Lead Research Organisation: University of Cambridge
Department Name: Computer Laboratory

Abstract

The study of computational complexity is concerned with understanding what makes certain computational tasks inherently difficult to solve. In this context, problems that can be solved by means of algorithms that take a number of steps bounded by a polynomial are considered to be feasible, or efficiently solvable. A long standing research concern in the field of descriptive complexity has been to give a complete classification of those problems that are feasible. Such a complete classification would take the form of a formal language (or a logic) in which one could define all the feasible problems, but no others. It has been known for some time that languages based on induction and counting are not sufficient for this purpose and it has recently been discovered that adding certain operators based on linear algebra can extend the power of such languages. Our research aims at building on this breakthrough by understanding the power of these extended languages. To do this we will develop new methods to analyse the expressive power and use this to determine whether or not the newly defined languages do capture the power of feasible computation.We will also investigate whether these languages capture feasible computation in interesting special cases.

Planned Impact

Research on a characterization of P, i.e. a complete classification of those problems that admit efficient solutions in terms of polynomial-time computability, would have an impact in a number of areas: (1) on designers of database management systems and of query and programming languages to whom it would provide a guideline for the design of systems within which feasible algorithms can be implemented; (2) on software developers in general to whom it would provide a conceptual tool for understanding what problems are feasible; and (3) other users of mathematical results, by enriching the landscape of such results and shaping the way we think about fundamental problems. The primiary means of achieving this impact are twofold. First, the publication of the results in accessible and permanent form. Secondly, in the longer run as results mature, they are taught to students and thereby diffuse through the user community.

Publications

10 25 50

publication icon
Anderson M (2016) On Symmetric Circuits and Fixed-Point Logics in Theory of Computing Systems

publication icon
Anderson M (2015) Solving Linear Programs without Breaking Abstractions in Journal of the ACM

publication icon
Atserias A (2014) Degree lower bounds of tower-type for approximating formulas with parity quantifiers in ACM Transactions on Computational Logic

publication icon
Bulian J (2015) Fixed-parameter Tractable Distances to Sparse Graph Classes in 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, September 16-18, 2015, Patras, Greece

 
Description The research project aimed at understanding a classification of
computational problems that admit feasible solutions (that is, they
are solvable in polynomial time). Giving a logical characterisation
of this class of problems is a long-standing open problem. The
research aimed at understanding why the best attempts at such a
characterization so far, based on logics of induction, counting, and
algebraic operators fall short of this goal. The main findings are:

- linear programming problems are expressible in logic with induction
and counting and, as a consequence, maximum matching problems in
graphs are also definable. This was an unexpected outcome as the
contrary had been conjectured.

- a characterisation of the definable problems in terms of
recognisability by symmetric circuits. This leads to the
identification of a symmetry barier in descriptive complexity.

- the formulation of techniques (based on algebraic pebble games) for
analysing the expressive power of logics with induction and
linear-algebraic operators.

- a polyonimial-time test, more powerful than those previously known,
for distinguishing graphs that are not isomorphic.
Exploitation Route The
findings have been incorporated into training materials delivered
through courses aimed at postgraduate students. The aim is to diffuse
the ideas developed in a way that influences the design and
development of algorithms and software in the long-term.
Follow-up work since the completion of the project has extended definability from linear programming to semidefinite programming. One surprising outcome of this has been a dichotomy on definability of finite-valued constraint satisfaction problems that has also yielded a surprising complexity dichotomy for approximations of such problems by semidefinite programs.
Sectors Digital/Communication/Information Technologies (including Software)

URL http://www.cl.cam.ac.uk/~ad260
 
Description The findings have been incorporated into training materials delivered through courses aimed at postgraduate students. The aim is to diffuse the ideas developed in a way that influences the design and development of algorithms and software in the long-term.
Sector Digital/Communication/Information Technologies (including Software)
Impact Types Cultural,Societal

 
Description Forschungs- und Arbeitsaufenthalte
Amount € 7,200 (EUR)
Funding ID A/13/05456 
Organisation German Academic Exchange Service (DAAD) 
Sector Public
Country United States
Start 07/2013 
End 04/2014
 
Description RWTH Aachen 
Organisation RWTH Aachen University
Department Department of Computer Science
Country Germany 
Sector Academic/University 
PI Contribution I spent eight months at RWTH Aachen to work on collaborative research on the graph isomorphism problem, and choiceless computation.
Collaborator Contribution My visit to Aachen was hosted by the department and I worked collaboratively with a number of students and other researchers based there - in particular Prof. Grohe, Prof. Graedel, Dr Pakusa and Dr Berkholz.
Impact Listed in outputs
Start Year 2013
 
Description Beroun Winter School 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Postgraduate students
Results and Impact 40 participants attended a three-day intensive winter school on algorithmic methods. As part of this, I delivered four hours of lectures on graph isomorphism.


I received multiple requests for the material on the research results presented.
Year(s) Of Engagement Activity 2013
 
Description Games Winter School 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? Yes
Geographic Reach International
Primary Audience Postgraduate students
Results and Impact 80 postgraduate students and young researchers attended a week-long school, which included 4 hours of lectures by myself on Games and Isomorphism.

Subsequent interest from postgraduate students in this research direction.
Year(s) Of Engagement Activity 2013
URL http://www.games.rwth-aachen.de/Activities/champery.html
 
Description PhD Open (Warsaw) 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? Yes
Geographic Reach International
Primary Audience Postgraduate students
Results and Impact over 50 postgraduate students attended six hours of lectures and a number of them undertook an assessment afterwards.
Year(s) Of Engagement Activity 2010
URL http://phdopen.mimuw.edu.pl/index.php?page=z10w1
 
Description Prague Fall School 
Form Of Engagement Activity A formal working group, expert panel or dialogue
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Postgraduate students
Results and Impact Short course (four hours of lectures) aimed at international group of postgraduate students in the area of logic and complexity. Stimulated discussion carried on by e-mail.

Extensive contact with a group of international research students.
Year(s) Of Engagement Activity 2011
URL http://www.karlin.mff.cuni.cz/~krajicek/fall11.html