Publications

2024

Marco Bressan, Leslie Ann Goldberg, Kitty Meeks, Marc Roth, Counting Subgraphs in Somewhere Dense Graphs. SICOMP, To Appear.
Andreas Goebel, Leslie Ann Goldberg, and Marc Roth, The Weisfeiler-Leman Dimension of Existential Conjunctive Queries, To Appear in PODS 2024.
Jacob Focke, Leslie Ann Goldberg, Marc Roth, and Stanislav Zivny, Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity, To Appear in PODS 2024.
Leslie Ann Goldberg and Marc Roth, Parameterised and Fine-grained Subgraph Counting, Modulo 2, Algorithmica, To Appear.
Yumou Fei, Leslie Ann Goldberg, Pinyan Lu, Two-State Spin Systems with Negative Interactions. ITCS 2024, https://doi.org/10.4230/LIPIcs.ITCS.2024.45
Ivona Bezakova, Andreas Galanis, Leslie Ann Goldberg, and Daniel Stefankovic, Fast sampling via spectral independence beyond bounded-degree graphs , ACM Transactions on Algorithms, 20 (1) (2024) https://doi.org/10.1145/3631354

2023

Andreas Galanis, Leslie Ann Goldberg, Paulina Smolarova, Sampling from the random cluster model on random regular graphs at all temperatures via Glauber dynamics. RANDOM 2023.
Leslie Ann Goldberg and Marc Roth, Parameterised and Fine-grained Subgraph Counting, Modulo 2, ICALP 2023. (see the journal version)
Gwendolyn Farach-Colton, Martin Farach-Colton, Leslie Ann Goldberg, Hanna Komlos, John Lapinskas, Reut Levi, Moti Medina, Miguel A. Mosteiro Graph Ranking and the Cost of Sybil Defense, EC 2023.
Amin Coja-Oghlan, Andreas Galanis, Leslie Ann Goldberg, Jean Bernoulli Ravelomanana, Daniel Stefankovic, and Eric Vigoda. Metastability of the Potts ferromagnet on random regular graphs . Communications in Mathematical Physics (2023) https://link.springer.com/article/10.1007/s00220-023-04644-6
Marco Bressan, Leslie Ann Goldberg, Kitty Meeks, Marc Roth, Counting Subgraphs in Somewhere Dense Graphs. ITCS 2023. (see the journal version)

Leslie Ann Goldberg and John Lapinskas, Instability of backoff protocols with arbitrary arrival rates SODA 2023.
Andreas Galanis, Leslie Ann Goldberg and Daniel Stefankovic, Implementations and the independent set polynomial below the Shearer threshold Theoretical Computer Science, 939 194-215 (2023). https://doi.org/10.1016/j.tcs.2022.10.025
Leslie Ann Goldberg, Marc Roth, and Tassilo Constantin Schwarz Parameterised Approximation of the Fixation Probability of the Dominant Mutation in the Multi-Type Moran Process. Submitted.

2022

Andreas Galanis, Leslie Ann Goldberg, Andres Herrera-Poyatos The complexity of approximating the complex-valued Ising model on bounded degree graphs . SIDMA 36(3) 2159-2204 (2022). https://doi.org/10.1137/21M1454043
Ivona Bezakova, Andreas Galanis, Leslie Ann Goldberg, and Daniel Stefankovic, Fast sampling via spectral independence beyond bounded-degree graphs. Proceedings of ICALP'22. (see the journal version)
Amin Coja-Oghlan, Andreas Galanis, Leslie Ann Goldberg, Jean Bernoulli Ravelomanana, Daniel Stefankovic, and Eric Vigoda. Metastability of the Potts ferromagnet on random regular graphs. Proceedings of ICALP'22. (see the journal version)
Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivny, Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations . Proceedings of PODS'22.
Andreas Galanis, Leslie Ann Goldberg, James Stewart Fast mixing via polymers for random graphs with unbounded degree. Information and Computation. (2022) https://doi.org/10.1016/j.ic.2022.104894
Andreas Galanis, Leslie Ann Goldberg, Andres Herrera-Poyatos The complexity of approximating the complex-valued Potts model. Computational Complexity, 31. Article 2 (2022). https://doi.org/10.1007/s00037-021-00218-x
Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Andres Herrera-Poyatos Fast sampling of satisfying assignments from random k-SAT . Submitted.

2021

Leslie Ann Goldberg, John Lapinskas, David Richerby Faster Exponential-time Algorithms for Approximately Counting Independent Sets. TCS. 892(12) 48-84 (2021) https://doi.org/10.1016/j.tcs.2021.09.009
Andreas Galanis, Leslie Ann Goldberg, Heng Guo and Kuan Yang Counting solutions to random CNF formulas. SICOMP, 50(6), 1701–1738 (2021). https://doi.org/10.1137/20M1351527.
Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivny, Counting Homomorphisms to K4-minor-free Graphs, modulo 2. SIDMA. 35(4) 2749--2814 (2021) https://doi.org/10.1137/20M1382921.
Andreas Galanis, Leslie Ann Goldberg, James Stewart, Fast mixing via polymers for random graphs with unbounded degree. Proceedings of APPROX/RANDOM 2021 . (see the journal version)
Andreas Galanis, Leslie Ann Goldberg, James Stewart Fast algorithms for general spin systems on bipartite expanders. ACM Transactions on Computation Theory. 13(4) Article 25 pp 1--18 (2021). https://doi.org/10.1145/3470865
Jacob Focke, Leslie Ann Goldberg, Stanislav Zivny, The Complexity of Approximately Counting Retractions to Square-Free Graphs . ACM Transactions on Algorithms. 17(3) Article 22 (2021). https://doi.org/10.1145/3458040
Ivona Bezakova, Andreas Galanis, Leslie Ann Goldberg, and Daniel Stefankovic, The complexity of approximating the matching polynomial in the complex plane . ACM Transactions on Computation Theory, Vol 13, No 2, Article 13 (2021) https://doi.org/10.1145/3448645
Leslie Ann Goldberg, Joost Jorritsma, Júlia Komjáthy, John Lapinskas, Increasing efficacy of contact-tracing applications by user referrals and stricter quarantining. PLoS ONE, 16(5): e0250435 (2021) https://doi.org/10.1371/journal.pone.0250435
Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg, Will Perkins, James Stewart, and Eric Vigoda Fast algorithms at low temperatures via Markov chains. Random Structures and Algorithms, Volume 58, Issue 2 (2021) 294--321 http://dx.doi.org/10.1002/rsa.20968. It is best to use the ArXiv version which has (corrected) extra factors in the running times in Theorems 5 and 6.
Andreas Galanis, Leslie Ann Goldberg, Kuan Yang, Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems JCSS, 115 (2021) 187-213. https://doi.org/10.1016/j.jcss.2020.08.003
Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivny, Counting Homomorphisms to K4-minor-free Graphs, modulo 2. SODA 2021. (see the journal version)

