Computational Counting
Lead Research Organisation:
Queen Mary University of London
Department Name: Sch of Mathematical Sciences
Abstract
Abstracts are not currently available in GtR for all funded research. This is normally because the abstract was not required at the time of proposal submission, but may be because it included sensitive information such as personal details.
Publications
Bulatov A
(2012)
The complexity of weighted and unweighted #CSP
in Journal of Computer and System Sciences
Bulatov A
(2013)
The expressibility of functions on the boolean domain, with applications to counting CSPs
in Journal of the ACM
Chen X
(2015)
The complexity of approximating conservative counting CSPs
in Journal of Computer and System Sciences
Dyer M
(2017)
On the Switch Markov Chain for Perfect Matchings
in Journal of the ACM
Dyer M
(2015)
On the switch Markov chain for perfect matchings
Dyer M
(2020)
Random Walks on Small World Networks
in ACM Transactions on Algorithms
Dyer M.
(2016)
On the switch Markov chain for perfect matchings
in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Goldberg L
(2012)
Inapproximability of the Tutte polynomial of a planar graph
in computational complexity
Goldberg L
(2011)
A Counterexample to rapid mixing of the Ge-Stefankovic Process
Goldberg L
(2012)
A counterexample to rapid mixing of the Ge-Štefankovic process
in Electronic Communications in Probability
| Description | • We have investigated in depth the computational complexity of the Tutte polynomial, a two-variable polynomial associated with a graph G that encodes much useful information about G. The complexity of exact computation was already well understood, but we now have substantially greater knowledge of the complexity of approximation within specified relative error. • We have established a general result about the computational complexity of computing good approximations to the partition functions of conservative counting CSPs. Constraint Satisfaction Problems (CSPs) arose in artificial intelligence, and are normally studied in their decision and optimisation variants. However the counting variant encodes many spin systems studied in statistical physics, and is well worth investigating. The "conservative" qualifier appearing above can be interpreted as indicating the presence of an external field acting on individual spins. Our result precisely characterises the complexity of conservative counting CSPs, and hence of the related spin systems. • We have made some contributions to the as yet underdeveloped study of the parameterised complexity of counting problems. Parameterised complexity is a framework for dealing with computational problems that are intractable in general, but which may be tractable on instances of interest. The difficult aspect of the problem is captured in a parameter which one hopes is small in instances occurring in practice. |
| Exploitation Route | • In our work on fixed parameter tractability, we developed an approximation algorithm for the problem of counting so-called motifs in a graph with a vertex colouring. This is an abstraction of a problem arising in molecular biology. • There is increasing interest in the theoretical computer science community in the parameterised complexity of counting problems. We believe that the general class of problem we have introduced will be of value in promoting future work in this area. |
| Sectors | Digital/Communication/Information Technologies (including Software) |
| URL | http://www.maths.qmul.ac.uk/~mj/pubs.html#2011 |