×

zbMATH — the first resource for mathematics

Goldberg, Leslie Ann

Compute Distance To:
Author ID: goldberg.leslie-ann Recent zbMATH articles by "Goldberg, Leslie Ann"
Published as: Goldberg, Leslie Ann; Goldberg, L. A.; Goldberg, Leslie Anne; Goldberg, Leslie A.
External Links: MGP · Wikidata · ORCID · dblp
Documents Indexed: 141 Publications since 1992, including 5 Books

Publications by Year

Citations contained in zbMATH Open

102 Publications have been cited 726 times in 396 Documents Cited by Year
The relative complexity of approximate counting problems. Zbl 1138.68424
Dyer, Martin; Goldberg, Leslie Ann; Greenhill, Catherine; Jerrum, Mark
44
2004
The complexity of weighted Boolean #CSP. Zbl 1191.68351
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
33
2009
Inapproximability of the Tutte polynomial. Zbl 1153.68039
Goldberg, Leslie Ann; Jerrum, Mark
25
2008
On the computational complexity of weighted voting games. Zbl 1185.91081
Elkind, Edith; Goldberg, Leslie Ann; Goldberg, Paul W.; Wooldridge, Michael
23
2009
A complexity dichotomy for partition functions with mixed signs. Zbl 1298.68099
Goldberg, Leslie Ann; Grohe, Martin; Jerrum, Mark; Thurley, Marc
22
2010
Markov chain comparison. Zbl 1189.60135
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Martin, Russell
22
2006
On counting homomorphisms to directed acyclic graphs. Zbl 1312.68098
Dyer, Martin E.; Goldberg, Leslie Ann; Paterson, Mike
22
2007
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.
22
2013
An approximation trichotomy for Boolean #CSP. Zbl 1201.68154
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
21
2010
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.
21
2014
The computational complexity of two-state spin systems. Zbl 1030.82001
Goldberg, Leslie Ann; Jerrum, Mark; Paterson, Mike
20
2003
Adaptive drift analysis. Zbl 1277.68289
Doerr, Benjamin; Goldberg, Leslie Ann
19
2013
Approximating the partition function of the ferromagnetic Potts model. Zbl 1281.68116
Goldberg, Leslie Ann; Jerrum, Mark
17
2012
Strong spatial mixing with fewer colors for lattice graphs. Zbl 1091.60013
Goldberg, Leslie Ann; Martin, Russell; Paterson, Mike
16
2005
Absorption time of the Moran process. Zbl 1359.92093
Díaz, Josep; Goldberg, Leslie Ann; Richerby, David; Serna, Maria
16
2014
Efficient algorithms for listing combinatorial structures. Zbl 0821.68059
Goldberg, Leslie Ann
15
1993
The complexity of ferromagnetic Ising with local fields. Zbl 1170.82001
Goldberg, Leslie Ann; Jerrum, Mark
15
2007
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
15
2006
Contention resolution with constant expected delay. Zbl 1094.68518
Goldberg, Leslie Ann; MacKenzie, Philip D.; Paterson, Mike; Srinivasan, Aravind
13
2000
The complexity of weighted Boolean #CSP with mixed signs. Zbl 1171.68013
Bulatov, Andrei; Dyer, Martin; Goldberg, Leslie Ann; Jalsenius, Markus; Richerby, David
12
2009
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
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
11
2009
A bound on the capacity of backoff and acknowledgment-based protocols. Zbl 1078.68552
Goldberg, Leslie Ann; Jerrum, Mark; Kannan, Sampath; Paterson, Mike
11
2004
Random sampling of 3-colorings in \({\mathbb Z}^{2}\). Zbl 1044.60100
Goldberg, Leslie Ann; Martin, Russell; Paterson, Mike
11
2004
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
10
2013
\(\#\)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
10
2016
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
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
The complexity of approximating bounded-degree Boolean #CSP. Zbl 1230.68105
Dyer, Martin; Goldberg, Leslie Ann; Jalsenius, Markus; Richerby, David
6
2010
Approximating the partition function of the ferromagnetic Potts model. Zbl 1288.68091
Goldberg, Leslie Ann; Jerrum, Mark
6
2010
The complexity of choosing an \(H\)-coloring (nearly) uniformly at random. Zbl 1105.68114
Goldberg, Leslie Ann; Kelk, Steven; Paterson, Mike
6
2004
Distributed selfish load balancing. Zbl 1141.68018
Berenbrink, Petra; Friedetzky, Tom; Goldberg, Leslie Ann; Goldberg, Paul W.; Hu, Zengjian; Martin, Russell
6
2007
Dobrushin conditions and systematic scan. Zbl 1168.60035
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
6
2008
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
Counting and sampling \(H\)-colourings. Zbl 1082.68079
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
6
2004
Better approximation guarantees for job-shop scheduling. Zbl 0967.68084
Goldberg, Leslie Ann; Paterson, Mike; Srinivasan, Aravind; Sweedyk, Elizabeth
6
2001
A complexity dichotomy for partition functions with mixed signs. Zbl 1236.68092
Goldberg, Leslie Ann; Grohe, Martin; Jerrum, Mark; Thurley, Marc
5
2009
Distributed selfish load balancing. Zbl 1192.68094
Berenbrink, Petra; Friedetzky, Tom; Goldberg, Leslie Ann; Goldberg, Paul; Hu, Zengjian; Martin, Russell
5
2006
Better approximation guarantees for job-shop scheduling. Zbl 1321.68503
Goldberg, Leslie Ann; Paterson, Mike; Srinivasan, Aravind; Sweedyk, Elizabeth
5
1997
Inapproximability of the Tutte polynomial. Zbl 1232.68073
Goldberg, Leslie Ann; Jerrum, Mark
5
2007
Approximately counting locally-optimal structures. Zbl 1342.68163
Goldberg, Leslie Ann; Gysel, Rob; Lapinskas, John
5
2016
Construction computer virus phylogenies. Zbl 0891.68045
Goldberg, Leslie Ann; Goldberg, Paul W.; Phillips, Cynthia A.; Sorkin, Gregory B.
5
1998
An optical simulation of shared memory. Zbl 0928.68134
Goldberg, Leslie Ann; Matias, Yossi; Rao, Satish
5
1999
A counterexample to rapid mixing of the Ge-Stefankovic process. Zbl 1246.60094
Goldberg, Leslie Ann; Jerrum, Mark
4
2012
The complexity of approximately counting stable matchings. Zbl 1304.68069
Chebolu, Prasad; Goldberg, Leslie Ann; Martin, Russell
4
2010
The mixing time of Glauber dynamics for coloring regular trees. Zbl 1348.68172
Goldberg, Leslie Ann; Jerrum, Mark; Karpinski, Marek
4
2010
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
4
2015
Doubly logarithmic communication algorithms for optical-communication parallel computers. Zbl 0885.68079
Goldberg, Leslie Ann; Jerrum, Mark; Leighton, Tom; Rao, Satish
4
1997
Convergence of the iterated prisoner’s dilemma game. Zbl 1006.60009
Dyer, Martin; Goldberg, Leslie Ann; Greenhill, Catherine; Istrate, Gabriel; Jerrum, Mark
4
2002
Matrix norms and rapid mixing for spin systems. Zbl 1166.15015
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
4
2009
The natural work-stealing algorithm is stable. Zbl 1027.60082
Berenbrink, Petra; Friedetzky, Tom; Goldberg, Leslie Ann
4
2003
Dobrushin conditions and systematic scan. Zbl 1155.60331
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
4
2006
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 in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs. Zbl 1353.68128
Galanis, Andreas; Goldberg, Leslie Ann
4
2016
A complexity classification of spin systems with an external field. Zbl 1355.68120
Goldberg, Leslie Ann; Jerrum, Mark
4
2015
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
The complexity of choosing an \(H\)-colouring (nearly) uniformly at random. Zbl 1192.68898
Goldberg, Leslie Ann; Kelk, Steven; Paterson, Mike
3
2002
Inapproximability of the Tutte polynomial of a planar graph. Zbl 1282.68122
Goldberg, Leslie Ann; Jerrum, Mark
3
2012
Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials. Zbl 1258.05020
Goldberg, Leslie Ann; Jerrum, Mark
3
2013
Counting unlabelled subtrees of a tree is \(\# P\)-complete. Zbl 0951.68047
Goldberg, Leslie Ann; Jerrum, Mark
3
2000
Analysis of practical backoff protocols for contention resolution with multiple servers. Zbl 0938.68012
Goldberg, Leslie Ann; MacKenzie, Philip D.
3
1999
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
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
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 1333.68122
Goldberg, Leslie Ann; Jerrum, Mark
2
2011
The complexity of approximating bounded-degree Boolean \(\#\)CSP. Zbl 1282.68136
Dyer, Martin; Goldberg, Leslie Ann; Jalsenius, Markus; Richerby, David
2
2012
Efficient algorithms for listing unlabeled graphs. Zbl 0770.68059
Goldberg, Leslie Ann
2
1992
Approximately counting locally-optimal structures. Zbl 1440.68118
Goldberg, Leslie Ann; Gysel, Rob; Lapinskas, John
2
2015
On counting homomorphisms to directed acyclic graphs. Zbl 1223.68055
Dyer, Martin; Goldberg, Leslie Ann; Paterson, Mike
2
2006
Approximating the partition function of planar two-state spin systems. Zbl 1401.05279
Goldberg, Leslie Ann; Jerrum, Mark; McQuillan, Colin
2
2015
Approximately counting \(H\)-colorings is \(\#\)BIS-hard. Zbl 1342.68147
Galanis, Andreas; Goldberg, Leslie Ann; Jerrum, Mark
2
2016
Absorption time of the Moran process. Zbl 1344.05135
Díaz, Josep; Goldberg, Leslie Ann; Richerby, David; Serna, Maria
2
2016
Polynomial space polynomial delay algorithms for listing families of graphs. Zbl 1310.68108
Goldberg, Leslie Ann
2
1993
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
Counting and sampling \(H\)-colourings. Zbl 1028.68098
Dyer, Martin; Goldberg, Leslie A.; Jerrum, Mark
2
2002
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
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
2
2013
Counting homomorphisms to cactus graphs modulo 2. Zbl 1359.05061
Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David
2
2014
The complexity of approximating complex-valued Ising and Tutte partition functions. Zbl 1382.68090
Goldberg, Leslie Ann; Guo, Heng
2
2017
Amplifiers for the Moran process. Zbl 1388.68296
Galanis, Andreas; Göbel, Andreas; Goldberg, Leslie Ann; Lapinskas, John; Richerby, David
2
2016
Amplifiers for the Moran process. Zbl 1426.68296
Galanis, Andreas; Göbel, Andreas; Goldberg, Leslie Ann; Lapinskas, John; Richerby, David
2
2017
Approximation via correlation decay when strong spatial mixing fails. Zbl 1422.68270
Bezáková, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Guo, Heng; Štefankovič, Daniel
2
2019
Efficient algorithms for listing combinatorial structures. Reprint of the 1993 hardback ed. Zbl 1205.01051
Goldberg, Leslie Ann
1
2009
A complexity dichotomy for hypergraph partition functions. Zbl 1217.68105
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
1
2010
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
1
2020
Automating Pólya theory: The computational complexity of the cycle index polynomial. Zbl 0785.20004
Goldberg, Leslie Ann
1
1993
Listing graphs that satisfy first-order sentences. Zbl 0921.03041
Goldberg, Leslie Ann
1
1994
The complexity of approximately counting tree homomorphisms. Zbl 1321.68312
Goldberg, Leslie Ann; Jerrum, Mark
1
2014
Inapproximability of the independent set polynomial below the Shearer threshold. Zbl 1441.68180
Galanis, Andreas; Goldberg, Leslie Ann; Štefankovič, Daniel
1
2017
The complexity of counting homomorphisms to cactus graphs modulo 2. Zbl 1347.68181
Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David
1
2014
Inapproximability of the independent set polynomial in the complex plane. Zbl 1427.68229
Bezáková, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Štefankovič, Daniel
1
2018
Randomly sampling molecules. Zbl 0958.68138
Goldberg, Leslie Ann; Jerrum, Mark
1
2000
An \(\omega(\sqrt{\log\log n})\) lower bound for routing in optical networks. Zbl 0907.68098
Goldberg, Leslie Ann; Jerrum, Mark; MacKenzie, Philip D.
1
1998
Computation in permutation groups: Counting and randomly sampling orbits. Zbl 0978.68067
Goldberg, Leslie Ann
1
2001
An improved stability bound for binary exponential backoff. Zbl 0992.68006
Al-Ammal, H.; Goldberg, L. A.; MacKenzie, P.
1
2001
The ‘Burnside process’ converges slowly. Zbl 1008.68085
Goldberg, Leslie Ann; Jerrum, Mark
1
2002
Functional clones and expressibility of partition functions. Zbl 1418.08001
Bulatov, Andrei; Goldberg, Leslie Ann; Jerrum, Mark; Richerby, David; Živný, Stanislav
1
2017
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
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
2
2019
Inapproximability of the independent set polynomial in the complex plane. Zbl 1427.68229
Bezáková, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Štefankovič, Daniel
1
2018
Uniqueness for the 3-state antiferromagnetic Potts model on the tree. Zbl 1398.05086
Galanis, Andreas; Goldberg, Leslie Ann; Yang, Kuan
1
2018
The complexity of approximating complex-valued Ising and Tutte partition functions. Zbl 1382.68090
Goldberg, Leslie Ann; Guo, Heng
2
2017
Amplifiers for the Moran process. Zbl 1426.68296
Galanis, Andreas; Göbel, Andreas; Goldberg, Leslie Ann; Lapinskas, John; Richerby, David
2
2017
Inapproximability of the independent set polynomial below the Shearer threshold. Zbl 1441.68180
Galanis, Andreas; Goldberg, Leslie Ann; Štefankovič, Daniel
1
2017
Functional clones and expressibility of partition functions. Zbl 1418.08001
Bulatov, Andrei; Goldberg, Leslie Ann; Jerrum, Mark; Richerby, David; Živný, Stanislav
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
10
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
4
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
Approximately counting \(H\)-colorings is \(\#\)BIS-hard. Zbl 1342.68147
Galanis, Andreas; Goldberg, Leslie Ann; Jerrum, Mark
2
2016
Absorption time of the Moran process. Zbl 1344.05135
Díaz, Josep; Goldberg, Leslie Ann; Richerby, David; Serna, Maria
2
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 approximating conservative counting CSPs. Zbl 1354.68114
Chen, Xi; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Lu, Pinyan; McQuillan, Colin; Richerby, David
4
2015
A complexity classification of spin systems with an external field. Zbl 1355.68120
Goldberg, Leslie Ann; Jerrum, Mark
4
2015
Approximately counting locally-optimal structures. Zbl 1440.68118
Goldberg, Leslie Ann; Gysel, Rob; Lapinskas, John
2
2015
Approximating the partition function of planar two-state spin systems. Zbl 1401.05279
Goldberg, Leslie Ann; Jerrum, Mark; McQuillan, Colin
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.
21
2014
Absorption time of the Moran process. Zbl 1359.92093
Díaz, Josep; Goldberg, Leslie Ann; Richerby, David; Serna, Maria
16
2014
Counting homomorphisms to cactus graphs modulo 2. Zbl 1359.05061
Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David
2
2014
The complexity of approximately counting tree homomorphisms. Zbl 1321.68312
Goldberg, Leslie Ann; Jerrum, Mark
1
2014
The complexity of counting homomorphisms to cactus graphs modulo 2. Zbl 1347.68181
Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David
1
2014
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.
22
2013
Adaptive drift analysis. Zbl 1277.68289
Doerr, Benjamin; Goldberg, Leslie Ann
19
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
10
2013
Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials. Zbl 1258.05020
Goldberg, Leslie Ann; Jerrum, Mark
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
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
2
2013
Approximating the partition function of the ferromagnetic Potts model. Zbl 1281.68116
Goldberg, Leslie Ann; Jerrum, Mark
17
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
A counterexample to rapid mixing of the Ge-Stefankovic process. Zbl 1246.60094
Goldberg, Leslie Ann; Jerrum, Mark
4
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
Inapproximability of the Tutte polynomial of a planar graph. Zbl 1282.68122
Goldberg, Leslie Ann; Jerrum, Mark
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
The complexity of approximating bounded-degree Boolean \(\#\)CSP. Zbl 1282.68136
Dyer, Martin; Goldberg, Leslie Ann; Jalsenius, Markus; Richerby, David
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
2
2011
A complexity dichotomy for partition functions with mixed signs. Zbl 1298.68099
Goldberg, Leslie Ann; Grohe, Martin; Jerrum, Mark; Thurley, Marc
22
2010
An approximation trichotomy for Boolean #CSP. Zbl 1201.68154
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
21
2010
The complexity of approximating bounded-degree Boolean #CSP. Zbl 1230.68105
Dyer, Martin; Goldberg, Leslie Ann; Jalsenius, Markus; Richerby, David
6
2010
Approximating the partition function of the ferromagnetic Potts model. Zbl 1288.68091
Goldberg, Leslie Ann; Jerrum, Mark
6
2010
The complexity of approximately counting stable matchings. Zbl 1304.68069
Chebolu, Prasad; Goldberg, Leslie Ann; Martin, Russell
4
2010
The mixing time of Glauber dynamics for coloring regular trees. Zbl 1348.68172
Goldberg, Leslie Ann; Jerrum, Mark; Karpinski, Marek
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
33
2009
On the computational complexity of weighted voting games. Zbl 1185.91081
Elkind, Edith; Goldberg, Leslie Ann; Goldberg, Paul W.; Wooldridge, Michael
23
2009
The complexity of weighted Boolean #CSP with mixed signs. Zbl 1171.68013
Bulatov, Andrei; Dyer, Martin; Goldberg, Leslie Ann; Jalsenius, Markus; Richerby, David
12
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
11
2009
A complexity dichotomy for partition functions with mixed signs. Zbl 1236.68092
Goldberg, Leslie Ann; Grohe, Martin; Jerrum, Mark; Thurley, Marc
5
2009
Matrix norms and rapid mixing for spin systems. Zbl 1166.15015
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
4
2009
Efficient algorithms for listing combinatorial structures. Reprint of the 1993 hardback ed. Zbl 1205.01051
Goldberg, Leslie Ann
1
2009
Inapproximability of the Tutte polynomial. Zbl 1153.68039
Goldberg, Leslie Ann; Jerrum, Mark
25
2008
Dobrushin conditions and systematic scan. Zbl 1168.60035
Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark
6
2008
On counting homomorphisms to directed acyclic graphs. Zbl 1312.68098
Dyer, Martin E.; Goldberg, Leslie Ann; Paterson, Mike
22
2007
The complexity of ferromagnetic Ising with local fields. Zbl 1170.82001
Goldberg, Leslie Ann; Jerrum, Mark
15
2007
Distributed selfish load balancing. Zbl 1141.68018
Berenbrink, Petra; Friedetzky, Tom; Goldberg, Leslie Ann; Goldberg, Paul W.; Hu, Zengjian; Martin, Russell
6
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
22
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
15
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
5
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
16
2005
The relative complexity of approximate counting problems. Zbl 1138.68424
Dyer, Martin; Goldberg, Leslie Ann; Greenhill, Catherine; Jerrum, Mark
44
2004
A bound on the capacity of backoff and acknowledgment-based protocols. Zbl 1078.68552
Goldberg, Leslie Ann; Jerrum, Mark; Kannan, Sampath; Paterson, Mike
11
2004
Random sampling of 3-colorings in \({\mathbb Z}^{2}\). Zbl 1044.60100
Goldberg, Leslie Ann; Martin, Russell; Paterson, Mike
11
2004
The complexity of choosing an \(H\)-coloring (nearly) uniformly at random. Zbl 1105.68114
Goldberg, Leslie Ann; Kelk, Steven; Paterson, Mike
6
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
20
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
4
2002
The complexity of choosing an \(H\)-colouring (nearly) uniformly at random. Zbl 1192.68898
Goldberg, Leslie Ann; Kelk, Steven; Paterson, Mike
3
2002
Counting and sampling \(H\)-colourings. Zbl 1028.68098
Dyer, Martin; Goldberg, Leslie A.; Jerrum, Mark
2
2002
The ‘Burnside process’ converges slowly. Zbl 1008.68085
Goldberg, Leslie Ann; Jerrum, Mark
1
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
Better approximation guarantees for job-shop scheduling. Zbl 0967.68084
Goldberg, Leslie Ann; Paterson, Mike; Srinivasan, Aravind; Sweedyk, Elizabeth
6
2001
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
Computation in permutation groups: Counting and randomly sampling orbits. Zbl 0978.68067
Goldberg, Leslie Ann
1
2001
An improved stability bound for binary exponential backoff. Zbl 0992.68006
Al-Ammal, H.; Goldberg, L. A.; MacKenzie, P.
1
2001
Contention resolution with constant expected delay. Zbl 1094.68518
Goldberg, Leslie Ann; MacKenzie, Philip D.; Paterson, Mike; Srinivasan, Aravind
13
2000
Counting unlabelled subtrees of a tree is \(\# P\)-complete. Zbl 0951.68047
Goldberg, Leslie Ann; Jerrum, Mark
3
2000
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
Randomly sampling molecules. Zbl 0958.68138
Goldberg, Leslie Ann; Jerrum, Mark
1
2000
An optical simulation of shared memory. Zbl 0928.68134
Goldberg, Leslie Ann; Matias, Yossi; Rao, Satish
5
1999
Analysis of practical backoff protocols for contention resolution with multiple servers. Zbl 0938.68012
Goldberg, Leslie Ann; MacKenzie, Philip D.
3
1999
Construction computer virus phylogenies. Zbl 0891.68045
Goldberg, Leslie Ann; Goldberg, Paul W.; Phillips, Cynthia A.; Sorkin, Gregory B.
5
1998
An \(\omega(\sqrt{\log\log n})\) lower bound for routing in optical networks. Zbl 0907.68098
Goldberg, Leslie Ann; Jerrum, Mark; MacKenzie, Philip D.
1
1998
Better approximation guarantees for job-shop scheduling. Zbl 1321.68503
Goldberg, Leslie Ann; Paterson, Mike; Srinivasan, Aravind; Sweedyk, Elizabeth
5
1997
Doubly logarithmic communication algorithms for optical-communication parallel computers. Zbl 0885.68079
Goldberg, Leslie Ann; Jerrum, Mark; Leighton, Tom; Rao, Satish
4
1997
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
Listing graphs that satisfy first-order sentences. Zbl 0921.03041
Goldberg, Leslie Ann
1
1994
Efficient algorithms for listing combinatorial structures. Zbl 0821.68059
Goldberg, Leslie Ann
15
1993
Polynomial space polynomial delay algorithms for listing families of graphs. Zbl 1310.68108
Goldberg, Leslie Ann
2
1993
...and 2 more Documents
all top 5

Cited by 594 Authors

43 Goldberg, Leslie Ann
21 Jerrum, Mark R.
19 Cai, Jin-Yi
18 Dyer, Martin E.
12 Lu, Pinyan
10 Doerr, Benjamin
10 Galanis, Andreas
10 Guo, Heng
10 Štefankovič, Daniel
9 Vigoda, Eric
8 Richerby, David M.
7 Bulatov, Andrei A.
7 Jalsenius, Markus
7 Sinclair, Alistair
6 Chlebus, Bogdan Stanislaw
6 Greco, Gianluigi
6 Kötzing, Timo
6 Xia, Mingji
5 Bachrach, Yoram
5 Bezáková, Ivona
5 Kowalczyk, Michael
5 Kowalski, Dariusz R.
5 Lapinskas, John
5 Lengler, Johannes
5 Randall, Dana J.
5 Srivastava, Piyush
5 Witt, Carsten
5 Wooldridge, Michael J.
5 Yin, Yitong
4 Anantharamu, Lakshmi
4 Berenbrink, Petra
4 Curticapean, Radu
4 Dell, Holger
4 Diaconis, Persi Warren
4 Fischer, Simon-Raphael
4 Fu, Zhiguo
4 Martin, Russell A.
4 Nakano, Shin-ichi
4 Regts, Guus
4 Williams, Tyson
4 Yamakami, Tomoyuki
3 Barvinok, Alexander I.
3 Bordewich, Magnus
3 Chen, Xi
3 Elkind, Edith
3 Fomin, Fedor V.
3 Frieze, Alan Michael
3 Gamarnik, David
3 Göbel, Andreas-Nikolas
3 Goldberg, Paul W.
3 Greenhill, Catherine S.
3 Hayes, Thomas P.
3 Jansen, Klaus
3 Kochol, Martin
3 Mastrolilli, Monaldo
3 Mcquillan, Colin
3 Moffatt, Iain
3 Moran, Shlomo
3 Mossel, Elchanan
3 Müller, Haiko
3 Rokicki, Mariusz A.
3 Rosenschein, Jeffrey S.
3 Scarcello, Francesco
3 Scheideler, Christian
3 Serna, Maria José
3 Snir, Sagi
3 Yang, Linji
3 Zick, Yair
3 Živný, Stanislav
2 Ackermann, Heiner
2 Ågotnes, Thomas
2 Barish, Robert D.
2 Bhatnagar, Nayantara
2 Bi, Dianjie
2 Blanca, Antonio
2 Bläser, Markus
2 Bonamy, Marthe
2 Bousquet, Nicolas
2 Briceño, Raimundo
2 Cauwet, Marie-Liesse
2 Chalkiadakis, Georgios
2 Chebolu, Prasad
2 Cryan, Mary
2 Czumaj, Artur
2 Della Vedova, Gianluca
2 Doerr, Carola
2 Efthymiou, Charilaos
2 Ellis-Monaghan, Joanna A.
2 Endriss, Ulle
2 Erdős, Péter L.
2 Feng, Weiming
2 Filmus, Yuval
2 Fotakis, Dimitris A.
2 Friedetzky, Tom
2 Ge, Qi
2 Gießen, Christian
2 Grohe, Martin
2 Guzzo, Antonella
2 Gysel, Rob
2 Helmuth, Tyler
...and 494 more Authors
all top 5

Cited in 100 Serials

34 Theoretical Computer Science
22 Journal of Computer and System Sciences
21 Algorithmica
18 Random Structures & Algorithms
17 SIAM Journal on Computing
14 Information and Computation
13 Distributed Computing
12 Combinatorics, Probability and Computing
11 Theory of Computing Systems
10 Artificial Intelligence
9 Discrete Applied Mathematics
8 SIAM Journal on Discrete Mathematics
8 Computational Complexity
7 The Annals of Applied Probability
5 Operations Research Letters
5 International Journal of Foundations of Computer Science
5 Journal of Scheduling
4 Journal of Statistical Physics
4 Mathematical Social Sciences
4 Probability Theory and Related Fields
4 Journal of Combinatorial Optimization
4 Journal of Discrete Algorithms
3 Communications in Mathematical Physics
3 Information Processing Letters
3 Advances in Applied Mathematics
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 ACM Transactions on Computation Theory
2 Discrete Mathematics
2 Statistics & Probability Letters
2 Journal of Symbolic Computation
2 Statistical Science
2 Annals of Operations Research
2 Machine Learning
2 Linear Algebra and its Applications
2 Annals of Mathematics and Artificial Intelligence
2 Bernoulli
2 Constraints
2 Annals of Combinatorics
2 LMS Journal of Computation and Mathematics
2 Electronic Journal of Statistics
2 Journal of Theoretical Biology
1 Computer Physics Communications
1 Journal of Mathematical Physics
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 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 Social Choice and Welfare
1 Graphs and Combinatorics
1 Discrete & Computational Geometry
1 Computers & Operations Research
1 International Journal of Approximate Reasoning
1 Journal of Theoretical Probability
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 Mathematical Programming. Series A. Series B
1 Journal of Knot Theory and its Ramifications
1 Journal of Algebraic Combinatorics
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 Journal of Machine Learning Research (JMLR)
1 Advances in Difference Equations
1 Journal of Statistical Mechanics: Theory and Experiment
1 Oberwolfach Reports
1 Frontiers of Mathematics in China
1 Optimization Letters
1 Journal of Physics A: Mathematical and Theoretical
1 Journal of Dynamics and Games
1 Research in the Mathematical Sciences
1 Journal de la Société Française de Statistique & Revue de Statistique Appliquée
all top 5

Cited in 36 Fields

250 Computer science (68-XX)
136 Combinatorics (05-XX)
68 Probability theory and stochastic processes (60-XX)
52 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
48 Statistical mechanics, structure of matter (82-XX)
47 Operations research, mathematical programming (90-XX)
24 Statistics (62-XX)
21 Biology and other natural sciences (92-XX)
13 Numerical analysis (65-XX)
10 Mathematical logic and foundations (03-XX)
8 Information and communication theory, circuits (94-XX)
7 Quantum theory (81-XX)
6 Dynamical systems and ergodic theory (37-XX)
5 Order, lattices, ordered algebraic structures (06-XX)
5 Convex and discrete geometry (52-XX)
4 Number theory (11-XX)
4 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 Special functions (33-XX)
1 Approximations and expansions (41-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

Wikidata Timeline

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