Computational Counting
Lead Research Organisation:
University of Leeds
Department Name: Sch of Computing
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.
Organisations
People |
ORCID iD |
| Martin Edward Dyer (Principal Investigator) |
Publications
Goldberg L
(2012)
A counterexample to rapid mixing of the Ge-Štefankovic process
in Electronic Communications in Probability
Dyer M
(2012)
The complexity of approximating bounded-degree Boolean #CSP
in Information and Computation
Dyer M
(2015)
On the chromatic number of a random hypergraph
in Journal of Combinatorial Theory, Series B
Bulatov A
(2012)
The complexity of weighted and unweighted #CSP
in Journal of Computer and System Sciences
Chen X
(2015)
The complexity of approximating conservative counting CSPs
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
Dyer M
(2017)
On the Switch Markov Chain for Perfect Matchings
in Journal of the ACM
Bulatov A.A.
(2012)
Log-supermodular functions, functional clones and counting CSPs
in Leibniz International Proceedings in Informatics, LIPIcs
Dyer M.
(2016)
On the switch Markov chain for perfect matchings
in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Dyer M
(2013)
An Effective Dichotomy for the Counting Constraint Satisfaction Problem
in SIAM Journal on Computing
Martin Edward Dyer (Co-Author)
(2013)
The complexity of approximating conservative counting CSPs
Dyer M
(2012)
On the chromatic number of a random hypergraph
Goldberg L
(2011)
A Counterexample to rapid mixing of the Ge-Stefankovic Process
| Description | A decidable dichotomy theorem for counting constraint satisfaction problems. |
| Exploitation Route | Already been used to prove an even more general theorem by Cai and Chen. |
| Sectors | Digital/Communication/Information Technologies (including Software),Education |