2020

Ivona Bezakova, Andreas Galanis, Leslie Ann Goldberg, and Daniel Stefankovic, Inapproximability of the independent set polynomial in the complex plane . SICOMP, 49(5) pp. STOC18-395--STOC18-448 (2020) https://doi.org/10.1137/18M1184485
Andreas Galanis, Leslie Ann Goldberg, Andres Herrera-Poyatos The complexity of approximating the complex-valued Potts model. MFCS 2020. (see the journal version)
Andreas Galanis, Leslie Ann Goldberg, James Stewart Fast algorithms for general spin systems on bipartite expanders. MFCS 2020. (see the journal version)
Martin E. Dyer, Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum, Eric Vigoda, Random Walks on Small World Networks ACM Transaction on Algorithms, (2020). https://doi.org/10.1145/3382208
Miriam Backens and Leslie Ann Goldberg, Holant clones and the approximability of conservative holant problems. ACM Transactions on Algorithms, (2020). https://doi.org/10.1145/3381425
Antonio Blanca, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic, Eric Vigoda, Kuan Yang, Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs. SIDMA, (2020). https://doi.org/10.1137/18M1219722
Jacob Focke, Leslie Ann Goldberg, Stanislav Zivny, The Complexity of Approximately Counting Retractions . ACM Transactions on Computation Theory, (2020). https://doi.org/10.1145/3397472
Andreas Galanis, Leslie Ann Goldberg, Heng Guo and Kuan Yang Counting solutions to random CNF formulas. ICALP 2020. (see the journal version)
Miriam Backens, Andrei Bulatov, Leslie Ann Goldberg, Colin McQuillan, Stanislav Zivny, Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin. JCSS, (2020) https://doi.org/10.1016/j.jcss.2019.12.003

2019

Leslie Ann Goldberg, John Lapinskas, David Richerby Phase Transitions of the Moran Process and Algorithmic Consequences. Random Structures and Algorithms (2019) https://doi.org/10.1002/rsa.20890
Leslie Ann Goldberg and Mark Jerrum, Approximating Pairwise Correlations in the Ising Model . ACM TOCT (2019) https://doi.org/10.1145/3337785
Radu Curticapean, Holger Dell, Fedor Fomin, Leslie Ann Goldberg and John Lapinskas, A Fixed-Parameter Perspective on #BIS. Algorithmica (2019) https://doi.org/10.1007/s00453-019-00606-4
Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg, Will Perkins, James Stewart, and Eric Vigoda, Fast algorithms at low temperatures via Markov chains. RANDOM 2019 (see the journal version)
Ivona Bezakova, Andreas Galanis, Leslie Ann Goldberg, and Daniel Stefankovic, The complexity of approximating the matching polynomial in the complex plane ICALP 2019 (see the journal version)
Jacob Focke, Leslie Ann Goldberg, Stanislav Zivny, The Complexity of Counting Surjective Homomorphisms and Compactions. SIDMA 33(2) (2019) 1006--1043. https://doi.org/10.1137/17M1153182
Ivona Bezakova, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, and Daniel Stefankovic, Approximation via Correlation Decay when Strong Spatial Mixing Fails SICOMP 48(2) 279-349 (2019). https://doi.org/10.1137/16M1083906
Leslie Ann Goldberg, John Lapinskas, Johannes Lengler, Florian Meier, Konstantinos Panagiotou, Pascal Pfister, Asymptotically Optimal Amplifiers for the Moran Process, Theoretical Computer Science 758 (2019) 73-93 https://doi.org/10.1016/j.tcs.2018.08.005 .
Jacob Focke, Leslie Ann Goldberg, Stanislav Zivny, The Complexity of Approximately Counting Retractions . SODA 2019. (see the journal version)

2018

Andreas Galanis, Leslie Ann Goldberg, Kuan Yang, Uniqueness for the 3-State Antiferromagnetic Potts Model on the Tree. Electronic Journal of Probability, Vol 23, paper 82, 1--43.
Antonio Blanca, Andreas Galanis, Leslie Ann Goldberg, Daniel Stefankovic, Eric Vigoda, Kuan Yang, Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs. RANDOM 2018. (see the journal version )
Ivona Bezakova, Andreas Galanis, Leslie Ann Goldberg, and Daniel Stefankovic, Inapproximability of the independent set polynomial in the complex plane . STOC 2018. (see the journal version )
Jacob Focke, Leslie Ann Goldberg, Stanislav Zivny, The Complexity of Counting Surjective Homomorphisms and Compactions. SODA 2018. (see the journal version )

