Publications

# Publications :: Search

## Show author

 Select a publication Show Title Venue Rating Date Journal article Paul G. Spirakis, Leslie Ann Goldberg, Antonín Kucera, Giuseppe Persiano. Statement from EATCS President and vice Presidents about the recent US travel restrictions to foreigners. Bulletin of the EATCS 2017, Volume 121 (0) 2017 Journal article Andreas Galanis, Andreas Göbel 0001, Leslie Ann Goldberg, John Lapinskas, David Richerby. Amplifiers for the Moran Process. J. ACM 2017, Volume 64 (0) 2017 Conference paper Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum. A Complexity Trichotomy for Approximately Counting List TOCT 2016, Volume 9 (0) 2017 Conference paper Radu Curticapean, Holger Dell, Fedor V. Fomin, Leslie Ann Goldberg, John Lapinskas. A Fixed-Parameter Perspective on #BIS. CoRR 2017, Volume 0 (0) 2017 Journal article Andrei A. Bulatov, Leslie Ann Goldberg, Mark Jerrum, David Richerby, Stanislav Zivny. Functional clones and expressibility of partition functions. Theor. Comput. Sci. 2017, Volume 687 (0) 2017 Journal article Jacob Focke, Leslie Ann Goldberg, Stanislav Zivny. The Complexity of Counting Surjective Homomorphisms and Compactions. CoRR 2017, Volume 0 (0) 2017 Conference paper Andreas Galanis, Leslie Ann Goldberg, Kuan Yang. Approximating Partition Functions of Bounded-Degree Boolean Counting Constraint Satisfaction Problems. 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland 2017 (0) 2017 Conference paper Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic. Inapproximability of the Independent Set Polynomial Below the Shearer Threshold. 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland 2017 (0) 2017 Conference paper Martin E. Dyer, Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum, Eric Vigoda. Random Walks on Small World Networks. CoRR 2017, Volume 0 (0) 2017 Conference paper Leslie Ann Goldberg, Heng Guo 0001. The Complexity of Approximating complex-valued Ising and Tutte partition functions. Computational Complexity 2017, Volume 26 (0) 2017 Journal article Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic. Inapproximability of the independent set polynomial in the complex plane. CoRR 2017, Volume 0 (0) 2017 Conference paper Andreas Galanis, Leslie Ann Goldberg. The complexity of approximately counting in 2-spin systems on Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016 2016 (0) 2016 Journal article Leslie Ann Goldberg, Mark Jerrum. A complexity trichotomy for approximately counting list H-colourings. CoRR 2016, Volume 0 (0) 2016 Journal article Leslie Ann Goldberg, Mark Jerrum. The complexity of counting locally maximal satisfying assignments of Boolean CSPs. Theor. Comput. Sci. 2016, Volume 634 (0) 2016 Conference paper Andreas Göbel 0001, Leslie Ann Goldberg, David Richerby. Counting Homomorphisms to Square-Free Graphs, Modulo 2. TOCT 2016, Volume 8 (0) 2016 Conference paper Leslie Ann Goldberg, Rob Gysel, John Lapinskas. Approximately counting locally-optimal structures. J. Comput. Syst. Sci. 2016, Volume 82 (0) 2016 Conference paper Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo 0001, Mark Jerrum, Daniel Stefankovic, Eric Vigoda. #BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region. J. Comput. Syst. Sci. 2016, Volume 82 (0) 2016 Journal article Josep Díaz, Leslie Ann Goldberg, David Richerby, Maria J. Serna. Absorption time of the Moran process. Random Struct. Algorithms 2016, Volume 49 (0) 2016 Conference paper Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum. Approximately Counting H-Colorings is $\#\mathrm{BIS}$-Hard. SIAM J. Comput. 2016, Volume 45 (0) 2016 Conference paper Andreas Galanis, Andreas Göbel 0001, Leslie Ann Goldberg, John Lapinskas, David Richerby. Amplifiers for the Moran Process. 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy 2016 (0) 2016 Conference paper Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum. A Complexity Trichotomy for Approximately Counting List H-Colourings. 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy 2016 (0) 2016 Conference paper Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Heng Guo 0001, Daniel Stefankovic. Approximation via Correlation Decay When Strong Spatial Mixing Fails. 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy 2016 (0) 2016 Conference paper Andrei A. Bulatov, Leslie Ann Goldberg, Mark Jerrum, David Richerby, Stanislav Zivny. Functional Clones and Expressibility of Partition Functions. CoRR 2016, Volume 0 (0) 2016 Conference paper Martin E. Dyer, Leslie Ann Goldberg, David Richerby. Counting 4×4 matrix partitions of graphs. Discrete Applied Mathematics 2016, Volume 213 (0) 2016 Conference paper Andreas Galanis, Leslie Ann Goldberg, Kuan Yang. Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems. CoRR 2016, Volume 0 (0) 2016 Conference paper Andreas Galanis, Leslie Ann Goldberg. The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs. Inf. Comput. 2016, Volume 251 (0) 2016 Conference paper Leslie Ann Goldberg, John Lapinskas, Johannes Lengler, Florian Meier, Konstantinos Panagiotou, Pascal Pfister. Asymptotically Optimal Amplifiers for the Moran Process. CoRR 2016, Volume 0 (0) 2016 Conference paper Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic. Inapproximability of the independent set polynomial below the Shearer threshold. CoRR 2016, Volume 0 (0) 2016 Journal article Leslie Ann Goldberg, Mark Jerrum, Colin McQuillan. Approximating the partition function of planar two-state spin systems. J. Comput. Syst. Sci. 2015, Volume 81 (0) 2015 Journal article Xi Chen, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, David Richerby. The complexity of approximating conservative counting CSPs. J. Comput. Syst. Sci. 2015, Volume 81 (0) 2015 Conference paper Andreas Göbel 0001, Leslie Ann Goldberg, David Richerby. Counting Homomorphisms to Square-Free Graphs, Modulo 2. CoRR 2015, Volume 0 (0) 2015 Journal article Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum. Approximately Counting H-Colourings is #BIS-Hard. CoRR 2015, Volume 0 (0) 2015 Conference paper Andreas Galanis, Leslie Ann Goldberg. The complexity of approximately counting in 2-spin systems on $k$-uniform bounded-degree hypergraphs. CoRR 2015, Volume 0 (0) 2015 Conference paper Leslie Ann Goldberg. Evolutionary Dynamics on Graphs: Invited Talk. Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII, Aberystwyth, United Kingdom, January 17 - 20, 2015 2015 (0) 2015 Conference paper Leslie Ann Goldberg, Rob Gysel, John Lapinskas. Approximately Counting Locally-Optimal Structures. Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I 2015 (0) 2015 Conference paper Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum. Approximately Counting H-Colourings is #\mathrm BIS # BIS -Hard. Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I 2015 (0) 2015 Conference paper Andreas Göbel 0001, Leslie Ann Goldberg, David Richerby. Counting Homomorphisms to Square-Free Graphs, Modulo 2. Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I 2015 (0) 2015 Conference paper Andreas Göbel 0001, Leslie Ann Goldberg, Colin McQuillan, David Richerby, Tomoyuki Yamakami. Counting List Matrix Partitions of Graphs. SIAM J. Comput. 2015, Volume 44 (0) 2015 Journal article Leslie Ann Goldberg, Mark Jerrum. The complexity of Boolean #MaximalCSP. CoRR 2015, Volume 0 (0) 2015 Conference paper Andreas Galanis, Andreas Göbel 0001, Leslie Ann Goldberg, John Lapinskas, David Richerby. Amplifiers for the Moran Process. CoRR 2015, Volume 0 (0) 2015 Conference paper Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Heng Guo 0001, Daniel Stefankovic. Approximation via Correlation Decay when Strong Spatial Mixing Fails. CoRR 2015, Volume 0 (0) 2015 Conference paper Andreas Göbel 0001, Leslie Ann Goldberg, David Richerby. Counting Homomorphisms to Cactus Graphs Modulo 2. 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), STACS 2014, March 5-8, 2014, Lyon, France 2014 (0) 2014 Journal article Josep Díaz, Leslie Ann Goldberg, George B. Mertzios, David Richerby, Maria J. Serna, Paul G. Spirakis. Approximating Fixation Probabilities in the Generalized Moran Process. Algorithmica 2014, Volume 69 (0) 2014 Conference paper Leslie Ann Goldberg, Mark Jerrum. The Complexity of Approximately Counting Tree Homomorphisms. TOCT 2014, Volume 6 (0) 2014 Journal article Martin E. Dyer, Leslie Ann Goldberg, David Richerby. Counting $4\times 4$ Matrix Partitions of Graphs. CoRR 2014, Volume 0 (0) 2014 Conference paper Josep Díaz, Leslie Ann Goldberg, David Richerby, Maria J. Serna. Absorption Time of the Moran Process. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, September 4-6, 2014, Barcelona, Spain 2014 (0) 2014 Conference paper Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Stefankovic, Eric Vigoda. #BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Non-uniqueness Region. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, September 4-6, 2014, Barcelona, Spain 2014 (0) 2014 Conference paper Andreas Göbel 0001, Leslie Ann Goldberg, David Richerby. The complexity of counting homomorphisms to cactus graphs modulo 2. TOCT 2014, Volume 6 (0) 2014 Conference paper Andreas Göbel 0001, Leslie Ann Goldberg, Colin McQuillan, David Richerby, Tomoyuki Yamakami. Counting List Matrix Partitions of Graphs. IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, June 11-13, 2014 2014 (0) 2014 Conference paper Leslie Ann Goldberg, Heng Guo 0001. The complexity of approximating complex-valued Ising and Tutte partition functions with applications to quantum simulation. CoRR 2014, Volume 0 (0) 2014 Journal article Leslie Ann Goldberg, Rob Gysel, John Lapinskas. Approximately counting locally-optimal structures. CoRR 2014, Volume 0 (0) 2014 Conference paper Leslie Ann Goldberg, Mark Jerrum. The Complexity of Computing the Sign of the Tutte Polynomial. SIAM J. Comput. 2014, Volume 43 (0) 2014 Journal article Leslie Ann Goldberg, Mark Jerrum. Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials. J. Comput. Syst. Sci. 2013, Volume 79 (0) 2013 Journal article Benjamin Doerr, Leslie Ann Goldberg. Adaptive Drift Analysis. Algorithmica 2013, Volume 65 (0) 2013 Journal article Leslie Ann Goldberg, Paul W. Goldberg, Piotr Krysta, Carmine Ventre. Ranking Games that have Competitiveness-based Strategies CoRR 2013, Volume 0 (0) 2013 Journal article Leslie Ann Goldberg, Paul W. Goldberg, Piotr Krysta, Carmine Ventre. Ranking games that have competitiveness-based strategies. Theor. Comput. Sci. 2013, Volume 476 (0) 2013 Conference paper Xi Chen, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, David Richerby. The complexity of approximating conservative counting CSPs. 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, February 27 - March 2, 2013, Kiel, Germany 2013 (0) 2013 Journal article Leslie Ann Goldberg, Mark Jerrum. The Complexity of Approximately Counting Tree Homomorphisms CoRR 2013, Volume 0 (0) 2013 Journal article Peter Bürgisser, Leslie Ann Goldberg, Mark Jerrum, Pascal Koiran. Computational Counting (Dagstuhl Seminar 13031). Dagstuhl Reports 2013, Volume 3 (0) 2013 Conference paper Andreas Göbel 0001, Leslie Ann Goldberg, Colin McQuillan, David Richerby, Tomoyuki Yamakami. Counting list matrix partitions of graphs. CoRR 2013, Volume 0 (0) 2013 Conference paper Leslie Ann Goldberg, Mark Jerrum. A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid. SIAM J. Comput. 2013, Volume 42 (0) 2013 Journal article Andreas Göbel 0001, Leslie Ann Goldberg, David Richerby. The Complexity of Counting Homomorphisms to Cactus Graphs Modulo 2. CoRR 2013, Volume 0 (0) 2013 Conference paper Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Colin McQuillan. The expressibility of functions on the boolean domain, with applications to counting CSPs. J. ACM 2013, Volume 60 (0) 2013 Journal article Jin-Yi Cai, Leslie Ann Goldberg, Heng Guo, Mark Jerrum. Approximating the Partition Function of Two-Spin Systems on Bipartite Graphs. CoRR 2013, Volume 0 (0) 2013 Journal article Josep Díaz, Leslie Ann Goldberg, David Richerby, Maria J. Serna. Absorption Time of the Moran Process. CoRR 2013, Volume 0 (0) 2013 Journal article Leslie Ann Goldberg. The EATCS Award 2014 - Call for nominations. Bulletin of the EATCS 2013, Volume 111 (0) 2013 Conference paper Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum, David Richerby. The complexity of weighted and unweighted #CSP. J. Comput. Syst. Sci. 2012, Volume 78 (0) 2012 Conference paper Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum. Log-supermodular functions, functional clones and counting CSPs. 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th - March 3rd, 2012, Paris, France 2012 (0) 2012 Conference paper Prasad Chebolu, Leslie Ann Goldberg, Russell Martin. The complexity of approximately counting stable roommate assignments. J. Comput. Syst. Sci. 2012, Volume 78 (0) 2012 Conference paper Leslie Ann Goldberg, Mark Jerrum. The Complexity of Computing the Sign of the Tutte Polynomial (and Consequent #P-hardness of Approximation). Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I 2012 (0) 2012 Conference paper Leslie Ann Goldberg, Mark Jerrum. The Complexity of Computing the Sign of the Tutte Polynomial (and consequent #P-hardness of Approximation) CoRR 2012, Volume 0 (0) 2012 Conference paper Josep Díaz, Leslie Ann Goldberg, George B. Mertzios, David Richerby, Maria J. Serna, Paul G. Spirakis. Can Fixation be Guaranteed in the Generalized Moran Process? CoRR 2012, Volume 0 (0) 2012 Conference paper Leslie Ann Goldberg, Mark Jerrum, Colin McQuillan. Approximating the partition function of planar two-state spin systems CoRR 2012, Volume 0 (0) 2012 Conference paper Xi Chen, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, David Richerby. The complexity of approximating conservative counting CSPs CoRR 2012, Volume 0 (0) 2012 Conference paper Leslie Ann Goldberg, Mark Jerrum. Inapproximability of the Tutte polynomial of a planar graph. Computational Complexity 2012, Volume 21 (0) 2012 Journal article Prasad Chebolu, Leslie Ann Goldberg, Russell Martin. The complexity of approximately counting stable matchings. Theor. Comput. Sci. 2012, Volume 437 (0) 2012 Conference paper Leslie Ann Goldberg, Mark Jerrum. Approximating the partition function of the ferromagnetic potts model. J. ACM 2012, Volume 59 (0) 2012 Journal article Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby. The complexity of approximating bounded-degree Boolean #CSP. Inf. Comput. 2012, Volume 220 (0) 2012 Conference paper Josep Díaz, Leslie Ann Goldberg, George B. Mertzios, David Richerby, Maria J. Serna, Paul G. Spirakis. Approximating fixation probabilities in the generalized Moran process. Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012 2012 (0) 2012 Conference paper Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald, Christian Scheideler. Stabilizing consensus with the power of two choices. SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, San Jose, CA, USA, June 4-6, 2011 (Co-located with FCRC 2011) 2011 (0) 2011 Conference paper Leslie Ann Goldberg, Mark Jerrum. A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid. Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I 2011 (0) 2011 Journal article Benjamin Doerr, Leslie Ann Goldberg. Adaptive Drift Analysis CoRR 2011, Volume 0 (0) 2011 Journal article Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum. Log-supermodular functions, functional clones and counting CSPs CoRR 2011, Volume 0 (0) 2011 Journal article Leslie Ann Goldberg, Mark Jerrum. A Counterexample to rapid mixing of the Ge-Stefankovic Process CoRR 2011, Volume 0 (0) 2011 Conference paper Josep Díaz, Leslie Ann Goldberg, George B. Mertzios, David Richerby, Maria J. Serna, Paul G. Spirakis. Approximating Fixation Probabilities in the Generalized Moran Process CoRR 2011, Volume 0 (0) 2011 Journal article Andrei Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum, David Richerby. The complexity of weighted and unweighted #CSP CoRR 2010, Volume 0 (0) 2010 Conference paper Leslie Ann Goldberg, Paul W. Goldberg, Piotr Krysta, Carmine Ventre. Ranking games that have competitiveness-based strategies. Proceedings 11th ACM Conference on Electronic Commerce (EC-2010), Cambridge, Massachusetts, USA, June 7-11, 2010 2010 (0) 2010 Journal article Leslie Ann Goldberg, Mark Jerrum. Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials CoRR 2010, Volume 0 (0) 2010 Conference paper Leslie Ann Goldberg, Mark Jerrum. Approximating the Partition Function of the Ferromagnetic Potts Model. Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I 2010 (0) 2010 Conference paper Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald, Christian Scheideler. Brief Announcement: Stabilizing Consensus with the Power of Two Choices. Distributed Computing, 24th International Symposium, DISC 2010, Cambridge, MA, USA, September 13-15, 2010. Proceedings 2010 (0) 2010 Conference paper Prasad Chebolu, Leslie Ann Goldberg, Russell Martin. The Complexity of Approximately Counting Stable Matchings. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings 2010 (0) 2010 Conference paper Benjamin Doerr, Leslie Ann Goldberg. Drift Analysis with Tail Bounds. Parallel Problem Solving from Nature - PPSN XI, 11th International Conference, Kraków, Poland, September 11-15, 2010, Proceedings, Part I 2010 (0) 2010 Conference paper Benjamin Doerr, Leslie Ann Goldberg. Adaptive Drift Analysis. Parallel Problem Solving from Nature - PPSN XI, 11th International Conference, Kraków, Poland, September 11-15, 2010, Proceedings, Part I 2010 (0) 2010 Journal article Leslie Ann Goldberg, Mark Jerrum. A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid CoRR 2010, Volume 0 (0) 2010 Conference paper Leslie Ann Goldberg, Mark Jerrum, Marek Karpinski. The mixing time of Glauber dynamics for coloring regular trees. Random Struct. Algorithms 2010, Volume 36 (0) 2010 Journal article Prasad Chebolu, Leslie Ann Goldberg, Russell Martin. The Complexity of Approximately Counting Stable Roommate Assignments CoRR 2010, Volume 0 (0) 2010 Conference paper Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum. A Complexity Dichotomy For Hypergraph Partition Functions. Computational Complexity 2010, Volume 19 (0) 2010 Conference paper Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, Marc Thurley. A Complexity Dichotomy for Partition Functions with Mixed Signs. SIAM J. Comput. 2009, Volume 39 (0) 2010 Conference paper Peter Bürgisser, Leslie Ann Goldberg, Mark Jerrum. 10481 Abstracts Collection - Computational Counting. Computational Counting, 28.11. - 03.12.2010 2010 (0) 2010 Conference paper Peter Bürgisser, Leslie Ann Goldberg, Mark Jerrum. 10481 Executive Summary - Computational Counting. Computational Counting, 28.11. - 03.12.2010 2010 (0) 2010