Leslie Ann Goldberg
Publications
Preprints
- L.A. Goldberg and M. Jerrum, The Complexity of Computing
the Sign of the Tutte Polynomial (and consequent #P-hardness of
Approximation), arXiv:1202.0313 [cs.CC]
Submitted.
- J. Diaz, L.A. Goldberg, G.B. Mertzios, D. Richerby, M. Serna and P.G. Spirakis,
Can Fixation be Guaranteed in the
Generalized Moran Process? arXiv:1202.0436 [cs.CE]
Submitted.
- P. Chebolu, L.A. Goldberg and R. Martin,
The complexity of approximately counting stable roommate assignments,
arXiv:1012.1237 [cs.CC] Submitted.
- L.A. Goldberg and M. Jerrum, Approximating the Tutte polynomial of a binary matroid and other
related combinatorial polynomials, arXiv:1006.5234 [cs.CC]
Submitted.
To appear
2012
- 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,
to appear in STACS 2012.
- J. Diaz, L.A. Goldberg, G.B. Mertzios, D. Richerby, M. Serna and P.G. Spirakis,
Approximating Fixation Probabilities in the
Generalized Moran Process,
to appear in SODA 2012.
2011
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. (superseded by 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.
- B. Doerr and L.A. Goldberg, Adaptive Drift Analysis
Proceedings of
PPSN 2010, 32-41. (superseded by journal version)
- B. Doerr and L.A. Goldberg, Drift Analysis with Tail Bounds, Proceedings
of
PPSN 2010, 174-183. (superseded by journal version)
- 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.
- M. Dyer, L.A. Goldberg, M. Jalsenius and D. Richerby,
The Complexity of Approximating
Bounded-Degree Boolean #CSP,
arXiv:0907.2663v1 [cs.CC] (July, 2009) Proceedings of STACS 2010.
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. (superseded by 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. (superseded by 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
(superseded by journal version)
- 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
(superseded by 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.
(superseded by 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
(superseded by 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.
(superseded by journal version)
-
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
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.
(superseded by 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, On
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).
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 (superseded by 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 (superseded by 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) (superseded by 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 (superseded by 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
(superseded by
journal
version)
- M. Dyer, L.A. Goldberg, C. Greenhill and M. Jerrum, On
the relative complexity of approximate counting problems, Proceedings of APPROX
2000
(superseded by 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
(superseded by 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)
(superseded by
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 (superseded
by
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 (superseded by 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 (superseded
by
journal
verson)
- 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.
(superseded by journal version)
-
L.A. Goldberg and M. Jerrum,
Randomly Sampling Molecules, Proceedings of SODA 8 (1997)
183-192
(superseded by 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.
(superseded by journal version)
-
L.A. Goldberg, M. Paterson, A. Srinivasan and E. Sweedyk,
Better Approximation Guarantees for Job-Shop Scheduling,
Proceedings of SODA
(1997) 599-608.
(superseded by 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
(superseded by 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.
(superseded by 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.
(superseded by 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
-
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.
(superseded by journal version)
1994
- L.A. Goldberg, Listing Graphs that Satisfy First Order Sentences,
Journal of Computer and Systems Sciences 49(2) (1994) 408--424.
-
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.
(superseded by 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.
(superseded by 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.
- L.A. Goldberg, Efficient Algorithms for Listing Combinatorial
Structures, (Cambridge University Press, 1993).
-
L.A. Goldberg,
Listing Graphs that Satisfy First Order Sentences,
Proceedings of STOC (1993)
218-225.
(superseded by journal version)
-
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.
(superseded by journal version)
1992
- L.A. Goldberg, Efficient Algorithms for Listing Unlabeled Graphs,
Journal of Algorithms 13(1) (1992) 128--143.
1990
- L.A. Henderson (now Goldberg), 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.
unpublished
Leslie Goldberg's Home
Page.