2017

Leslie Ann Goldberg and Heng Guo, The complexity of approximating complex-valued Ising and Tutte partition functions Computational Complexity, (2017) https://doi.org/10.1007/s00037-017-0162-2.
Radu Curticapean, Holger Dell, Fedor Fomin, Leslie Ann Goldberg and John Lapinskas, A Fixed-Parameter Perspective on #BIS. IPEC 2017. (Best Paper Prize.) (see the journal version )
Andreas Galanis, Leslie Ann Goldberg, and Mark Jerrum, A Complexity Trichotomy for Approdximately Counting List H-Colorings ACM TOCT (2017) https://doi.org/10.1145/3037381.
Andrei Bulatov, Leslie Ann Goldberg, Mark Jerrum, David Richerby, Stanislav Živný, Functional Clones and Expressibility of Partition Functions Theoretical Computer Science, 687 (2017) 11-39 https://doi.org/10.1016/j.tcs.2017.05.001.
Andreas Galanis, Leslie Ann Goldberg and Daniel Stefankovic, Inapproximability of the independent set polynomial below the Shearer threshold ICALP 2017:28:1-28:13 (see the journal version)
Andreas Galanis, Leslie Ann Goldberg, Kuan Yang, Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems ICALP 2017:27:1-27:14 (see the journal version )
Andreas Galanis, Andreas Goebel, Leslie Ann Goldberg, John Lapinskas, and David Richerby, Amplifiers for the Moran Process, JACM 2017 https://doi.org/10.1145/3019609.

2016

Andreas Galanis and Leslie Ann Goldberg, The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs Information and Computation, 251:36-66 (2016) http://dx.doi.org/10.1016/j.ic.2016.07.003.
Leslie Ann Goldberg, Rob Gysel and John Lapinskas, Approximately counting locally-optimal structures JCSS 82(6) (2016) 1144-1160. http://dx.doi.org/10.1016/j.jcss.2016.04.001 .
Martin Dyer, Leslie Ann Goldberg and David Richerby, Counting 4x4 Matrix Partitions of Graphs Discrete Applied Mathematics, (2016) http://dx.doi.org/10.1016/j.dam.2016.05.001 .
Andreas Göbel, Leslie Ann Goldberg and David Richerby, Counting Homomorphisms to Square-Free Graphs, Modulo 2, ACM Transactions on Computation Theory (TOCT) 8(3) (2016) Article 12. http://dx.doi.org/10.1145/2898441.
Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Stefankovic and Eric Vigoda, #BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Nonuniqueness Region. JCSS 82 (2016) 690-711. http://dx.doi.org/10.1016/j.jcss.2015.11.009.
Andreas Galanis, Leslie Ann Goldberg,and Mark Jerrum, Approximately Counting H-Colourings is #BIS-Hard SIAM J. Comput., 45(3) 680--711 (2016). http://dx.doi.org/10.1137/15M1020551.
Leslie Ann Goldberg and Mark Jerrum, The complexity of counting locally maximal satisfying assignments of Boolean CSPs TCS Vol 634 Pages 35-56 (2016) http://dx.doi.org/10.1016/j.tcs.2016.04.008 .
Andreas Galanis, Leslie Ann Goldberg and Mark Jerrum, A complexity trichotomy for approximately counting list H-colourings ICALP 2016. (see the journal version )
Andreas Galanis, Andreas Göbel, Leslie Ann Goldberg, John Lapinskas, and David Richerby, Amplifiers for the Moran Process. ICALP 2016. (Best Paper Prize for Track A: Algorithms, Automata, Complexity and Games.) (see the journal version )
Ivona Bezakova, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, and Daniel Stefankovic, Approximation via Correlation Decay when Strong Spatial Mixing Fails ICALP 2016. (see the journal version)
J. Diaz, L.A. Goldberg, D. Richerby and M. Serna, Absorption Time of the Moran Process. http://dx.doi.org/10.1002/rsa.20617 Random Structures and Algorithms (2016)
Andreas Galanis and Leslie Ann Goldberg, The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs SODA 2016. (see the journal version )

2015

L.A. Goldberg and M. Jerrum, A complexity classification of spin systems with an external field. Proceedings of the National Academy of Sciences (PNAS) October 2015. http://www.pnas.org/content/112/43/13161.abstract
Andreas Göbel, Leslie Ann Goldberg, Colin McQuillan, David Richerby and Tomoyuki Yamakami, Counting list matrix partitions of graphs. SICOMP 44(4) 1089-1118, 2015. http://dx.doi.org/10.1137/140963029
Andreas Galanis, Leslie Ann Goldberg,and Mark Jerrum, Approximately Counting H-Colourings is #BIS-Hard ICALP 2015. (see the journal version)
Andreas Göbel, Leslie Ann Goldberg and David Richerby, Counting Homomorphisms to Square-Free Graphs, Modulo 2 ICALP 2015. (see the journal version )
Leslie Ann Goldberg, Rob Gysel and John Lapinskas, Approximately counting locally-optimal structures ICALP 2015 (see the journal version).
Leslie Ann Goldberg, Mark Jerrum, and Colin McQuillan, Approximating the partition function of planar two-state spin systems, JCSS, 2015. http://dx.doi.org/10.1016/j.jcss.2014.06.007
Xi Chen, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, and David Richerby, The complexity of approximating conservative counting CSPs, JCSS, 2015. http://dx.doi.org/10.1016/j.jcss.2014.06.006

2014

