Descriptive Complexity with Algebraic Operators
Lead Research Organisation:
University of Cambridge
Department Name: Computer Science and Technology
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.
People |
ORCID iD |
Anuj Dawar (Principal Investigator) |
Publications
Anderson M
(2015)
Solving Linear Programs without Breaking Abstractions
in Journal of the ACM
Anderson M
(2017)
On Symmetric Circuits and Fixed-Point Logics
Anderson M
(2016)
On Symmetric Circuits and Fixed-Point Logics
in Theory of Computing Systems
Anuj Dawar
(2015)
A Definability Dichotomy for Finite Valued CSPs.
Atserias A
(2012)
Automata, Languages, and Programming
Atserias A
(2014)
Degree lower bounds of tower-type for approximating formulas with parity quantifiers
in ACM Transactions on Computational Logic
Bouland A
(2012)
Parameterized and Exact Computation
Bulian J
(2015)
Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree
in Algorithmica
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 | Academic/University |
Country | United States |
Start | 06/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 |