Mark Jerrum

Discret. Comput. Geom., October, 2023

A simple polynomial-time approximation algorithm for the total variation distance between two product distributions.

[BibT_eX]

[DOI]

TheoretiCS, 2023

Perfect Sampling of q-Spin Systems on ℤ2 via Weak Spatial Mixing.

[BibT_eX]

[DOI]

Konrad Anand

CoRR, 2023

2022

Counting and Sampling: Algorithms and Complexity (Dagstuhl Seminar 22482).

[BibT_eX]

[DOI]

Dagstuhl Reports, November, 2022

Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing.

[BibT_eX]

[DOI]

Konrad Anand

SIAM J. Comput., June, 2022

A simple polynomial-time approximation algorithm for total variation distances between product distributions.

[BibT_eX]

[DOI]

CoRR, 2022

2021

Counting Weighted Independent Sets beyond the Permanent.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2021

Approximately counting bases of bicircular matroids.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2021

Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2021

Fundamentals of Partial Rejection Sampling.

[BibT_eX]

[DOI]

CoRR, 2021

Counting vertices of integer polytopes defined by facets.

[BibT_eX]

[DOI]

CoRR, 2021

The Size of the Giant Joint Component in a Binomial Random Double Graph.

[BibT_eX]

[DOI]

Tamás Makai

Electron. J. Comb., 2021

2020

Random Walks on Small World Networks.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2020

2019

Approximating Pairwise Correlations in the Ising Model.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2019

A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability.

[BibT_eX]

[DOI]

SIAM J. Comput., 2019

Uniform Sampling Through the Lovász Local Lemma.

[BibT_eX]

[DOI]

Jingcheng Liu

J. ACM, 2019

2018

Perfect Simulation of the Hard Disks Model by Partial Rejection Sampling.

[BibT_eX]

[DOI]

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017

A Complexity Trichotomy for Approximately Counting List H-Colorings.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2017

Functional clones and expressibility of partition functions.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2017

On the Switch Markov Chain for Perfect Matchings.

[BibT_eX]

[DOI]

Haiko Müller

J. ACM, 2017

Computational Counting (Dagstuhl Seminar 18341).

[BibT_eX]

[DOI]

Ivona Bezáková

Dagstuhl Reports, 2017

A simple FPRAS for bi-directed reachability.

[BibT_eX]

[DOI]

CoRR, 2017

The parameterised complexity of counting even and odd induced subgraphs.

[BibT_eX]

[DOI]

Comb., 2017

Random cluster dynamics for the Ising model is rapidly mixing.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Counting Constraint Satisfaction Problems.

[BibT_eX]

[DOI]

Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 2017

2016

The complexity of counting locally maximal satisfying assignments of Boolean CSPs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2016

Approximately Counting H-Colorings is $\#\mathrm{BIS}$-Hard.

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2016

A complexity trichotomy for approximately counting list H-colourings.

[BibT_eX]

[DOI]

CoRR, 2016

A Complexity Trichotomy for Approximately Counting List H-Colourings.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

Some Hard Families of Parameterized Counting Problems.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2015

The Complexity of Parity Graph Homomorphism: An Initial Investigation.

[BibT_eX]

[DOI]

John D. Faben

Theory Comput., 2015

A complexity classification of spin systems with an external field.

[BibT_eX]

[DOI]

Proc. Natl. Acad. Sci. USA, 2015

The parameterised complexity of counting connected subgraphs and graph motifs.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2015

Approximating the partition function of planar two-state spin systems.

[BibT_eX]

[DOI]

Colin McQuillan

J. Comput. Syst. Sci., 2015

The complexity of approximating conservative counting CSPs.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2015

The complexity of Boolean #MaximalCSP.

[BibT_eX]

[DOI]

CoRR, 2015

Approximately Counting H-Colourings is #BIS-Hard.

[BibT_eX]

[DOI]

CoRR, 2015

Approximately Counting H-Colourings is #\mathrm BIS # BIS -Hard.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

The Complexity of Approximately Counting Tree Homomorphisms.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2014

The Complexity of Computing the Sign of the Tutte Polynomial.

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

2013

A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid.

[BibT_eX]

[DOI]

SIAM J. Comput., 2013

Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2013

The expressibility of functions on the boolean domain, with applications to counting CSPs.

[BibT_eX]

[DOI]

J. ACM, 2013

Computational Counting (Dagstuhl Seminar 13031).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2013

Some hard classes of parameterised counting problems.

[BibT_eX]

[DOI]

CoRR, 2013

The Parameterised Complexity of Counting Connected Subgraphs.

[BibT_eX]

[DOI]

CoRR, 2013

Approximating the Partition Function of Two-Spin Systems on Bipartite Graphs.

[BibT_eX]

[DOI]

CoRR, 2013

2012

The complexity of weighted and unweighted #CSP.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2012

Approximating the partition function of the ferromagnetic potts model.

[BibT_eX]

[DOI]

J. ACM, 2012

Inapproximability of the Tutte polynomial of a planar graph.

[BibT_eX]