L.A. Goldberg and M. Jerrum, The Complexity of Computing the Sign of the Tutte Polynomial, SICOMP 43(6), pages 1921-1952, 2014. http://dx.doi.org/10.1137/12088330X
Andreas Göbel, Leslie Ann Goldberg and David Richerby, The Complexity of Counting Homomorphisms to Cactus Graphs Modulo 2, ACM Transactions on Computation Theory, 2014. http://dx.doi.org/10.1145/2635825
Leslie Ann Goldberg and Mark Jerrum, The Complexity of Approximately Counting Tree Homomorphisms, ACM Transactions on Computation Theory, Volume 6, Issue 2, May 2014 Article No. 8 http://dx.doi.org/10.1145/2600917
Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Stefankovic and Eric Vigoda, #BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Nonuniqueness Region. Proceedings of RANDOM 2014. (see the journal version )
J. Diaz, L.A. Goldberg, D. Richerby and M. Serna, Absorption Time of the Moran Process. Proceedings of RANDOM 2014. (see the journal version )
J. Diaz, L.A. Goldberg, G.B. Mertzios, D. Richerby, M. Serna and P.G. Spirakis, Approximating Fixation Probabilities in the Generalized Moran Process, Algorithmica May 2014, Volume 69, Issue 1, pp 78-91 http://dx.doi.org/10.1007/s00453-012-9722-7
Andreas Göbel, Leslie Ann Goldberg, Colin McQuillan, David Richerby and Tomoyuki Yamakami, Counting list matrix partitions of graphs. Proceedings of CCC 2014. (see the journal version )
Andreas Göbel, Leslie Ann Goldberg and David Richerby, The Complexity of Counting Homomorphisms to Cactus Graphs Modulo 2, Proceedings of STACS 2014. (see the journal version )

2013

A.A. Bulatov, M. Dyer, L.A. Goldberg, M. Jerrum, and C. McQuillan, The expressibility of functions on the Boolean domain, with applications to Counting CSPs , JACM Vol 60 Issue 5 Oct 2013 Article 32. http://dx.doi.org/10.1145/2528401
L.A. Goldberg and M. Jerrum, A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid, SICOMP 42(3) 1132-1157 (2013). http://dx.doi.org/10.1137/110851213
L.A. Goldberg, P.W. Goldberg, P. Krysta, and C. Ventre, Ranking games that have competitiveness-based strategies, TCS 476 24-37 (2013). http://dx.doi.org/10.1016/j.tcs.2013.01.013
J. Diaz, L.A. Goldberg, G.B. Mertzios, D. Richerby, M. Serna and P.G. Spirakis, On the fixation probability of superstars, Proceedings of the Royal Society A vol 469 no 2156 paper 20130193 2013. http://dx.doi.org/10.1098/rspa.2013.0193
Xi Chen, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, and David Richerby, The complexity of approximating conservative counting CSPs, Proceedings of STACS 2013. (see the journal version )
L.A. Goldberg and M. Jerrum, Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials, JCSS 79(1) (February, 2013) 68-78. http://dx.doi.org/10.1016/j.jcss.2012.04.005
B. Doerr and L.A. Goldberg, Adaptive drift analysis, Algorithmica 65(1) 224-250 (January, 2013) http://dx.doi.org/10.1007/s00453-011-9585-3

2012

