×

Goldberg, Leslie Ann

Compute Distance To:
Author ID: goldberg.leslie-ann Recent zbMATH articles by "Goldberg, Leslie Ann"
Published as: Goldberg, Leslie Ann; Goldberg, Leslie A.; Goldberg, L. A.; Goldberg, Leslie Anne
External Links: MGP · ORCID · Wikidata · dblp
all top 5

Co-Authors

8 single-authored
59 Jerrum, Mark R.
30 Galanis, Andreas
28 Dyer, Martin E.
22 Richerby, David M.
16 Paterson, Mike S.
11 Goldberg, Paul W.
11 Martin, Russell A.
11 Štefankovič, Daniel
9 Lapinskas, John
7 Göbel, Andreas-Nikolas
7 Živný, Stanislav
6 Bezáková, Ivona
6 Bulatov, Andrei A.
6 Guo, Heng
6 Mcquillan, Colin
6 Yang, Kuan
5 Díaz, Josep
5 Focke, Jacob
5 Greenhill, Catherine S.
5 Jalsenius, Markus
5 Serna Iglesias, Maria José
5 Sweedyk, Elizabeth
5 Vigoda, Eric
4 Berenbrink, Petra
4 MacKenzie, Philip D.
3 Chebolu, Prasad
3 Cryan, Mary
3 Friedetzky, Tom
3 Herrera-Poyatos, Andrés
3 Mertzios, George B.
3 Phillips, Cynthia A.
3 Spirakis, Paul G.
3 Srinivasan, Aravind
2 Aceto, Luca
2 Al-Ammal, Hesham
2 Backens, Miriam
2 Blanca, Antonio
2 Cai, Jin-Yi
2 Chen, Xi
2 Curticapean, Radu
2 Damgård, Ivan Bjerre
2 Dell, Holger
2 Elkind, Edith
2 Fomin, Fedor V.
2 Grohe, Martin
2 Gysel, Rob
2 Halldórsson, Magnús Mar
2 Hu, Zengjian
2 Ingólfsdóttir, Anna
2 Kannan, Sampath K.
2 Kelk, Steven
2 Lu, Pinyan
2 Mitzenmacher, Michael
2 Pevzner, Pavel A.
2 Sahinalp, Suleyman Cenk
2 Thurley, Marc
2 Walukiewicz, Igor
2 Wooldridge, Michael J.
1 Adler, Micah
1 Doerr, Benjamin
1 Fich, Faith Ellen
1 Istrate, Gabriel I.
1 Jansen, Klaus
1 Karpinski, Marek
1 Krysta, Piotr
1 Leighton, Tom
1 Lengler, Johannes
1 MacKenzie, Phil
1 Matias, Yossi
1 Meier, Florian
1 Panagiotou, Konstantinos D.
1 Pfister, Pascal
1 Ravi, Ramamoorthi
1 Rolim, José D. P.
1 Roth, Marc
1 Sorkin, Gregory B.
1 Ventre, Carmine
1 Warnow, Tandy J.
1 Yamakami, Tomoyuki

Publications by Year

Citations contained in zbMATH Open