[DOI]

Comput. Complex., 2012

Log-supermodular functions, functional clones and counting CSPs.

[BibT_eX]

[DOI]

Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

The Complexity of Computing the Sign of the Tutte Polynomial (and Consequent #P-hardness of Approximation).

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011

A Counterexample to rapid mixing of the Ge-Stefankovic Process

[BibT_eX]

[DOI]

CoRR, 2011

2010

A Complexity Dichotomy for Partition Functions with Mixed Signs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2010

The mixing time of Glauber dynamics for coloring regular trees.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2010

An approximation trichotomy for Boolean #CSP.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2010

A Complexity Dichotomy For Hypergraph Partition Functions.

[BibT_eX]

[DOI]

Comput. Complex., 2010

Constraint satisfaction problems and computational complexity: technical persepctive.

[BibT_eX]

[DOI]

Commun. ACM, 2010

10481 Executive Summary - Computational Counting.

[BibT_eX]

[DOI]

Peter Bürgisser

Proceedings of the Computational Counting, 28.11. - 03.12.2010, 2010

10481 Abstracts Collection - Computational Counting.

[BibT_eX]

[DOI]

Peter Bürgisser

Proceedings of the Computational Counting, 28.11. - 03.12.2010, 2010

2009

The Complexity of Weighted Boolean #CSP.

[BibT_eX]

[DOI]

SIAM J. Comput., 2009

2008

Inapproximability of the Tutte polynomial.

[BibT_eX]

[DOI]

Inf. Comput., 2008

Dobrushin Conditions and Systematic Scan.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2008

The Mixing Time of Glauber Dynamics for Colouring Regular Trees

[BibT_eX]

[DOI]

CoRR, 2008

08201 Abstracts Collection - Design and Analysis of Randomized and Approximation Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Design and Analysis of Randomized and Approximation Algorithms, 11.05., 2008

2007

The Complexity of Ferromagnetic Ising with Local Fields.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2007

Matrix norms and rapid mixing for spin systems

[BibT_eX]

[DOI]

CoRR, 2007

2006

Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows.

[BibT_eX]

[DOI]

SIAM J. Comput., 2006

Two Remarks Concerning Balanced Matroids.

[BibT_eX]

[DOI]

Comb., 2006

2005

05201 Abstracts Collection - Design and Analysis of Randomized and Approximation Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Design and Analysis of Randomized and Approximation Algorithms, 15.05., 2005

2004

A bound on the capacity of backoff and acknowledgment-based protocols.

[BibT_eX]

[DOI]

SIAM J. Comput., 2004

A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.

[BibT_eX]

[DOI]

J. ACM, 2004

Counting and sampling H-colourings?

[BibT_eX]

[DOI]

Inf. Comput., 2004

The Relative Complexity of Approximate Counting Problems.

[BibT_eX]

[DOI]

Algorithmica, 2004

2003

The computational complexity of two-state spin systems.

[BibT_eX]

[DOI]

Mike Paterson

Random Struct. Algorithms, 2003

2002

On Counting Independent Sets in Sparse Graphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2002

The "Burnside Process" Converges Slowly.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2002

Convergence Of The Iterated Prisoner's Dilemma Game.

[BibT_eX]

[DOI]

Gabriel Istrate

Comb. Probab. Comput., 2002

Spectral Gap and log-Sobolev Constant for Balanced Matroids.

[BibT_eX]

[DOI]

Jung-Bae Son

Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

2001

A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs.

[BibT_eX]

[DOI]

Proceedings of the Graphs, 2001

2000

An Extension of Path Coupling and Its Application to the Glauber Dynamics for Graph Colorings.

[BibT_eX]

[DOI]

Michael Mitzenmacher

SIAM J. Comput., 2000

Counting Unlabelled Subtrees of a Tree is #P-complete.

[BibT_eX]

[DOI]

LMS J. Comput. Math., 2000

A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2000

An extension of path coupling and its application to the Glauber dynamics for graph colourings (extended abstract).

[BibT_eX]

[DOI]

Michael Mitzenmacher

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

1999

Randomly Sampling Molecules.

[BibT_eX]

[DOI]

SIAM J. Comput., 1999

On Approximately Counting Colorings of Small Degree Graphs.

[BibT_eX]

[DOI]

Russ Bubley

SIAM J. Comput., 1999

Bisimulation Equivanlence Is Decidable for Normed Process Algebra.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1999

1998

An Omega(sqrt{log log n}) Lower Bound for Routing in Optical Networks.

[BibT_eX]

[DOI]

Philip D. MacKenzie

SIAM J. Comput., 1998

Approximately Counting Hamilton Paths and Cycles in Dense Graphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 1998

An elementary analysis of a procedure for sampling points in a convex body.

[BibT_eX]

[DOI]

Russ Bubley

Random Struct. Algorithms, 1998

The Metropolis Algorithm for Graph Bisection.

[BibT_eX]

[DOI]

Gregory B. Sorkin

Discret. Appl. Math., 1998

1997

Doubly Logarithmic Communication Algorithms for Optical-Communication Parallel Computers.

[BibT_eX]

[DOI]

Frank Thomson Leighton

Satish Rao

SIAM J. Comput., 1997

A Quasi-Polynomial-Time Algorithm for Sampling Words from a Context-Free Language.

[BibT_eX]

[DOI]

Inf. Comput., 1997

Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION.

[BibT_eX]

[DOI]

Algorithmica, 1997

The Swendsen-Wang Process Does Not Always Mix Rapidly.

[BibT_eX]

[DOI]

Vivek Gore

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

1996

A Polynomial Algorithm for Deciding Bisimilarity of Normed Context-Free Processes.

[BibT_eX]

[DOI]

Faron Moller

Theor. Comput. Sci., 1996

A Polynomial-Time Algorithm for Deciding Bisimulation Equivalence of Normed Basic Parallel Processes.

[BibT_eX]

[DOI]

Faron Moller

Math. Struct. Comput. Sci., 1996

Generating and Counting Hamilton Cycles in Random Regular Graphs.

[BibT_eX]

[DOI]

J. Algorithms, 1996

A Mildly Exponential Approximation Algorithm for the Permanent.

[BibT_eX]

[DOI]

Umesh V. Vazirani

Algorithmica, 1996

Learning Linear Transformations.

[BibT_eX]

[DOI]

Ravi Kannan

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995

A Very Simple Algorithm for Estimating the Number of k-Colorings of a Low-Degree Graph.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 1995

Bounding the Vapnik-Chervonenkis Dimension of Concept Classes Parameterized by Real Numbers.

[BibT_eX]

[DOI]

Paul W. Goldberg

Mach. Learn., 1995

An Analysis of a Monte Carlo Algorithm for Estimating the Permanent.

[BibT_eX]

[DOI]

Comb., 1995

Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 1995

1994

Simple Translation-Invariant Concepts Are Hard to Learn

[BibT_eX]

[DOI]

Inf. Comput., September, 1994

Three-Dimensional Statistical Data Security Problems.

[BibT_eX]

[DOI]

Robert W. Irving

SIAM J. Comput., 1994

Counting Trees in a Graph is #P-Complete.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1994

An W(log log n) Lower Bound for Routing in Optical Networks.

[BibT_eX]

[DOI]

Philip D. MacKenzie

Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, 1994

Approximately Counting Hamilton Cycles in Dense Graphs.

[BibT_eX]

[DOI]

Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

A Polynomial-time Algorithm for Deciding Equivalence of Normed Context-free Processes

[BibT_eX]

[DOI]

Faron Moller

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993

Polynomial-Time Approximation Algorithms for the Ising Model.

[BibT_eX]

[DOI]

SIAM J. Comput., 1993

A Doubly Logarithmic Communication Algorithm for the Completely Connected Optical Communication Parallel Computer.

[BibT_eX]

[DOI]

Frank Thomson Leighton

Satish Rao

Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, 1993

An analysis of a Monte Carlo algorithm for estimating the permanent.

[BibT_eX]

Proceedings of the 3rd Integer Programming and Combinatorial Optimization Conference, Erice, Italy, April 29, 1993

Simulated Annealing for Graph Bisection

[BibT_eX]

[DOI]

Gregory B. Sorkin

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992

Large Cliques Elude the Metropolis Process.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 1992

Uniform Sampling Modulo a Group of Symmetries Using Markov Chain Simulation.

[BibT_eX]

[DOI]

Proceedings of the Expanding Graphs, 1992

1990

Fast Uniform Generation of Regular Graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1990

Polynomial-Time Approximation Algorithms for Ising Model (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

1989

Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains

[BibT_eX]

[DOI]

Inf. Comput., July, 1989

Approximating the Permanent.

[BibT_eX]

[DOI]

SIAM J. Comput., 1989

1988

Conductance and the Rapid Mixing Property for Markov Chains: the Approximation of the Permanent Resolved (Preliminary Version)

[BibT_eX]

[DOI]

Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

On Continuous Homotopic One Layer Routing.

[BibT_eX]

[DOI]

Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988

On Continuous Homotopic One Layer Routing.

[BibT_eX]

[DOI]

Proceedings of the Computational Geometry and its Applications, 1988

1986

Random Generation of Combinatorial Structures from a Uniform Distribution.

[BibT_eX]

[DOI]

Leslie G. Valiant

Vijay V. Vazirani

Theor. Comput. Sci., 1986

A Compact Representation for Permutation Groups.

[BibT_eX]

[DOI]

J. Algorithms, 1986

1985

The Complexity of Finding Minimum-Length Generator Sequences.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1985

Random Generation of Combinatorial Structures from a Uniform Distribution (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Automata, 1985

1984

Families of Fixed Degree Graphs for Processor Interconnection.

[BibT_eX]

[DOI]

Sven Skyum

IEEE Trans. Computers, 1984

The Complexity of Finding Minimum-Length Generator Sequences (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Automata, 1984

1982

Some Exact Complexity Results for Straight-Line Computations over Semirings.

[BibT_eX]

[DOI]