L.A. Goldberg and M. Jerrum, Approximating the partition function of the ferromagnetic Potts model, Journal of the ACM 59(5) Article 25 (Oct, 2012). http://doi.acm.org/10.1145/2371656.2371660
M. Dyer, L.A. Goldberg, M. Jalsenius and D. Richerby, The Complexity of Approximating Bounded-Degree Boolean #CSP, Information and Computation Volumes 220-221, November-December 2012, pages 1-14. http://dx.doi.org/10.1016/j.ic.2011.12.007
L.A. Goldberg and M. Jerrum, Inapproximability of the Tutte polynomial of a planar graph, Computational Complexity 21(4) 605-642 (2012). http://dx.doi.org/10.1007/s00037-012-0046-4
L.A. Goldberg and M. Jerrum, The Complexity of Computing the Sign of the Tutte Polynomial (and consequent #P-hardness of Approximation), Proceedings of ICALP 2012. (This paper won the "Best Paper Prize" for Track A: Algorithms, Automata, Complexity and Games.) (see the journal version )
P. Chebolu, L.A. Goldberg and R. Martin, The complexity of approximately counting stable matchings, TCS 437 (2012) 35-68. http://dx.doi.org/10.1016/j.tcs.2012.02.029
P. Chebolu, L.A. Goldberg and R. Martin, The complexity of approximately counting stable roommate assignments, JCSS 78(5) (September,2012) 1579-1605 http://dx.doi.org/10.1016/j.jcss.2012.02.003
A. Bulatov, M. Dyer, L.A. Goldberg, M. Jalsenius, M. Jerrum and D. Richerby, The complexity of weighted and unweighted #CSP, JCSS 78(2) (2012) 681--688 http://dx.doi.org/10.1016/j.jcss.2011.12.002
L.A. Goldberg and M. Jerrum, A Counterexample to rapid mixing of the Ge-Stefankovic Process, Electronic Communications in Probability. Vol 17 Article 5 Pages 1--6. (2012). http://dx.doi.org/10.1214/ECP.v17-1712
A.A. Bulatov, M. Dyer, L.A. Goldberg and M. Jerrum, Log-supermodular functions, functional clones and counting CSPs, Proceedings of STACS 2012. This material is included in the journal paper The expressibility of functions on the Boolean domain, with applications to Counting CSPs with McQuillan.
J. Diaz, L.A. Goldberg, G.B. Mertzios, D. Richerby, M. Serna and P.G. Spirakis, Approximating Fixation Probabilities in the Generalized Moran Process, Proceedings of SODA 2012, 954-960 (see the journal version)

2011

L.A. Goldberg and M. Jerrum, A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid, Proceedings of ICALP 2011, 521-532 (see the journal version)
B. Doerr, L.A. Goldberg, L. Minder, T. Sauerwald and C. Scheideler, Stabilizing Consensus With the Power of Two Choices, Proceedings of SPAA 2011, 149-158.

2010

M. Dyer, L.A. Goldberg, and M. Jerrum, A complexity dichotomy for hypergraph partition functions, Computational Complexity 19(4) 605-633 (2010) http://dx.doi.org/10.1007/s00037-010-0300-6
L.A. Goldberg, M. Grohe, M. Jerrum and M. Thurley, A complexity dichotomy for partition functions with mixed signs, SICOMP Volume 39, Issue 7, pp. 3336-3402 (2010) http://dx.doi.org/10.1137/090757496
L.A. Goldberg, M. Jerrum and M. Karpinski, The Mixing Time of Glauber Dynamics for Colouring Regular Trees, Random Structures and Algorithms 36(4) (2010) 464-476 http://dx.doi.org/10.1002/rsa.20303
P. Chebolu, L.A. Goldberg and R. Martin, The complexity of approximately counting stable matchings, Proceedings of APPROX 2010, 81-94. (see the journal version)
B. Doerr, L.A. Goldberg, L. Minder, T. Sauerwald and C. Scheideler, Brief Announcement: Stabilizing Consensus With the Power of Two Choices, Distributed Computing, Lecture Notes in Computer Science Vol 6343 pages 528--530 (2010) http://dx.doi.org/10.1007/978-3-642-15763-9_50
L.A. Goldberg and M. Jerrum, Approximating the partition function of the ferromagnetic Potts model, Proceedings of ICALP 2010, 396-407. (This paper won the "Best Paper Prize" for Track A: Algorithms, Automata, Complexity and Games. See the journal version)
B. Doerr and L.A. Goldberg, Adaptive Drift Analysis, Proceedings of PPSN 2010, 32-41. (see the journal version)
B. Doerr and L.A. Goldberg, Drift Analysis with Tail Bounds, Proceedings of PPSN 2010, 174-183. (This material is included in the journal paper Adaptive Drift Analysis)
M. Dyer, L.A. Goldberg, and M. Jerrum, An approximation trichotomy for Boolean #CSP, JCSS 76 (2010) 267-277. http://dx.doi.org/10.1016/j.jcss.2009.08.003
L.A. Goldberg, P.W. Goldberg, P. Krysta, and C. Ventre, Ranking games that have competitiveness-based strategies, Proceedings of EC 2010, 335-344. (see the journal version)
M. Dyer, L.A. Goldberg, M. Jalsenius and D. Richerby, The Complexity of Approximating Bounded-Degree Boolean #CSP, Proceedings of STACS 2010. See the journal version)

2009

E. Elkind, L.A. Goldberg, P.W. Goldberg and M. Wooldridge, On The Computational Complexity of Weighted Voting Games, Annals of Mathematics and Artificial Intelligence http://dx.doi.org/10.1007/s10472-009-9162-5
A. Bulatov, M. Dyer, L.A. Goldberg, M. Jalsenius and D. Richerby, The Complexity of Weighted Booleam #CSP with Mixed Signs, Theoretical Computer Science 410 (2009) 3949--3961 http://dx.doi.org/10.1016/j.tcs.2009.06.003
E. Elkind, L.A. Goldberg, P. Goldberg and M. Wooldridge, A tractable and expressive class of marginal contribution nets and its applications. Mathematical Logical Quarterly Vol 55 Issue 4 (2009) 362-376 http://dx.doi.org/10.1002/malq.200810021
M. Dyer, L.A. Goldberg, and M. Jerrum, Matrix norms and rapid mixing for spin systems, Annals of Applied Probability, 2009, Vol 19, No 1, 71-107 http://dx.doi.org/10.1214/08-AAP532
L.A. Goldberg, M. Grohe, M. Jerrum and M. Thurley, A complexity dichotomy for partition functions with mixed signs, Proceedings of STACS 2009. (see the journal version)
M. Dyer, L.A. Goldberg, and M. Jerrum, The Complexity of Weighted Boolean #CSP, SIAM Journal on Computing 38(5) (Jan 2009) 1970-1986 http://dx.doi.org/10.1137/070690201

2008

M. Dyer, L.A. Goldberg, and M. Jerrum, Dobrushin conditions and Systematic Scan, Combinatorics, Probability, and Computing 17(6) 749-757 (2008) http://dx.doi.org/10.1017/S0963548308009437
E. Elkind, L.A. Goldberg, P. Goldberg and M. Wooldridge, on the dimensionality of voting games AAAI 2008 69-74.
E. Elkind, L.A. Goldberg, P. Goldberg and M. Wooldridge, A tractable and expressive class of marginal contribution nets and its applications. AAMAS 2008. (see the journal version)
L.A. Goldberg and M. Jerrum, Inapproximability of the Tutte polynomial, Information and Computation 206(7) (July 2008) 908--929 http://dx.doi.org/10.1016/j.ic.2008.04.003

2007

M. Dyer, L.A. Goldberg and M. Paterson, On counting homomorphisms to directed acyclic graphs, J. ACM 54, 6, Article 27 (December 2007) http://doi.acm.org/10.1145/1314690.1314691
P. Berenbrink, T. Friedetzky, L.A. Goldberg, P. Goldberg, Z. Hu and R. Martin, Distributed Selfish Load Balancing, SICOMP Volume 37 Issue 4 Pages 1163-1181, 2007 Society for Industrial and Applied Mathematics http://dx.doi.org/10.1137/060660345
E. Elkind, L.A. Goldberg and P.W. Goldberg, Computing Good Nash Equilibria in Graphical Games, Proceedings of the 8th ACM Conference on Electronic Commerce (San Diego, California, USA, June 11 - 15, 2007). EC '07. ACM Press, New York, NY, 162-171. http://doi.acm.org/10.1145/1250910.1250935
E. Elkind, L.A. Goldberg and P.W. Goldberg, Frugality Ratios And Improved Truthful Mechanisms for Vertex Cover, Proceedings of the 8th ACM Conference on Electronic Commerce (San Diego, California, USA, June 11 - 15, 2007). EC '07. ACM Press, New York, NY, 336-345. http://doi.acm.org/10.1145/1250910.1250959
E. Elkind, L.A. Goldberg, P.W. Goldberg and M. Wooldridge, Computational Complexity of Weighted Threshold Games, Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence (AAAI-07) 2007 718 - 723. http://www.aaai.org/Library/AAAI/aaai07contents.php (see the journal version On The Computational Complexity of Weighted Voting Games)
L.A. Goldberg and M. Jerrum, Inapproximability of the Tutte polynomial, Proceedings of the Thirty-Ninth Annual ACM Symposium on theory of Computing (San Diego, California, USA, June 11 - 13, 2007). STOC '07. ACM Press, New York, NY, 459-468. http://doi.acm.org/10.1145/1250790.1250858 (see the journal version)
L.A. Goldberg and M. Jerrum, The Complexity of Ferromagnetic Ising with Local Fields, Comb. Probab. Comput. 16, 1 (2007), 43-61. http://dx.doi.org/10.1017/S096354830600767X

2006

P. Berenbrink, T. Friedetzky, L.A. Goldberg, P. Goldberg, Z. Hu and R. Martin, Distributed Selfish Load Balancing, Proceedings of SODA 2006. (see the journal version)
P. Berenbrink, L.A. Goldberg, P. Goldberg, R. Martin, Utilitarian Resource Assignment, Journal of Discrete Algorithms, Volume 4, Issue 4 , December 2006, Pages 567-587, http://dx.doi.org/10.1016/j.jda.2005.06.009
M. Cryan, M. Dyer, L.A. Goldberg, M. Jerrum and R. Martin, Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows, SIAM Journal of Computing vol 36 no 1 pp 247-278 (2006)
M. Dyer, L.A. Goldberg, and M. Jerrum, Dobrushin conditions and Systematic Scan, Proc. 10th International Workshop on Randomization and Computation (RANDOM), Lecture Notes in Computer Science 4110, Springer, 2006, pp. 327-338 (see the journal version)
M. Dyer, L. A. Goldberg and M. Jerrum, Systematic scan for sampling colourings, The Annals of Applied Probability 16(1), 185-230, 2006 Euclid
M. Dyer, L.A. Goldberg, M. Jerrum and R. Martin, Markov chain comparison, Probability Surveys 3 (2006) 89-111.
M. Dyer, L.A. Goldberg and M. Paterson, On counting homomorphisms to directed acyclic graphs, Proceedings of 33rd ICALP 2006, pages 38-49. (This paper won the "Best Paper Prize" for Track A: Algorithms, Automata, Complexity and Games. The journal version is here)
E. Elkind, L.A. Goldberg and P.W. Goldberg, Nash Equilibria in Graphical Games on Trees Revisited, ACM Conference on Electronic Commerce EC'06, 2006.
L.A. Goldberg, M. Jalsenius, R. Martin and M. Paterson, Improved mixing bounds for the Anti-Ferromagnetic Potts Model on Z^2, LMS J. Comput. Math. 9 (2006) 1 --20.

2005

L.A. Goldberg, R. Martin and M. Paterson, Strong Spatial Mixing for Lattice Graphs with Fewer Colours, SICOMP, 35(2) 486-517 (2005).

2004

M. Dyer, L.A. Goldberg, and M. Jerrum, Counting and Sampling H-colourings, Information and Computation 189 (2004) 1-16.
L.A. Goldberg, M. Jerrum, S. Kannan and M. Paterson, A bound on the capacity of backoff and acknowledgement-based protocols, SICOMP, 33(2) 313--331 (2004), copyright SIAM
L.A. Goldberg, S.Kelk and M.Paterson, The complexity of choosing an H-colouring (nearly) uniformly at random, SICOMP, 33(2) 416-432 (2004) copyright SIAM
L.A. Goldberg, R. Martin and M. Paterson, Random sampling of 3-colourings in Z^2, Random Structures and Algorithms 24(3) 279-302 (2004) .
L.A. Goldberg, R. Martin and M. Paterson, Strong Spatial Mixing for Lattice Graphs with Fewer Colours, Proceedings of FOCS 2004. (see the journal version)

2003

M. Adler, P. Berenbrink, T. Friedetzky, L.A. Goldberg, P. Goldberg and M. Paterson, A Proportionate Fair Scheduling Rule with Good Worst-case Performance, Proceedings of SPAA 2003.
P. Berenbrink , T. Friedetzky and L.A. Goldberg, The Natural Work-Stealing Algorithm is Stable, SICOMP 32(5) 1260-1279 (2003), copyright SIAM
M. Dyer, L.A. Goldberg, C. Greenhill and M. Jerrum, The relative complexity of approximate counting problems, Algorithmica 38(3) 471-500 (2003)
L.A. Goldberg, M. Jerrum and M.Paterson, The computational complexity of two-state spin systems, Random Structures and Algorithms, 23(2) 133-154 (2003). http://dx.doi.org/10.1002/rsa.1009

2002

M. Cryan, M. Dyer, L.A. Goldberg, M. Jerrum and R. Martin, Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows, Proceedings of FOCS 2002 (see the journal version)
M. Dyer, L.A. Goldberg, C. Greenhill, G. Istrate and M. Jerrum, Convergence of the Iterated Prisoner's Dilemma game, Combinatorics, Probability and Computing (11) 135-147, 2002, copyright Cambridge University Press.
M. Dyer, L.A. Goldberg, and M. Jerrum, Counting and Sampling H-colourings, Proceedings of RANDOM 2002 (see the journal version)
Leslie Ann Goldberg and Mark Jerrum, The "Burnside Process" Converges Slowly, Combinatorics, Probability and Computing (11) 21-34, 2002, copyright Cambridge University Press.
L.A. Goldberg, S.Kelk and M.Paterson, The complexity of choosing an H-colouring (nearly) uniformly at random, Proceedings of STOC (2002) (see the journal version)

2001

H. Al-Ammal, L.A. Goldberg and P. MacKenzie, An improved stability bound for binary exponential backoff, Theory of Computing Systems 30:229-244 (2001).
P. Berenbrink , T. Friedetzky and L.A. Goldberg, The Natural Work-Stealing Algorithm is Stable, Proceedings FOCS 2001 (see the journal version)
M. Cryan, L.A. Goldberg and P.W. Goldberg, Evolutionary Trees can be Learned in Polynomial Time in the Two-State General Markov Model, SICOMP 31(2):375-397 (2001), copyright SIAM.
M. Dyer, L.A. Goldberg, C. Greenhill, M. Jerrum and M. Mitzenmacher, An extension of path coupling and its application to the Glauber dynamics for graph colourings, SIAM Journal of Computing volume 30, number 6, (2001), pp. 1962 -- 1975, copyright SIAM.
L.A. Goldberg, Computation in permutation groups: counting and randomly sampling orbits. In J.W.P. Hirschfeld, editor, Surveys in Combinatorics, volume 288 of London Mathematical Society Lecture Note Series, pages 109-143. Cambridge University press, 2001.
L.A. Goldberg, P. W. Goldberg, M. Paterson, P. Pevzner, S.C. Sahinalp and E. Sweedyk, The Complexity of Gene Placement, Journal of Algorithms 41(2) 225--243, 2001.
L.A. Goldberg, M. Paterson, A. Srinivasan and E. Sweedyk, Better approximation guarantees for job-shop scheduling, SIAM Journal on Discrete Mathematics, 14(1) (2001) 67--92, copyright SIAM.

2000

M. Adler, F. Fich, L.A. Goldberg and M. Paterson, Tight size bounds for packet headers in narrow meshes, Proceedings of ICALP 27, LNCS vol 1853 pages 756-767, 2000, (copyright Springer-Verlag).
H. Al-Ammal, L.A. Goldberg and P. MacKenzie, Binary exponential backoff is stable for high arrival rates, Proceedings of STACS 17, Lecture Notes in Computer Science 1770 (2000) 169-180 (see the journal version)
M. Dyer, L.A. Goldberg, C. Greenhill and M. Jerrum, On the relative complexity of approximate counting problems, Proceedings of APPROX 2000 (see the journal version)
M. Dyer, L.A. Goldberg, C. Greenhill, M. Jerrum and M. Mitzenmacher, An extension of path coupling and its application to the Glauber dynamics for graph colourings, Proceedings of SODA 11 (2000) 616-624 (see the journal version)
L.A. Goldberg and M. Jerrum, Counting unlabelled subtrees of a tree is #P-Complete, LMS Journal of Computation and Mathematics, 3 (2000) 117-124.
L.A. Goldberg, M. Jerrum, S. Kannan and M. Paterson, A bound on the capacity of backoff and acknowledgement-based protocols, Proceedings of ICALP 27 Lecture Notes in Computer Science 1853 705-716 (2000) (see the journal version)
L.A. Goldberg, P.D. MacKenzie, M. Paterson and A. Srinivasan, Contention Resolution with Constant Expected Delay, Journal of the ACM, 47(6):1048--1096, 2000.

1999

M. Cryan, L.A. Goldberg and C. A. Phillips, Approximation Algorithms for the Fixed-Topology Phylogenetic Number Problem, Algorithmica 25 (1999) 311-329
L.A. Goldberg, P. W. Goldberg, M. Paterson, P. Pevzner, S.C. Sahinalp and E. Sweedyk, The Complexity of Gene Placement, Proceedings of SODA 10 (1999) 386-395 (see the journal version)
L.A. Goldberg, W.E. Hart and D.B. Wilson, Analysis of a simple learning algorithm: Learning foraging thresholds for lizards, Journal of Theoretical Biology, 197 (1999) 361-369.
L.A. Goldberg and M. Jerrum, Randomly Sampling Molecules, SIAM Journal on Computing 29(3) (1999) 834-853, copyright SIAM.
L.A. Goldberg and P.D. MacKenzie, Analysis of Practical Backoff Protocols for Contention Resolution with Multiple Servers. Journal of Computer and System Sciences 58 (1999) 232--258.
L.A. Goldberg, Y, Matias and S. Rao, An Optical Simulation of Shared Memory. SIAM Journal on Computing 28(5) (1999) 1829-1847, copyright SIAM.

1998

M. Cryan, L.A. Goldberg and P.W. Goldberg, Evolutionary Trees can be Learned in Polynomial Time in the Two-State General Markov Model, Proceedings of FOCS 39 (1998) 436-445 (see the journal version)
L.A. Goldberg, P.W. Goldberg, C.A. Phillips and G.B. Sorkin, Constructing Computer Virus Phylogenies, Journal of Algorithms 26(1) (1998) 188-208.
L.A. Goldberg and M. Jerrum, The "Burnside Process" Converges Slowly, Proceedings of RANDOM 2, Springer Lecture Notes in Computer Science 1518 (1998) 331-345 (see the journal version)
L.A. Goldberg, M. Jerrum and P. MacKenzie, An Omega(log log n) Lower Bound for Routing in Optical Networks, SIAM Journal on Computing, 27(4) (1998) 1083-1098. copyright SIAM

1997

M. Cryan, L.A. Goldberg and C.A. Phillips, Approximation Algorithms for the Fixed-Topology Phylogenetic Number Problem, Proceedings of Combinatorial Pattern Matching (CPM) 8 (1997) 130-149. (see the journal version)
L.A. Goldberg and M. Jerrum, Randomly Sampling Molecules, Proceedings of SODA 8 (1997) 183-192 (see the journal version)
L.A. Goldberg, M. Jerrum, T. Leighton, and S. Rao, Doubly Logarithmic Communication Algorithms for Optical Communication Parallel Computers, SIAM Journal on Computing, 26(4) (1997) 1100-1119, copyright SIAM.
L.A. Goldberg and P.D. MacKenzie Contention Resolution with Guaranteed Constant Expected Delay, Proceedings of FOCS 38 (1997), 213-222. (this material was included in the journal paper Contention Resolution with Constant Expected Delay with Paterson and Srinivasan)
L.A. Goldberg, M. Paterson, A. Srinivasan and E. Sweedyk, Better Approximation Guarantees for Job-Shop Scheduling, Proceedings of SODA (1997) 599-608. (see the journal version)

1996

L.A. Goldberg, P.W. Goldberg, C.A. Phillips and G.B. Sorkin, Constructing Computer Virus Phylogenies, Proceedings of Combinatorial Pattern Matching (CPM) (1996) 253-270 (see the journal version )
L.A. Goldberg, P.W. Goldberg, C. Phillips, Z. Sweedyk and T. Warnow, Minimizing Phylogenetic Number to find Good Evolutionary Trees. Discrete Applied Mathematics 71(1-3) (1996) 111-136.
L.A. Goldberg, W.E. Hart and D.B. Wilson, Analysis of a Simple Learning Algorithm: Learning Foraging Thresholds for Lizards, Proceedings of Conference on Computational Learning Theory (COLT) 9 (1996) 2-9. (see the journal version) )
L.A. Goldberg and P.D. MacKenzie, Analysis of Practical Backoff Protocols for Contention Resolution with Multiple Servers, Proceedings of SODA 7 (1996) 554-563. (see the journal version)