122 Publications have been cited 925 times in 479 Documents Cited by Year
The relative complexity of approximate counting problems. Zbl 1138.68424
Dyer, Martin; Goldberg, Leslie Ann; Greenhill, Catherine; Jerrum, Mark
57
2004
The complexity of weighted Boolean #CSP. Zbl 1191.68351
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
38
2009
Inapproximability of the Tutte polynomial. Zbl 1153.68039
Goldberg, Leslie Ann; Jerrum, Mark
30
2008
A complexity dichotomy for partition functions with mixed signs. Zbl 1298.68099
Goldberg, Leslie Ann; Grohe, Martin; Jerrum, Mark; Thurley, Marc
29
2010
On the computational complexity of weighted voting games. Zbl 1185.91081
Elkind, Edith; Goldberg, Leslie Ann; Goldberg, Paul W.; Wooldridge, Michael
28
2009
An approximation trichotomy for Boolean #CSP. Zbl 1201.68154
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
27
2010
On counting homomorphisms to directed acyclic graphs. Zbl 1312.68098
Dyer, Martin E.; Goldberg, Leslie Ann; Paterson, Mike
26
2007
Approximating the partition function of the ferromagnetic Potts model. Zbl 1281.68116
Goldberg, Leslie Ann; Jerrum, Mark
26
2012
Adaptive drift analysis. Zbl 1277.68289
Doerr, Benjamin; Goldberg, Leslie Ann
25
2013
On the fixation probability of superstars. Zbl 1371.92097
Díaz, Josep; Goldberg, Leslie Ann; Mertzios, George B.; Richerby, David; Serna, Maria; Spirakis, Paul G.
24
2013
Markov chain comparison. Zbl 1189.60135
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Martin, Russell
24
2006
Approximating fixation probabilities in the generalized Moran process. Zbl 1303.92095
Díaz, Josep; Goldberg, Leslie Ann; Mertzios, George B.; Richerby, David; Serna, Maria; Spirakis, Paul G.
23
2014
The computational complexity of two-state spin systems. Zbl 1030.82001
Goldberg, Leslie Ann; Jerrum, Mark; Paterson, Mike
23
2003
Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows. Zbl 1117.62062
Cryan, Mary; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Martin, Russell
18
2006
The complexity of ferromagnetic Ising with local fields. Zbl 1170.82001
Goldberg, Leslie Ann; Jerrum, Mark
17
2007
Strong spatial mixing with fewer colors for lattice graphs. Zbl 1091.60013
Goldberg, Leslie Ann; Martin, Russell; Paterson, Mike
17
2005
Contention resolution with constant expected delay. Zbl 1094.68518
Goldberg, Leslie Ann; MacKenzie, Philip D.; Paterson, Mike; Srinivasan, Aravind
17
2000
Efficient algorithms for listing combinatorial structures. Zbl 0821.68059
Goldberg, Leslie Ann
16
1993
Absorption time of the Moran process. Zbl 1359.92093
Díaz, Josep; Goldberg, Leslie Ann; Richerby, David; Serna, Maria
16
2014
The expressibility of functions on the Boolean domain, with applications to counting CSPs. Zbl 1281.68131
Bulatov, Andrei A.; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Mcquillan, Colin
15
2013
The complexity of weighted Boolean #CSP with mixed signs. Zbl 1171.68013
Bulatov, Andrei; Dyer, Martin; Goldberg, Leslie Ann; Jalsenius, Markus; Richerby, David
14
2009
\(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region. Zbl 1338.68086
Cai, Jin-Yi; Galanis, Andreas; Goldberg, Leslie Ann; Guo, Heng; Jerrum, Mark; Štefankovič, Daniel; Vigoda, Eric
14
2016
A tractable and expressive class of marginal contribution nets and its applications. Zbl 1175.91022
Elkind, Edith; Goldberg, Leslie Ann; Goldberg, Paul W.; Wooldridge, Michael
13
2009
Random sampling of 3-colorings in \({\mathbb Z}^{2}\). Zbl 1044.60100
Goldberg, Leslie Ann; Martin, Russell; Paterson, Mike
13
2004
A bound on the capacity of backoff and acknowledgment-based protocols. Zbl 1078.68552
Goldberg, Leslie Ann; Jerrum, Mark; Kannan, Sampath; Paterson, Mike
12
2004
Systematic scan for sampling colorings. Zbl 1095.60024
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
12
2006
The complexity of weighted and unweighted \(\#\)CSP. Zbl 1282.68110
Bulatov, Andrei; Dyer, Martin; Goldberg, Leslie Ann; Jalsenius, Markus; Jerrum, Mark; Richerby, David
11
2012
Evolutionary trees can be learned in polynomial time in the two-state general Markov model. Zbl 1052.68061
Cryan, Mary; Goldberg, Leslie Ann; Goldberg, Paul W.
10
2001
Approximately counting \(H\)-colorings is \(\#\)BIS-hard. Zbl 1342.68147
Galanis, Andreas; Goldberg, Leslie Ann; Jerrum, Mark
9
2016
The complexity of choosing an \(H\)-coloring (nearly) uniformly at random. Zbl 1105.68114
Goldberg, Leslie Ann; Kelk, Steven; Paterson, Mike
8
2004
The complexity of approximating complex-valued Ising and Tutte partition functions. Zbl 1382.68090
Goldberg, Leslie Ann; Guo, Heng
7
2017
The complexity of approximating conservative counting CSPs. Zbl 1354.68114
Chen, Xi; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Lu, Pinyan; McQuillan, Colin; Richerby, David
7
2015
Dobrushin conditions and systematic scan. Zbl 1168.60035
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
7
2008
Utilitarian resource assignment. Zbl 1124.91042
Berenbrink, Petra; Goldberg, Leslie Ann; Goldberg, Paul W.; Martin, Russell
7
2006
Improved mixing bounds for the anti-ferromagnetic Potts model on \(\mathbb Z^2\). Zbl 1122.82007
Goldberg, Leslie Ann; Jalsenius, Markus; Martin, Russell; Paterson, Mike
7
2006
Distributed selfish load balancing. Zbl 1192.68094
Berenbrink, Petra; Friedetzky, Tom; Goldberg, Leslie Ann; Goldberg, Paul; Hu, Zengjian; Martin, Russell
7
2006
Distributed selfish load balancing. Zbl 1141.68018
Berenbrink, Petra; Friedetzky, Tom; Goldberg, Leslie Ann; Goldberg, Paul W.; Hu, Zengjian; Martin, Russell
7
2007
Matrix norms and rapid mixing for spin systems. Zbl 1166.15015
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
6
2009
An optical simulation of shared memory. Zbl 0928.68134
Goldberg, Leslie Ann; Matias, Yossi; Rao, Satish
6
1999
Minimizing phylogenetic number to find good evolutionary trees. Zbl 0880.92030
Goldberg, Leslie Ann; Goldberg, Paul W.; Phillips, Cynthia A.; Sweedyk, Elizabeth; Warnow, Tandy
6
1996
Approximating the partition function of the ferromagnetic Potts model. Zbl 1288.68091
Goldberg, Leslie Ann; Jerrum, Mark
6
2010
The mixing time of Glauber dynamics for coloring regular trees. Zbl 1348.68172
Goldberg, Leslie Ann; Jerrum, Mark; Karpinski, Marek
6
2010
Better approximation guarantees for job-shop scheduling. Zbl 0967.68084
Goldberg, Leslie Ann; Paterson, Mike; Srinivasan, Aravind; Sweedyk, Elizabeth
6
2001
The complexity of approximating bounded-degree Boolean #CSP. Zbl 1230.68105
Dyer, Martin; Goldberg, Leslie Ann; Jalsenius, Markus; Richerby, David
6
2010
Counting and sampling \(H\)-colourings. Zbl 1082.68079
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
6
2004
Convergence of the iterated prisoner’s dilemma game. Zbl 1006.60009
Dyer, Martin; Goldberg, Leslie Ann; Greenhill, Catherine; Istrate, Gabriel; Jerrum, Mark
6
2002
Absorption time of the Moran process. Zbl 1344.05135
Díaz, Josep; Goldberg, Leslie Ann; Richerby, David; Serna, Maria
6
2016
A complexity classification of spin systems with an external field. Zbl 1355.68120
Goldberg, Leslie Ann; Jerrum, Mark
6
2015
Amplifiers for the Moran process. Zbl 1426.68296
Galanis, Andreas; Göbel, Andreas; Goldberg, Leslie Ann; Lapinskas, John; Richerby, David
5
2017
Inapproximability of the independent set polynomial in the complex plane. Zbl 1427.68229
Bezáková, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Štefankovič, Daniel
5
2018
Construction computer virus phylogenies. Zbl 0891.68045
Goldberg, Leslie Ann; Goldberg, Paul W.; Phillips, Cynthia A.; Sorkin, Gregory B.
5
1998
Inapproximability of the Tutte polynomial of a planar graph. Zbl 1282.68122
Goldberg, Leslie Ann; Jerrum, Mark
5
2012
Inapproximability of the Tutte polynomial. Zbl 1232.68073
Goldberg, Leslie Ann; Jerrum, Mark
5
2007
A complexity dichotomy for partition functions with mixed signs. Zbl 1236.68092
Goldberg, Leslie Ann; Grohe, Martin; Jerrum, Mark; Thurley, Marc
5
2009
Approximately counting locally-optimal structures. Zbl 1342.68163
Goldberg, Leslie Ann; Gysel, Rob; Lapinskas, John
5
2016
Better approximation guarantees for job-shop scheduling. Zbl 1321.68503
Goldberg, Leslie Ann; Paterson, Mike; Srinivasan, Aravind; Sweedyk, Elizabeth
5
1997
A counterexample to rapid mixing of the Ge-Stefankovic process. Zbl 1246.60094
Goldberg, Leslie Ann; Jerrum, Mark
5
2012
The complexity of approximating bounded-degree Boolean \(\#\)CSP. Zbl 1282.68136
Dyer, Martin; Goldberg, Leslie Ann; Jalsenius, Markus; Richerby, David
5
2012
The complexity of approximately counting in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs. Zbl 1353.68128
Galanis, Andreas; Goldberg, Leslie Ann
5
2016
A complexity trichotomy for approximately counting list \(H\)-colorings. Zbl 1427.68121
Galanis, Andreas; Goldberg, Leslie Ann; Jerrum, Mark
4
2017
Doubly logarithmic communication algorithms for optical-communication parallel computers. Zbl 0885.68079
Goldberg, Leslie Ann; Jerrum, Mark; Leighton, Tom; Rao, Satish
4
1997
Analysis of practical backoff protocols for contention resolution with multiple servers. Zbl 0938.68012
Goldberg, Leslie Ann; MacKenzie, Philip D.
4
1999
Dobrushin conditions and systematic scan. Zbl 1155.60331
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
4
2006
The complexity of approximately counting stable matchings. Zbl 1304.68069
Chebolu, Prasad; Goldberg, Leslie Ann; Martin, Russell
4
2010
The natural work-stealing algorithm is stable. Zbl 1027.60082
Berenbrink, Petra; Friedetzky, Tom; Goldberg, Leslie Ann
4
2003
Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials. Zbl 1258.05020
Goldberg, Leslie Ann; Jerrum, Mark
4
2013
The complexity of computing the sign of the Tutte polynomial (and consequent #P-hardness of approximation). Zbl 1272.68155
Goldberg, Leslie Ann; Jerrum, Mark
4
2012
The complexity of counting homomorphisms to cactus graphs modulo 2. Zbl 1347.68181
Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David
4
2014
The complexity of computing the sign of the Tutte polynomial. Zbl 1437.68068
Goldberg, Leslie Ann; Jerrum, Mark
4
2014
Inapproximability of the independent set polynomial in the complex plane. Zbl 1476.68193
Bezáková, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Štefankovič, Daniel
3
2020
Approximation via correlation decay when strong spatial mixing fails. Zbl 1388.68300
Bezáková, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Guo, Heng; Štefankovič, Daniel
3
2016
Counting homomorphisms to square-free graphs, modulo 2. Zbl 1427.68241
Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David
3
2016
Approximation via correlation decay when strong spatial mixing fails. Zbl 1422.68270
Bezáková, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Guo, Heng; Štefankovič, Daniel
3
2019
The complexity of approximating the matching polynomial in the complex plane. Zbl 07495903
Bezáková, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Štefankovič, Daniel
3
2021
Holant clones and the approximability of conservative holant problems. Zbl 1484.68144
Backens, Miriam; Goldberg, Leslie Ann
3
2020
An extension of path coupling and its application to the Glauber dynamics for graph colorings. Zbl 0999.05035
Dyer, Martin; Goldberg, Leslie Ann; Greenhill, Catherine; Jerrum, Mark; Mitzenmacher, Michael
3
2001
The complexity of choosing an \(H\)-colouring (nearly) uniformly at random. Zbl 1192.68898
Goldberg, Leslie Ann; Kelk, Steven; Paterson, Mike
3
2002
Sampling in uniqueness from the Potts and random-cluster models on random regular graphs. Zbl 1436.82004
Blanca, Antonio; Galanis, Andreas; Goldberg, Leslie Ann; Štefankovič, Daniel; Vigoda, Eric; Yang, Kuan
3
2020
A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid. Zbl 1333.68122
Goldberg, Leslie Ann; Jerrum, Mark
3
2011
The complexity of approximately counting tree homomorphisms. Zbl 1321.68312
Goldberg, Leslie Ann; Jerrum, Mark
3
2014
The complexity of approximately counting stable roommate assignments. Zbl 1244.68038
Chebolu, Prasad; Goldberg, Leslie Ann; Martin, Russell
3
2012
The complexity of approximately counting stable matchings. Zbl 1310.68103
Chebolu, Prasad; Goldberg, Leslie Ann; Martin, Russell
3
2012
Counting unlabelled subtrees of a tree is \(\# P\)-complete. Zbl 0951.68047
Goldberg, Leslie Ann; Jerrum, Mark
3
2000
The complexity of approximating conservative counting CSPs. Zbl 1354.68115
Chen, Xi; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Lu, Pinyan; Mcquillan, Colin; Richerby, David
3
2013
Amplifiers for the Moran process. Zbl 1388.68296
Galanis, Andreas; Göbel, Andreas; Goldberg, Leslie Ann; Lapinskas, John; Richerby, David
2
2016
Approximating the partition function of planar two-state spin systems. Zbl 1401.05279
Goldberg, Leslie Ann; Jerrum, Mark; McQuillan, Colin
2
2015
Approximating pairwise correlations in the Ising model. Zbl 07143739
Goldberg, Leslie Ann; Jerrum, Mark
2
2019
Uniqueness for the 3-state antiferromagnetic Potts model on the tree. Zbl 1398.05086
Galanis, Andreas; Goldberg, Leslie Ann; Yang, Kuan
2
2018
Asymptotically optimal amplifiers for the Moran process. Zbl 1422.60124
Goldberg, Leslie Ann; Lapinskas, John; Lengler, Johannes; Meier, Florian; Panagiotou, Konstantinos; Pfister, Pascal
2
2019
Efficient algorithms for listing unlabeled graphs. Zbl 0770.68059
Goldberg, Leslie Ann
2
1992
On counting homomorphisms to directed acyclic graphs. Zbl 1223.68055
Dyer, Martin; Goldberg, Leslie Ann; Paterson, Mike
2
2006
An extension of path coupling and its application to the Glauber dynamics for graph colourings (extended abstract). Zbl 0981.05046
Dyer, Martin; Goldberg, Leslie Ann; Greenhill, Catherine; Jerrum, Mark; Mitzenmacher, Michael
2
2000
Efficient algorithms for listing combinatorial structures. Reprint of the 1993 hardback ed. Zbl 1205.01051
Goldberg, Leslie Ann
2
2009
The ‘Burnside process’ converges slowly. Zbl 1008.68085
Goldberg, Leslie Ann; Jerrum, Mark
2
2002
Counting and sampling \(H\)-colourings. Zbl 1028.68098
Dyer, Martin; Goldberg, Leslie A.; Jerrum, Mark
2
2002
An improved stability bound for binary exponential backoff. Zbl 0992.68006
Al-Ammal, H.; Goldberg, L. A.; MacKenzie, P.
2
2001
Approximately counting locally-optimal structures. Zbl 1440.68118
Goldberg, Leslie Ann; Gysel, Rob; Lapinskas, John
2
2015
Polynomial space polynomial delay algorithms for listing families of graphs. Zbl 1310.68108
Goldberg, Leslie Ann
2
1993
Log-supermodular functions, functional clones and counting CSPs. Zbl 1245.68100
Bulatov, Andrei A.; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
2
2012
A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid. Zbl 1272.05019
Goldberg, Leslie Ann; Jerrum, Mark
2
2013
The complexity of approximating the complex-valued Potts model. Zbl 07506814
Galanis, Andreas; Goldberg, Leslie Ann; Herrera-Poyatos, Andrés
1
2022
The complexity of approximating the matching polynomial in the complex plane. Zbl 07495903
Bezáková, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Štefankovič, Daniel
3
2021
Fast algorithms for general spin systems on bipartite expanders. Zbl 07499573
Galanis, Andreas; Goldberg, Leslie Ann; Stewart, James
1
2021
Inapproximability of the independent set polynomial in the complex plane. Zbl 1476.68193
Bezáková, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Štefankovič, Daniel
3
2020
Holant clones and the approximability of conservative holant problems. Zbl 1484.68144
Backens, Miriam; Goldberg, Leslie Ann
3
2020
Sampling in uniqueness from the Potts and random-cluster models on random regular graphs. Zbl 1436.82004
Blanca, Antonio; Galanis, Andreas; Goldberg, Leslie Ann; Štefankovič, Daniel; Vigoda, Eric; Yang, Kuan
3
2020
Phase transitions of the Moran process and algorithmic consequences. Zbl 1444.92072
Goldberg, Leslie Ann; Lapinskas, John; Richerby, David
2
2020
Random walks on small world networks. Zbl 1484.05195
Dyer, Martin E.; Galanis, Andreas; Goldberg, Leslie Ann; Jerrum, Mark; Vigoda, Eric
1
2020
Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin. Zbl 1435.68221
Backens, Miriam; Bulatov, Andrei; Goldberg, Leslie Ann; McQuillan, Colin; Živný, Stanislav
1
2020
Approximation via correlation decay when strong spatial mixing fails. Zbl 1422.68270
Bezáková, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Guo, Heng; Štefankovič, Daniel
3
2019
Approximating pairwise correlations in the Ising model. Zbl 07143739
Goldberg, Leslie Ann; Jerrum, Mark
2
2019
Asymptotically optimal amplifiers for the Moran process. Zbl 1422.60124
Goldberg, Leslie Ann; Lapinskas, John; Lengler, Johannes; Meier, Florian; Panagiotou, Konstantinos; Pfister, Pascal
2
2019
A fixed-parameter perspective on #BIS. Zbl 1430.68185
Curticapean, Radu; Dell, Holger; Fomin, Fedor; Goldberg, Leslie Ann; Lapinskas, John
1
2019
The complexity of approximately counting retractions. Zbl 1432.68179
Focke, Jacob; Goldberg, Leslie Ann; Živný, Stanislav
1
2019
Inapproximability of the independent set polynomial in the complex plane. Zbl 1427.68229
Bezáková, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Štefankovič, Daniel
5
2018
Uniqueness for the 3-state antiferromagnetic Potts model on the tree. Zbl 1398.05086
Galanis, Andreas; Goldberg, Leslie Ann; Yang, Kuan
2
2018
The complexity of approximating complex-valued Ising and Tutte partition functions. Zbl 1382.68090
Goldberg, Leslie Ann; Guo, Heng
7
2017
Amplifiers for the Moran process. Zbl 1426.68296
Galanis, Andreas; Göbel, Andreas; Goldberg, Leslie Ann; Lapinskas, John; Richerby, David
5
2017
A complexity trichotomy for approximately counting list \(H\)-colorings. Zbl 1427.68121
Galanis, Andreas; Goldberg, Leslie Ann; Jerrum, Mark
4
2017
Functional clones and expressibility of partition functions. Zbl 1418.08001
Bulatov, Andrei; Goldberg, Leslie Ann; Jerrum, Mark; Richerby, David; Živný, Stanislav
2
2017
Inapproximability of the independent set polynomial below the Shearer threshold. Zbl 1441.68180
Galanis, Andreas; Goldberg, Leslie Ann; Štefankovič, Daniel
2
2017
Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems. Zbl 1441.68155
Galanis, Andreas; Goldberg, Leslie Ann; Yang, Kuan
1
2017
\(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region. Zbl 1338.68086
Cai, Jin-Yi; Galanis, Andreas; Goldberg, Leslie Ann; Guo, Heng; Jerrum, Mark; Štefankovič, Daniel; Vigoda, Eric
14
2016
Approximately counting \(H\)-colorings is \(\#\)BIS-hard. Zbl 1342.68147
Galanis, Andreas; Goldberg, Leslie Ann; Jerrum, Mark
9
2016
Absorption time of the Moran process. Zbl 1344.05135
Díaz, Josep; Goldberg, Leslie Ann; Richerby, David; Serna, Maria
6
2016
Approximately counting locally-optimal structures. Zbl 1342.68163
Goldberg, Leslie Ann; Gysel, Rob; Lapinskas, John
5
2016
The complexity of approximately counting in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs. Zbl 1353.68128
Galanis, Andreas; Goldberg, Leslie Ann
5
2016
Approximation via correlation decay when strong spatial mixing fails. Zbl 1388.68300
Bezáková, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Guo, Heng; Štefankovič, Daniel
3
2016
Counting homomorphisms to square-free graphs, modulo 2. Zbl 1427.68241
Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David
3
2016
Amplifiers for the Moran process. Zbl 1388.68296
Galanis, Andreas; Göbel, Andreas; Goldberg, Leslie Ann; Lapinskas, John; Richerby, David
2
2016
The complexity of counting locally maximal satisfying assignments of Boolean CSPs. Zbl 1339.68117
Goldberg, Leslie Ann; Jerrum, Mark
1
2016
The complexity of approximating conservative counting CSPs. Zbl 1354.68114
Chen, Xi; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Lu, Pinyan; McQuillan, Colin; Richerby, David
7
2015
A complexity classification of spin systems with an external field. Zbl 1355.68120
Goldberg, Leslie Ann; Jerrum, Mark
6
2015
Approximating the partition function of planar two-state spin systems. Zbl 1401.05279
Goldberg, Leslie Ann; Jerrum, Mark; McQuillan, Colin
2
2015
Approximately counting locally-optimal structures. Zbl 1440.68118
Goldberg, Leslie Ann; Gysel, Rob; Lapinskas, John
2
2015
Approximating fixation probabilities in the generalized Moran process. Zbl 1303.92095
Díaz, Josep; Goldberg, Leslie Ann; Mertzios, George B.; Richerby, David; Serna, Maria; Spirakis, Paul G.
23
2014
Absorption time of the Moran process. Zbl 1359.92093
Díaz, Josep; Goldberg, Leslie Ann; Richerby, David; Serna, Maria
16
2014
The complexity of counting homomorphisms to cactus graphs modulo 2. Zbl 1347.68181
Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David
4
2014
The complexity of computing the sign of the Tutte polynomial. Zbl 1437.68068
Goldberg, Leslie Ann; Jerrum, Mark
4
2014
The complexity of approximately counting tree homomorphisms. Zbl 1321.68312
Goldberg, Leslie Ann; Jerrum, Mark
3
2014
Counting homomorphisms to cactus graphs modulo 2. Zbl 1359.05061
Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David
2
2014
Adaptive drift analysis. Zbl 1277.68289
Doerr, Benjamin; Goldberg, Leslie Ann
25
2013
On the fixation probability of superstars. Zbl 1371.92097
Díaz, Josep; Goldberg, Leslie Ann; Mertzios, George B.; Richerby, David; Serna, Maria; Spirakis, Paul G.
24
2013
The expressibility of functions on the Boolean domain, with applications to counting CSPs. Zbl 1281.68131
Bulatov, Andrei A.; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Mcquillan, Colin
15
2013
Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials. Zbl 1258.05020
Goldberg, Leslie Ann; Jerrum, Mark
4
2013
The complexity of approximating conservative counting CSPs. Zbl 1354.68115
Chen, Xi; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Lu, Pinyan; Mcquillan, Colin; Richerby, David
3
2013
A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid. Zbl 1272.05019
Goldberg, Leslie Ann; Jerrum, Mark
2
2013
Approximating the partition function of the ferromagnetic Potts model. Zbl 1281.68116
Goldberg, Leslie Ann; Jerrum, Mark
26
2012
The complexity of weighted and unweighted \(\#\)CSP. Zbl 1282.68110
Bulatov, Andrei; Dyer, Martin; Goldberg, Leslie Ann; Jalsenius, Markus; Jerrum, Mark; Richerby, David
11
2012
Inapproximability of the Tutte polynomial of a planar graph. Zbl 1282.68122
Goldberg, Leslie Ann; Jerrum, Mark
5
2012
A counterexample to rapid mixing of the Ge-Stefankovic process. Zbl 1246.60094
Goldberg, Leslie Ann; Jerrum, Mark
5
2012
The complexity of approximating bounded-degree Boolean \(\#\)CSP. Zbl 1282.68136
Dyer, Martin; Goldberg, Leslie Ann; Jalsenius, Markus; Richerby, David
5
2012
The complexity of computing the sign of the Tutte polynomial (and consequent #P-hardness of approximation). Zbl 1272.68155
Goldberg, Leslie Ann; Jerrum, Mark
4
2012
The complexity of approximately counting stable roommate assignments. Zbl 1244.68038
Chebolu, Prasad; Goldberg, Leslie Ann; Martin, Russell
3
2012
The complexity of approximately counting stable matchings. Zbl 1310.68103
Chebolu, Prasad; Goldberg, Leslie Ann; Martin, Russell
3
2012
Log-supermodular functions, functional clones and counting CSPs. Zbl 1245.68100
Bulatov, Andrei A.; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
2
2012
Approximating fixation probabilities in the generalized Moran process. Zbl 1423.92217
Díaz, Josep; Goldberg, Leslie Ann; Mertzios, George B.; Richerby, David; Serna, Maria; Spirakis, Paul G.
1
2012
A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid. Zbl 1333.68122
Goldberg, Leslie Ann; Jerrum, Mark
3
2011
Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 14th international workshop, APPROX 2011, and 15th international workshop, RANDOM 2011, Princeton, NJ, USA, August 17–19, 2011. Proceedings. Zbl 1219.68018
1
2011
A complexity dichotomy for partition functions with mixed signs. Zbl 1298.68099
Goldberg, Leslie Ann; Grohe, Martin; Jerrum, Mark; Thurley, Marc
29
2010
An approximation trichotomy for Boolean #CSP. Zbl 1201.68154
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
27
2010
Approximating the partition function of the ferromagnetic Potts model. Zbl 1288.68091
Goldberg, Leslie Ann; Jerrum, Mark
6
2010
The mixing time of Glauber dynamics for coloring regular trees. Zbl 1348.68172
Goldberg, Leslie Ann; Jerrum, Mark; Karpinski, Marek
6
2010
The complexity of approximating bounded-degree Boolean #CSP. Zbl 1230.68105
Dyer, Martin; Goldberg, Leslie Ann; Jalsenius, Markus; Richerby, David
6
2010
The complexity of approximately counting stable matchings. Zbl 1304.68069
Chebolu, Prasad; Goldberg, Leslie Ann; Martin, Russell
4
2010
A complexity dichotomy for hypergraph partition functions. Zbl 1217.68105
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
1
2010
The complexity of weighted Boolean #CSP. Zbl 1191.68351
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
38
2009
On the computational complexity of weighted voting games. Zbl 1185.91081
Elkind, Edith; Goldberg, Leslie Ann; Goldberg, Paul W.; Wooldridge, Michael
28
2009
The complexity of weighted Boolean #CSP with mixed signs. Zbl 1171.68013
Bulatov, Andrei; Dyer, Martin; Goldberg, Leslie Ann; Jalsenius, Markus; Richerby, David
14
2009
A tractable and expressive class of marginal contribution nets and its applications. Zbl 1175.91022
Elkind, Edith; Goldberg, Leslie Ann; Goldberg, Paul W.; Wooldridge, Michael
13
2009
Matrix norms and rapid mixing for spin systems. Zbl 1166.15015
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
6
2009
A complexity dichotomy for partition functions with mixed signs. Zbl 1236.68092
Goldberg, Leslie Ann; Grohe, Martin; Jerrum, Mark; Thurley, Marc
5
2009
Efficient algorithms for listing combinatorial structures. Reprint of the 1993 hardback ed. Zbl 1205.01051
Goldberg, Leslie Ann
2
2009
Inapproximability of the Tutte polynomial. Zbl 1153.68039
Goldberg, Leslie Ann; Jerrum, Mark
30
2008
Dobrushin conditions and systematic scan. Zbl 1168.60035
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
7
2008
On counting homomorphisms to directed acyclic graphs. Zbl 1312.68098
Dyer, Martin E.; Goldberg, Leslie Ann; Paterson, Mike
26
2007
The complexity of ferromagnetic Ising with local fields. Zbl 1170.82001
Goldberg, Leslie Ann; Jerrum, Mark
17
2007
Distributed selfish load balancing. Zbl 1141.68018
Berenbrink, Petra; Friedetzky, Tom; Goldberg, Leslie Ann; Goldberg, Paul W.; Hu, Zengjian; Martin, Russell
7
2007
Inapproximability of the Tutte polynomial. Zbl 1232.68073
Goldberg, Leslie Ann; Jerrum, Mark
5
2007
Markov chain comparison. Zbl 1189.60135
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Martin, Russell
24
2006
Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows. Zbl 1117.62062
Cryan, Mary; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Martin, Russell
18
2006
Systematic scan for sampling colorings. Zbl 1095.60024
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
12
2006
Utilitarian resource assignment. Zbl 1124.91042
Berenbrink, Petra; Goldberg, Leslie Ann; Goldberg, Paul W.; Martin, Russell
7
2006
Improved mixing bounds for the anti-ferromagnetic Potts model on \(\mathbb Z^2\). Zbl 1122.82007
Goldberg, Leslie Ann; Jalsenius, Markus; Martin, Russell; Paterson, Mike
7
2006
Distributed selfish load balancing. Zbl 1192.68094
Berenbrink, Petra; Friedetzky, Tom; Goldberg, Leslie Ann; Goldberg, Paul; Hu, Zengjian; Martin, Russell
7
2006
Dobrushin conditions and systematic scan. Zbl 1155.60331
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
4
2006
On counting homomorphisms to directed acyclic graphs. Zbl 1223.68055
Dyer, Martin; Goldberg, Leslie Ann; Paterson, Mike
2
2006
Strong spatial mixing with fewer colors for lattice graphs. Zbl 1091.60013
Goldberg, Leslie Ann; Martin, Russell; Paterson, Mike
17
2005
The relative complexity of approximate counting problems. Zbl 1138.68424
Dyer, Martin; Goldberg, Leslie Ann; Greenhill, Catherine; Jerrum, Mark
57
2004
Random sampling of 3-colorings in \({\mathbb Z}^{2}\). Zbl 1044.60100
Goldberg, Leslie Ann; Martin, Russell; Paterson, Mike
13
2004
A bound on the capacity of backoff and acknowledgment-based protocols. Zbl 1078.68552
Goldberg, Leslie Ann; Jerrum, Mark; Kannan, Sampath; Paterson, Mike
12
2004
The complexity of choosing an \(H\)-coloring (nearly) uniformly at random. Zbl 1105.68114
Goldberg, Leslie Ann; Kelk, Steven; Paterson, Mike
8
2004
Counting and sampling \(H\)-colourings. Zbl 1082.68079
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
6
2004
The computational complexity of two-state spin systems. Zbl 1030.82001
Goldberg, Leslie Ann; Jerrum, Mark; Paterson, Mike
23
2003
The natural work-stealing algorithm is stable. Zbl 1027.60082
Berenbrink, Petra; Friedetzky, Tom; Goldberg, Leslie Ann
4
2003
Convergence of the iterated prisoner’s dilemma game. Zbl 1006.60009
Dyer, Martin; Goldberg, Leslie Ann; Greenhill, Catherine; Istrate, Gabriel; Jerrum, Mark
6
2002
The complexity of choosing an \(H\)-colouring (nearly) uniformly at random. Zbl 1192.68898
Goldberg, Leslie Ann; Kelk, Steven; Paterson, Mike
3
2002
The ‘Burnside process’ converges slowly. Zbl 1008.68085
Goldberg, Leslie Ann; Jerrum, Mark
2
2002
Counting and sampling \(H\)-colourings. Zbl 1028.68098
Dyer, Martin; Goldberg, Leslie A.; Jerrum, Mark
2
2002
Evolutionary trees can be learned in polynomial time in the two-state general Markov model. Zbl 1052.68061
Cryan, Mary; Goldberg, Leslie Ann; Goldberg, Paul W.
10
2001
...and 22 more Documents
all top 5

Cited by 694 Authors

54 Goldberg, Leslie Ann
23 Jerrum, Mark R.
22 Cai, Jin-Yi
19 Galanis, Andreas
18 Dyer, Martin E.
14 Lu, Pinyan
13 Štefankovič, Daniel
12 Doerr, Benjamin
12 Guo, Heng
12 Vigoda, Eric
9 Bulatov, Andrei A.
9 Richerby, David M.
8 Sinclair, Alistair
7 Greco, Gianluigi
7 Jalsenius, Markus
7 Kötzing, Timo
7 Kowalski, Dariusz R.
7 Lapinskas, John
7 Witt, Carsten
6 Bachrach, Yoram
6 Bezáková, Ivona
6 Blanca, Antonio
6 Chlebus, Bogdan Stanislaw
6 Lengler, Johannes
6 Xia, Mingji
5 Curticapean, Radu
5 Dell, Holger
5 Fu, Zhiguo
5 Göbel, Andreas-Nikolas
5 Kowalczyk, Michael
5 Randall, Dana J.
5 Regts, Guus
5 Srivastava, Piyush
5 Wooldridge, Michael J.
5 Yin, Yitong
5 Živný, Stanislav
4 Anantharamu, Lakshmi
4 Berenbrink, Petra
4 Bordewich, Magnus
4 Diaconis, Persi Warren
4 Fischer, Simon-Raphael
4 Kochol, Martin
4 Lagodzinski, J. A. Gregor
4 Martin, Russell A.
4 Mossel, Elchanan
4 Nakano, Shin-ichi
4 Roth, Marc
4 Spirakis, Paul G.
4 Williams, Tyson
4 Yamakami, Tomoyuki
4 Yang, Kuan
3 Barvinok, Alexander I.
3 Chen, Xi
3 Elkind, Edith
3 Fomin, Fedor V.
3 Fotakis, Dimitris A.
3 Frieze, Alan Michael
3 Gamarnik, David
3 Goldberg, Paul W.
3 Greenhill, Catherine S.
3 Hayes, Thomas P.
3 Herrera-Poyatos, Andrés
3 Jansen, Klaus
3 Lin, Jiabao
3 Mastrolilli, Monaldo
3 Mcquillan, Colin
3 Meeks, Kitty
3 Moffatt, Iain
3 Moran, Shlomo
3 Müller, Haiko
3 Pagourtzis, Aris T.
3 Patel, Viresh
3 Roch, Sébastien
3 Rokicki, Mariusz A.
3 Rosenschein, Jeffrey S.
3 Scarcello, Francesco
3 Scheideler, Christian
3 Serna Iglesias, Maria José
3 Snir, Sagi
3 Vishnoi, Nisheeth K.
3 Yang, Linji
3 Young, Maxwell
3 Zick, Yair
2 Ackermann, Heiner
2 Ågotnes, Thomas
2 Backens, Miriam
2 Bakali, Eleni
2 Barish, Robert D.
2 Bhatnagar, Nayantara
2 Bi, Dianjie
2 Bläser, Markus
2 Bonamy, Marthe
2 Bousquet, Nicolas
2 Briceño, Raimundo
2 Buys, Pjotr
2 Cauwet, Marie-Liesse
2 Chalki, Aggeliki
2 Chalkiadakis, Georgios
2 Chebolu, Prasad
2 Chen, Zongchen
...and 594 more Authors
all top 5

Cited in 113 Serials

40 Theoretical Computer Science
25 SIAM Journal on Computing
25 Algorithmica
23 Journal of Computer and System Sciences
18 Random Structures & Algorithms
15 Information and Computation
14 Distributed Computing
12 Artificial Intelligence
12 SIAM Journal on Discrete Mathematics
12 Combinatorics, Probability and Computing
12 Theory of Computing Systems
10 Discrete Applied Mathematics
10 Computational Complexity
8 The Annals of Applied Probability
6 Communications in Mathematical Physics
6 Operations Research Letters
5 Journal of Statistical Physics
5 Mathematical Social Sciences
5 International Journal of Foundations of Computer Science
5 Journal of Scheduling
4 Probability Theory and Related Fields
4 Journal of Combinatorial Optimization
4 Journal of Discrete Algorithms
3 Information Processing Letters
3 Advances in Applied Mathematics
3 Machine Learning
3 European Journal of Operational Research
3 Stochastic Processes and their Applications
3 Annales de l’Institut Henri Poincaré. Probabilités et Statistiques
3 Mathematical Logic Quarterly (MLQ)
3 Journal of Theoretical Biology
3 ACM Transactions on Computation Theory
2 Discrete Mathematics
2 Statistics & Probability Letters
2 Journal of Symbolic Computation
2 Statistical Science
2 Journal of Theoretical Probability
2 Annals of Operations Research
2 Linear Algebra and its Applications
2 Mathematical Programming. Series A. Series B
2 Annals of Mathematics and Artificial Intelligence
2 Bernoulli
2 Constraints
2 Annals of Combinatorics
2 Journal of Applied Statistics
2 LMS Journal of Computation and Mathematics
2 Journal of Machine Learning Research (JMLR)
2 Electronic Journal of Statistics
1 Computer Physics Communications
1 Journal of Mathematical Physics
1 Physica A
1 Advances in Mathematics
1 Algebra Universalis
1 The Annals of Probability
1 Applied Mathematics and Computation
1 Dissertationes Mathematicae
1 Information Sciences
1 Journal of Applied Probability
1 Journal of Combinatorial Theory. Series A
1 Journal of Combinatorial Theory. Series B
1 Journal of Functional Analysis
1 Journal of Mathematical Economics
1 Michigan Mathematical Journal
1 Operations Research
1 Quaestiones Mathematicae
1 Synthese
1 Transactions of the American Mathematical Society
1 European Journal of Combinatorics
1 Ergodic Theory and Dynamical Systems
1 Combinatorica
1 Physica D
1 Social Choice and Welfare
1 Graphs and Combinatorics
1 Discrete & Computational Geometry
1 Computers & Operations Research
1 International Journal of Approximate Reasoning
1 Mathematical and Computer Modelling
1 Queueing Systems
1 Journal of Parallel and Distributed Computing
1 AI Communications
1 JETAI. Journal of Experimental & Theoretical Artificial Intelligence
1 Neural Computation
1 Computational Geometry
1 MSCS. Mathematical Structures in Computer Science
1 Games and Economic Behavior
1 Computational Statistics
1 Applied Mathematical Modelling
1 Proceedings of the National Academy of Sciences of the United States of America
1 Journal of Knot Theory and its Ramifications
1 SIAM Journal on Optimization
1 Journal of Algebraic Combinatorics
1 The Electronic Journal of Combinatorics
1 The Journal of Artificial Intelligence Research (JAIR)
1 Journal of Difference Equations and Applications
1 Discrete and Continuous Dynamical Systems
1 Mathematical Problems in Engineering
1 Multibody System Dynamics
1 New Journal of Physics
1 RAIRO. Operations Research
1 Advances in Difference Equations
...and 13 more Serials
all top 5

Cited in 38 Fields

308 Computer science (68-XX)
155 Combinatorics (05-XX)
77 Probability theory and stochastic processes (60-XX)
63 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
57 Operations research, mathematical programming (90-XX)
55 Statistical mechanics, structure of matter (82-XX)
28 Statistics (62-XX)
26 Biology and other natural sciences (92-XX)
15 Numerical analysis (65-XX)
12 Mathematical logic and foundations (03-XX)
9 Quantum theory (81-XX)
9 Information and communication theory, circuits (94-XX)
8 Dynamical systems and ergodic theory (37-XX)
6 Convex and discrete geometry (52-XX)
5 Order, lattices, ordered algebraic structures (06-XX)
5 Number theory (11-XX)
5 Linear and multilinear algebra; matrix theory (15-XX)
4 Manifolds and cell complexes (57-XX)
3 Ordinary differential equations (34-XX)
2 General algebraic systems (08-XX)
2 Commutative algebra (13-XX)
2 Group theory and generalizations (20-XX)
2 Differential geometry (53-XX)
1 General and overarching topics; collections (00-XX)
1 History and biography (01-XX)
1 Field theory and polynomials (12-XX)
1 Category theory; homological algebra (18-XX)
1 Measure and integration (28-XX)
1 Functions of a complex variable (30-XX)
1 Special functions (33-XX)
1 Approximations and expansions (41-XX)
1 Harmonic analysis on Euclidean spaces (42-XX)
1 Integral equations (45-XX)
1 Operator theory (47-XX)
1 Mechanics of particles and systems (70-XX)
1 Mechanics of deformable solids (74-XX)
1 Fluid mechanics (76-XX)
1 Systems theory; control (93-XX)

Citations by Year

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.