| Publication | Date of Publication | Type |
|---|
Counting answers to unions of conjunctive queries: natural tractability criteria and meta-complexity
ACM Transactions on Computational Logic | 2026-03-26 | Paper |
| Sampling from the random cluster model on random regular graphs at all temperatures via Glauber dynamics | 2025-01-14 | Paper |
| Parameterised and fine-grained subgraph counting, Modulo 2 | 2024-11-14 | Paper |
Fast sampling of satisfying assignments from random \(k\)-SAT with applications to connectivity
SIAM Journal on Discrete Mathematics | 2024-11-05 | Paper |
Counting subgraphs in somewhere dense graphs
SIAM Journal on Computing | 2024-10-21 | Paper |
Parameterised approximation of the fixation probability of the dominant mutation in the multi-type Moran process
Theoretical Computer Science | 2024-10-07 | Paper |
| Counting subgraphs in somewhere dense graphs | 2024-09-25 | Paper |
| Some new (and old) results on contention resolution (invited talk) | 2024-06-24 | Paper |
| Fast sampling via spectral independence beyond bounded-degree graphs | 2024-06-24 | Paper |
| Metastability of the Potts ferromagnet on random regular graphs | 2024-06-24 | Paper |
Parameterised and fine-grained subgraph counting, modulo 2
Algorithmica | 2024-04-02 | Paper |
| scientific article; zbMATH DE number 7799581 (Why is no real title available?) | 2024-02-05 | Paper |
| scientific article; zbMATH DE number 7788475 (Why is no real title available?) | 2024-01-15 | Paper |
Metastability of the Potts ferromagnet on random regular graphs
Communications in Mathematical Physics | 2023-06-23 | Paper |
| Sampling from the random cluster model on random regular graphs at all temperatures via Glauber dynamics | 2023-05-22 | Paper |
The complexity of approximately counting retractions
ACM Transactions on Computation Theory | 2022-12-05 | Paper |
Implementations and the independent set polynomial below the Shearer threshold
Theoretical Computer Science | 2022-11-17 | Paper |
The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs
SIAM Journal on Discrete Mathematics | 2022-09-21 | Paper |
Counting solutions to random CNF formulas
SIAM Journal on Computing | 2022-08-17 | Paper |
| The complexity of approximating the matching polynomial in the complex plane | 2022-07-21 | Paper |
| scientific article; zbMATH DE number 7559110 (Why is no real title available?) | 2022-07-18 | Paper |
| The complexity of approximating the complex-valued Potts model | 2022-07-18 | Paper |
The complexity of approximating the complex-valued Potts model
Computational Complexity | 2022-04-12 | Paper |
| Instability of backoff protocols with arbitrary arrival rates | 2022-03-31 | Paper |
The Complexity of Approximating the Matching Polynomial in the Complex Plane
ACM Transactions on Computation Theory | 2022-03-22 | Paper |
The Complexity of Approximating the Matching Polynomial in the Complex Plane
ACM Transactions on Computation Theory | 2022-03-22 | Paper |
The Complexity of Approximately Counting Retractions to Square-free Graphs
ACM Transactions on Algorithms | 2022-02-16 | Paper |
Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2
SIAM Journal on Discrete Mathematics | 2021-12-01 | Paper |
Faster exponential-time algorithms for approximately counting independent sets
Theoretical Computer Science | 2021-10-21 | Paper |
Sampling in uniqueness from the Potts and random-cluster models on random regular graphs
(available as arXiv preprint) | 2021-08-04 | Paper |
Holant clones and the approximability of conservative holant problems
ACM Transactions on Algorithms | 2021-05-03 | Paper |
Random walks on small world networks
ACM Transactions on Algorithms | 2021-05-03 | Paper |
The complexity of approximating the complex-valued Ising model on bounded degree graphs
(available as arXiv preprint) | 2021-05-01 | Paper |
Inapproximability of the independent set polynomial in the complex plane
SIAM Journal on Computing | 2020-10-26 | Paper |
Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems
Journal of Computer and System Sciences | 2020-10-23 | Paper |
Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems
Journal of Computer and System Sciences | 2020-10-23 | Paper |
Phase transitions of the Moran process and algorithmic consequences
Random Structures & Algorithms | 2020-06-19 | Paper |
Phase transitions of the Moran process and algorithmic consequences
Random Structures & Algorithms | 2020-06-19 | Paper |
The complexity of computing the sign of the Tutte polynomial
SIAM Journal on Computing | 2020-05-31 | Paper |
| scientific article; zbMATH DE number 7204479 (Why is no real title available?) | 2020-05-27 | Paper |
| scientific article; zbMATH DE number 7204480 (Why is no real title available?) | 2020-05-27 | Paper |
| A fixed-parameter perspective on \#BIS | 2020-05-27 | Paper |
The complexity of approximating the complex-valued Potts model
(available as arXiv preprint) | 2020-05-03 | Paper |
Sampling in uniqueness from the Potts and random-cluster models on random regular graphs
SIAM Journal on Discrete Mathematics | 2020-03-26 | Paper |
Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin
Journal of Computer and System Sciences | 2020-02-24 | Paper |
Approximating pairwise correlations in the Ising model
ACM Transactions on Computation Theory | 2019-12-16 | Paper |
A Complexity Trichotomy for Approximately Counting List H -Colorings
ACM Transactions on Computation Theory | 2019-12-06 | Paper |
Counting homomorphisms to square-free graphs, modulo 2
ACM Transactions on Computation Theory | 2019-12-06 | Paper |
The complexity of approximately counting retractions
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
A fixed-parameter perspective on \#BIS
Algorithmica | 2019-09-10 | Paper |
The complexity of counting surjective homomorphisms and compactions
SIAM Journal on Discrete Mathematics | 2019-08-29 | Paper |
Inapproximability of the independent set polynomial in the complex plane
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
| Approximating fixation probabilities in the generalized Moran process | 2019-05-10 | Paper |
Approximation via Correlation Decay When Strong Spatial Mixing Fails
SIAM Journal on Computing | 2019-05-07 | Paper |
Fast algorithms at low temperatures via Markov chains
(available as arXiv preprint) | 2019-01-20 | Paper |
Asymptotically optimal amplifiers for the Moran process
Theoretical Computer Science | 2019-01-10 | Paper |
Asymptotically optimal amplifiers for the Moran process
Theoretical Computer Science | 2019-01-10 | Paper |
Uniqueness for the 3-state antiferromagnetic Potts model on the tree
Electronic Journal of Probability | 2018-10-25 | Paper |
Uniqueness for the 3-state antiferromagnetic Potts model on the tree
Electronic Journal of Probability | 2018-10-25 | Paper |
Amplifiers for the Moran process
Journal of the ACM | 2018-08-02 | Paper |
The complexity of approximately counting in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs
(available as arXiv preprint) | 2018-04-22 | Paper |
| The complexity of counting surjective homomorphisms and compactions | 2018-03-15 | Paper |
The complexity of counting surjective homomorphisms and compactions
(available as arXiv preprint) | 2018-03-15 | Paper |
A complexity trichotomy for approximately counting list \(H\)-colourings
(available as arXiv preprint) | 2017-12-19 | Paper |
Amplifiers for the Moran process
(available as arXiv preprint) | 2017-12-19 | Paper |
Approximation via correlation decay when strong spatial mixing fails
(available as arXiv preprint) | 2017-12-19 | Paper |
The complexity of approximating complex-valued Ising and Tutte partition functions
Computational Complexity | 2017-12-18 | Paper |
On the fixation probability of superstars
Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences | 2017-09-29 | Paper |
Functional clones and expressibility of partition functions
Theoretical Computer Science | 2017-06-13 | Paper |
| \#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region | 2017-03-22 | Paper |
| Absorption time of the Moran process | 2017-03-22 | Paper |
| scientific article; zbMATH DE number 6691415 (Why is no real title available?) | 2017-03-03 | Paper |
A complexity classification of spin systems with an external field
Proceedings of the National Academy of Sciences | 2017-02-16 | Paper |
| The complexity of approximating conservative counting CSPs | 2017-01-30 | Paper |
The complexity of approximately counting in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs
Information and Computation | 2016-11-18 | Paper |
The complexity of counting homomorphisms to cactus graphs modulo 2
ACM Transactions on Computation Theory | 2016-10-24 | Paper |
Counting \(4 \times 4\) matrix partitions of graphs
Discrete Applied Mathematics | 2016-09-12 | Paper |
Absorption time of the Moran process
Random Structures & Algorithms | 2016-09-07 | Paper |
Absorption time of the Moran process
Random Structures & Algorithms | 2016-09-07 | Paper |
Approximately counting locally-optimal structures
Journal of Computer and System Sciences | 2016-06-13 | Paper |
Approximately counting \(H\)-colorings is \(\#\)BIS-hard
SIAM Journal on Computing | 2016-06-01 | Paper |
The complexity of counting locally maximal satisfying assignments of Boolean CSPs
Theoretical Computer Science | 2016-05-18 | Paper |
\(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
Journal of Computer and System Sciences | 2016-04-18 | Paper |
Approximately counting \(H\)-colourings is \(\#\mathrm{BIS}\)-hard
Automata, Languages, and Programming | 2015-10-27 | Paper |
Counting homomorphisms to square-free graphs, modulo 2
Lecture Notes in Computer Science | 2015-10-27 | Paper |
Approximately Counting Locally-Optimal Structures
Automata, Languages, and Programming | 2015-10-27 | Paper |
The complexity of approximately counting tree homomorphisms
ACM Transactions on Computation Theory | 2015-09-03 | Paper |
Counting List Matrix Partitions of Graphs
SIAM Journal on Computing | 2015-09-02 | Paper |
| scientific article; zbMATH DE number 6472592 (Why is no real title available?) | 2015-08-14 | Paper |
| scientific article; zbMATH DE number 6472637 (Why is no real title available?) | 2015-08-14 | Paper |
Polynomial space polynomial delay algorithms for listing families of graphs
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 | 2015-05-07 | Paper |
Approximating fixation probabilities in the generalized Moran process
Algorithmica | 2014-11-19 | Paper |
Approximating fixation probabilities in the generalized Moran process
Algorithmica | 2014-11-19 | Paper |
Approximating the partition function of planar two-state spin systems
Journal of Computer and System Sciences | 2014-09-22 | Paper |
The complexity of approximating conservative counting CSPs
Journal of Computer and System Sciences | 2014-09-22 | Paper |
Approximating the partition function of the ferromagnetic Potts model
Journal of the ACM | 2014-02-17 | Paper |
The expressibility of functions on the Boolean domain, with applications to counting CSPs
Journal of the ACM | 2014-02-17 | Paper |
A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid
SIAM Journal on Computing | 2013-09-25 | Paper |
The complexity of computing the sign of the Tutte polynomial (and consequent \#P-hardness of approximation)
Automata, Languages, and Programming | 2013-08-12 | Paper |
Ranking games that have competitiveness-based strategies
Theoretical Computer Science | 2013-04-17 | Paper |
Adaptive drift analysis
Algorithmica | 2013-03-05 | Paper |
Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials
Journal of Computer and System Sciences | 2013-02-21 | Paper |
The complexity of approximating bounded-degree Boolean \(\#\)CSP
Information and Computation | 2013-01-17 | Paper |
Inapproximability of the Tutte polynomial of a planar graph
Computational Complexity | 2012-12-27 | Paper |
| Log-supermodular functions, functional clones and counting CSPs | 2012-08-23 | Paper |
The complexity of approximately counting stable roommate assignments
Journal of Computer and System Sciences | 2012-08-17 | Paper |
The complexity of approximately counting stable matchings
Theoretical Computer Science | 2012-08-08 | Paper |
A counterexample to rapid mixing of the Ge-Stefankovic process
Electronic Communications in Probability | 2012-06-22 | Paper |
The complexity of weighted and unweighted \(\#\)CSP
Journal of Computer and System Sciences | 2012-05-11 | Paper |
| A complexity dichotomy for partition functions with mixed signs | 2012-04-24 | Paper |
| The complexity of approximating bounded-degree Boolean \#CSP | 2012-01-23 | Paper |
A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid
Lecture Notes in Computer Science | 2011-07-06 | Paper |
A Complexity Dichotomy for Partition Functions with Mixed Signs
SIAM Journal on Computing | 2011-04-04 | Paper |
A complexity dichotomy for hypergraph partition functions
Computational Complexity | 2011-02-18 | Paper |
| Efficient Algorithms for Listing Combinatorial Structures | 2011-01-25 | Paper |
The mixing time of Glauber dynamics for coloring regular trees
Random Structures & Algorithms | 2010-11-24 | Paper |
The Complexity of Approximately Counting Stable Matchings
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2010-09-10 | Paper |
Approximating the partition function of the ferromagnetic Potts model
Lecture Notes in Computer Science | 2010-09-07 | Paper |
Distributed selfish load balancing
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
The complexity of choosing an H -colouring (nearly) uniformly at random
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
Markov chain comparison
Probability Surveys | 2010-06-29 | Paper |
Markov chain comparison
Probability Surveys | 2010-06-29 | Paper |
An approximation trichotomy for Boolean \#CSP
Journal of Computer and System Sciences | 2010-05-25 | Paper |
On the computational complexity of weighted voting games
Annals of Mathematics and Artificial Intelligence | 2010-03-15 | Paper |
The Complexity of Weighted Boolean #CSP
SIAM Journal on Computing | 2009-11-06 | Paper |
The Complexity of Weighted Boolean #CSP
SIAM Journal on Computing | 2009-11-06 | Paper |
The complexity of weighted Boolean \#CSP with mixed signs
Theoretical Computer Science | 2009-09-10 | Paper |
A Tractable and Expressive Class of Marginal Contribution Nets and Its Applications
Mathematical Logic Quarterly | 2009-08-14 | Paper |
Matrix norms and rapid mixing for spin systems
The Annals of Applied Probability | 2009-04-02 | Paper |
On Counting Homomorphisms to Directed Acyclic Graphs
Automata, Languages and Programming | 2009-03-12 | Paper |
Dobrushin Conditions and Systematic Scan
Combinatorics, Probability and Computing | 2009-03-04 | Paper |
| Inapproximability of the Tutte polynomial | 2009-01-05 | Paper |
On counting homomorphisms to directed acyclic graphs
Journal of the ACM | 2008-12-21 | Paper |
Inapproximability of the Tutte polynomial
Information and Computation | 2008-08-14 | Paper |
Distributed Selfish Load Balancing
SIAM Journal on Computing | 2008-08-14 | Paper |
Distributed Selfish Load Balancing
SIAM Journal on Computing | 2008-08-14 | Paper |
Dobrushin Conditions and Systematic Scan
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2007-08-28 | Paper |
Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z2
LMS Journal of Computation and Mathematics | 2007-04-04 | Paper |
Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z2
LMS Journal of Computation and Mathematics | 2007-04-04 | Paper |
Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows
SIAM Journal on Computing | 2007-03-27 | Paper |
The Complexity of Ferromagnetic Ising with Local Fields
Combinatorics, Probability and Computing | 2007-03-20 | Paper |
Utilitarian resource assignment
Journal of Discrete Algorithms | 2007-02-14 | Paper |
Contention resolution with constant expected delay
Journal of the ACM | 2006-09-12 | Paper |
Systematic scan for sampling colorings
The Annals of Applied Probability | 2006-06-29 | Paper |
Strong Spatial Mixing with Fewer Colors for Lattice Graphs
SIAM Journal on Computing | 2006-06-01 | Paper |
The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random
SIAM Journal on Computing | 2005-02-21 | Paper |
A Bound on the Capacity of Backoff and Acknowledgment-Based Protocols
SIAM Journal on Computing | 2005-02-21 | Paper |
Counting and sampling \(H\)-colourings
Information and Computation | 2004-11-23 | Paper |
The relative complexity of approximate counting problems
Algorithmica | 2004-09-22 | Paper |
Random sampling of 3‐colorings in ℤ2
Random Structures & Algorithms | 2004-08-06 | Paper |
| scientific article; zbMATH DE number 2019624 (Why is no real title available?) | 2003-12-17 | Paper |
The computational complexity of two‐state spin systems
Random Structures & Algorithms | 2003-11-10 | Paper |
The Natural Work-Stealing Algorithm is Stable
SIAM Journal on Computing | 2003-09-28 | Paper |
Convergence of the Iterated Prisoner's Dilemma Game
Combinatorics, Probability and Computing | 2003-03-17 | Paper |
An improved stability bound for binary exponential backoff
Theory of Computing Systems | 2002-09-11 | Paper |
The complexity of gene placement
Journal of Algorithms | 2002-07-08 | Paper |
| scientific article; zbMATH DE number 1500516 (Why is no real title available?) | 2002-06-13 | Paper |
The ‘Burnside Process’ Converges Slowly
Combinatorics, Probability and Computing | 2002-05-14 | Paper |
Evolutionary trees can be learned in polynomial time in the two-state general Markov model
SIAM Journal on Computing | 2002-04-23 | Paper |
| scientific article; zbMATH DE number 1670534 (Why is no real title available?) | 2002-01-06 | Paper |
| scientific article; zbMATH DE number 1670868 (Why is no real title available?) | 2001-12-09 | Paper |
| scientific article; zbMATH DE number 1670864 (Why is no real title available?) | 2001-11-11 | Paper |
| Computation in permutation groups: Counting and randomly sampling orbits | 2001-09-09 | Paper |
An extension of path coupling and its application to the Glauber dynamics for graph colorings
SIAM Journal on Computing | 2001-06-21 | Paper |
Better approximation guarantees for job-shop scheduling
SIAM Journal on Discrete Mathematics | 2001-03-19 | Paper |
| scientific article; zbMATH DE number 1445357 (Why is no real title available?) | 2000-10-23 | Paper |
Counting Unlabelled Subtrees of a Tree is #P-complete
LMS Journal of Computation and Mathematics | 2000-09-25 | Paper |
| scientific article; zbMATH DE number 1301969 (Why is no real title available?) | 2000-09-24 | Paper |
Analysis of practical backoff protocols for contention resolution with multiple servers
Journal of Computer and System Sciences | 2000-06-29 | Paper |
Randomly Sampling Molecules
SIAM Journal on Computing | 2000-03-19 | Paper |
Approximation algorithms for the fixed-topology phylogenetic number problem
Algorithmica | 2000-02-07 | Paper |
| scientific article; zbMATH DE number 1305428 (Why is no real title available?) | 1999-09-15 | Paper |
An $\Omega(\sqrt{\,\log\log n}\,)$ Lower Bound for Routing in Optical Networks
SIAM Journal on Computing | 1998-09-20 | Paper |
Constructing Computer Virus Phylogenies
Journal of Algorithms | 1998-02-09 | Paper |
Minimizing phylogenetic number to find good evolutionary trees
Discrete Applied Mathematics | 1998-02-02 | Paper |
| scientific article; zbMATH DE number 871955 (Why is no real title available?) | 1996-09-22 | Paper |
Listing graphs that satisfy first-order sentences
Journal of Computer and System Sciences | 1994-12-04 | Paper |
| Efficient Algorithms for Listing Combinatorial Structures | 1994-02-17 | Paper |
Automating Pólya theory: The computational complexity of the cycle index polynomial
Information and Computation | 1993-09-01 | Paper |
Efficient algorithms for listing unlabeled graphs
Journal of Algorithms | 1992-06-28 | Paper |