1995

L.A. Goldberg, Routing in Optical Networks: The Problem of Contention, in Interconnection Networks and Mapping and Scheduling Parallel Computations, DIMACS Series in Discrete Mathematics Vol 21, (Frank Hsu, Arnold Rosenberg and Dominique Sotteau, eds.) American Mathematical Society 1995. 173-180 http://www.ams.org/bookstore?fn=20&arg1=app-dm&ikey=DIMACS-21
L.A. Goldberg, P.W. Goldberg, C.A. Phillips, E. Sweedyk and T. Warnow, Minimizing Phylogenetic Number to find Good Evolutionary Trees, Proceedings of Combinatorial Pattern Matching (CPM) 6 (1995) 102-127. (see the journal version in 1996)

1994

L.A. Goldberg, Listing Graphs that Satisfy First Order Sentences, Journal of Computer and Systems Sciences 49(2) (1994) 408--424. http://dx.doi.org/10.1016/S0022-0000(05)80057-1
L.A. Goldberg, M. Jerrum and P. MacKenzie, An Omega(log log n) Lower Bound for Routing in Optical Networks. Proceedings of ACM Symposium on Parallel Algorithms and Architectures (SPAA) 6 (1994) 147-146. (see the journal version)
L.A. Goldberg, Y. Matias and S. Rao, An Optical Simulation of Shared Memory, Proceedings of ACM Symposium on Parallel Algorithms and Architectures (SPAA) 6 (1994) 257-267. (see the journal version)

1993

L.A. Goldberg, Automating Polya Theory: The Computational Complexity of the Cycle Index Polynomial, Information and Computation 105(2) (1993) 268--288. http://dx.doi.org/10.1006/inco.1993.1045
L.A. Goldberg, Efficient Algorithms for Listing Combinatorial Structures, (Cambridge University Press, 1993). http://ebooks.cambridge.org/ebook.jsf?bid=CBO9780511569913 (One of three winners of the UK Distinguished Dissertations in Computer Science Prize.)
L.A. Goldberg, Listing Graphs that Satisfy First Order Sentences, Proceedings of STOC (1993) 218-225. (see the journal version in 1994)
L.A. Goldberg, M. Jerrum, T. Leighton, and S. Rao, Doubly Logarithmic Communication Algorithms for Optical Communication Parallel Computers, Proceedings of ACM Symposium on Parallel Algorithms and Architectures (SPAA) 5 (1993) 300-309. (see the journal version)

1992

L.A. Goldberg, Efficient Algorithms for Listing Unlabeled Graphs, Journal of Algorithms 13(1) (1992) 128--143. http://dx.doi.org/10.1016/0196-6774(92)90009-2

1990

L.A. Henderson, R.E. Hiromoto, O.M. Lubeck, and M.L. Simmons, On the Use of Diagnostic Dependence-Analysis Tools in Parallel Programming: Experiences Using PTOOL, The Journal of Supercomputing 4 (1990) 83--96. http://dx.doi.org/10.1007/BF00162344 (This paper was written when I was an undergraduate student using my original name, Leslie Ann Henderson)