Research Papers and Publications

Paul Goldberg

Return to main page

Links labelled "DOI" point to the official web page for the paper.

Refereed Journal Papers

L.A. Goldberg, P.W. Goldberg, P. Krysta and C. Ventre. Ranking Games that have Competitiveness-based Strategies. To appear in Theoretical Computer Science Journal version of ACM-EC 2010 paper below. DOI;
Available on arxiv

P.W. Goldberg, T.B. Sørensen, Rahul Savani and Carmine Ventre. On the Approximation Performance of Fictitious Play in Finite Games. International Journal of Game Theory (2012) DOI; Springer link

H. Ackermann, P.W. Goldberg, V. Mirrokni, H. Röglin, and B. Vöcking. Uncoordinated Two-Sided Matching Markets. SIAM J. Comput..  40(1) pp. 92-106. (2011) PDF; DOI
(Journal version of ACM-EC’08 paper below)

E. Elkind, L.A. Goldberg, P.W. Goldberg and M.J. Wooldridge. A Tractable and Expressive Class of Marginal Contribution Nets and Its Applications. Mathematical Logic Quarterly 55(4), pp. 362-376 (Aug 2009). PDF DOI
(Journal version of AAMAS’08 paper below)

E. Elkind, L.A. Goldberg, P.W. Goldberg, M. Wooldridge. On the Computational Complexity of Weighted Voting Games. Annals of Mathematics and Artificial Intelligence. Vol. 56, No. 2 pp 109-131 (June 2009). PDF of online version PDF of preprint DOI
(special issue for BISFAI’07 workshop; this is journal version of AAAI’07 paper below, having a slightly different title)

C. Daskalakis, P.W. Goldberg and C.H. Papadimitriou. The Complexity of Computing a Nash Equilibrium. Communications of the ACM Vol. 52 No. 02 pp. 89-97 (Feb 2009). PDF; DOI
This is an expository version of the SICOMP paper that appears in the “research highlights” section of the CACM; it is intended to give the intuition and ideas of the result, and the complexity class PPAD. See also Ehud Kalai’s “technical perspective” article just beforehand (DOI).

C. Daskalakis, P.W. Goldberg and C.H. Papadimitriou. The Complexity of Computing a Nash Equilibrium. SIAM Journal on Computing Vol. 39 No. 1 pp. 195-259 (May 2009). PDF; DOI; URL
(special issue of SICOMP for STOC’06). This paper was awarded the Game Theory and Computer Science prize at GAMES 08, the 3rd World Congress of the Game Theory Society, and a SIAM Oustanding Paper Prize in 2011.

H. Ackermann, P.W. Goldberg, V. Mirrokni, H. Röglin, and B. Vöcking. A Unified Approach to Congestion Games and Two-Sided Markets. Internet Mathematics 5(4) 439-457 (2008). URL; DOI
(special issue for WINE 2007)

P. Berenbrink, T.K. Friedetzky, L.A. Goldberg, P.W. Goldberg, R. Martin. Distributed Selfish Load Balancing. SIAM Journal on Computing. Vol. 37 No. 4, pp. 1163-1181 (2007). DOI
postscript of preprint; PDF of preprint

N. Palmer and P.W. Goldberg. PAC-learnability of Probabilistic Deterministic Finite State Automata in terms of Variation Distance. Theoretical Computer Science. Vol. 387 Issue 1 (2007), pp. 18-31. (Nov 2007) DOI
postscript of preprint; PDF of preprint

P. Berenbrink, L.A. Goldberg, P.W. Goldberg and R. Martin. Utilitarian Resource Assignment Journal of Discrete Algorithms Vol. 4 Issue 4, (Dec. 2006), 567-587. DOI
postscript of preprint; PDF (final version)

P.W. Goldberg. Some Discriminant-based PAC Algorithms Journal of Machine Learning Research Vol. 7 (2006), 283-306.
postscript of preprint; PDF of preprint; Abstract and on-line final version.

P.W. Goldberg. A Bound on the Precision Required to Estimate a Boolean Perceptron from its Average Satisfying Assignment SIAM Journal on Discrete Mathematics Vol. 20 Issue 2 (2006), 328-343. DOI
postscript (preprint 17.11.05.); PDF (final version)

S. Cenk Sahinalp, Evan Eichler, P.W. Goldberg, Petra Berenbrink, Tom Friedetzky, Funda Ergun. Identifying Uniformly Mutated Segments within Repeats. Journal of Bioinformatics and Computational Biology Vol. 2 Issue 4, pp. 657-668 (Dec. 2004) DOI
postscript; PDF

P.W. Goldberg. Learning Fixed-dimension Linear Thresholds from Fragmented Data. Information and Computation, Vol. 171 Issue 1, 98-122 (2001) DOI
postscript; PDF

L.A. Goldberg, P.W. Goldberg, M.S. Paterson, P. Pevzner, C. Sahinalp and E. Sweedyk. The Complexity of Gene Placement. Journal of Algorithms Vol. 41 Issue 2, 225-243 (2001) DOI
postscript (preprint); PDF (final version)

Mary Cryan, Leslie Ann Goldberg and Paul W. Goldberg. Evolutionary Trees can be Learned in Polynomial Time in the Two-State General Markov Model. SIAM Journal on Computing, Vol. 31 Issue 2, pp. 375-397 (2001). DOI
postscript (preprint); PDF (final version)

N.H. Bshouty, P.W. Goldberg, S.A. Goldman, H.D. Mathias. Exact Learning of Discretized Geometric Concepts. SIAM journal on computing 28 No. 2, pp. 674-699 (1998). (Tech. report WUCS-94-19, Dept. of Computer Science, Washington University (1994), 30pp.)
postscript; PDF; gzipped postscript.

L.A. Goldberg, P.W. Goldberg, C.A. Phillips, G. Sorkin. Constructing Computer Virus Phylogenies. Journal of Algorithms, Vol 26(1) (Jan. 98) pages 188--208.
postscript; PDF; gzipped postscript.

L.A. Goldberg, P.W. Goldberg, C.A. Phillips, Z Sweedyk, T. Warnow. Minimizing Phylogenetic Number to find Good Evolutionary Trees. Discrete Applied Mathematics, Vol. 71, Numbers 1-3 (Dec. 1996) pages 111--136. (special issue on combinatorial problems in biology)

P.W. Goldberg, S.A. Goldman, S.D. Scott. PAC Learning of One-dimensional Patterns. Machine Learning, 25(1), pages 51--70, (October 1996) Tech. report WUCS-95-10, dept. of Computer Science, Washington University (1995), 20pp.

P.W. Goldberg, M.C. Golumbic, H. Kaplan, R. Shamir. Four Strikes Against Physical Mapping of DNA. Journal of Computational Biology. Vol. 2, No. 1 (1995), pages 139--152. Tech. report 287/93, Dept. of Computer Science, Tel Aviv University (1993), 18pp.

P.W. Goldberg and M.R. Jerrum. Bounding the Vapnik-Chervonenkis Dimension of Concept Classes Parameterized by Real Numbers. Machine Learning, 18, pages 131--148, (1995) (special issue for COLT 93).
postscript; PDF; gzipped postscript. (These on-line copies are not quite identical to the journal version, but are very similar.)

Conference Papers

P.W. Goldberg and C. Ventre. Using Lotteries to Approximate the Optimal Revenue Proceedings of 12th AAMAS (2013).
Available on arxiv

P.W Goldberg and Arnoud Pastink. On the Communication Complexity of Approximate Nash Equilibria Procs of the 5th International Symposium on Algorithmic Game Theory LNCS 7615 pp.192-203 (Oct 2012). proceedings version;

P.W Goldberg and Antony McCabe. Commodity Auctions and Frugality Ratios Procs of the 5th International Symposium on Algorithmic Game Theory LNCS 7615 pp.180-191 (Oct 2012). proceedings version;

J. Fearnley, P.W Goldberg, R. Savani and T.B. Sørensen. Approximate Well-supported Nash Equilibria Below Two-thirds Procs of the 5th International Symposium on Algorithmic Game Theory LNCS 7615 pp.108-119 (Oct 2012). proceedings version; available on arXiv.

D. Ferraioli, P.W Goldberg and C. Ventre. Decentralized Dynamics for Finite Opinion Games Procs of the 5th International Symposium on Algorithmic Game Theory LNCS 7615 pp.144-155 (Oct 2012). proceedings version;

X. Deng, P.W. Goldberg, B. Tang, and J. Zhang. Multi-unit Bayesian Auction with Demand or Budget Constraints WIT-EC workshop, to appear, WIT-EC procs version slightly updated version

P.W. Goldberg, C.H. Papadimitriou and Rahul Savani. The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions 52nd FOCS pp. 67-76 (Oct 2011). New version, August 2011; Also available on arxiv. FOCS procs version; DOI of FOCS procs paper

P.W. Goldberg, T.B. Sørensen, Rahul Savani and Carmine Ventre. On the Approximation Performance of Fictitious Play in Finite Games procs of 19th ESA, LNCS 6942, pp. 93-105 (Sept 2011). ESA version; Available on arxiv March 2011; DOI of ESA procs paper
A journal version in International Journal on Game Theory is listed above.

P.W. Goldberg. How do you like your equilibrium selection problems? Hard, or very hard? short summary of invited talk at 3rd SAGT LNCS 6386, pp. 15-17 (Oct 2010).
PDF;

L.A. Goldberg, P.W. Goldberg, P. Krysta and C. Ventre. Ranking Games that have Competitiveness-based Strategies. Procs of the 11th ACM-EC Harvard University, MA, USA. (July 2010). pp. 335-344
postscript; PDF; DOI of ACM-EC procs paper

E. Elkind, L.A. Goldberg, P.W. Goldberg and M.J. Wooldridge. On the Dimensionality of Voting Games. Procs. of the 23rd AAAI Conference on AI Chicago, USA. (July 2008).
postscript; PDF;

H. Ackermann, P.W. Goldberg, V. Mirrokni, H. Röglin, and B. Vöcking. Uncoordinated Two-Sided Matching Markets. Procs. of the 9th ACM Conference on Electronic Commerce (EC’08) Chicago, USA (July 2008). postscript; PDF;
This paper received an “outstanding paper” award at the EC conference. There is a 6-page summary article in the July 2009 issue of sigecom exchanges.

H. Ackermann, P.W. Goldberg, V. Mirrokni, H. Röglin, and B. Vöcking. A Unified Approach to Congestion Games and Two-Sided Markets. Procs. of the 3rd Workshop on Internet and Network Economics (WINE) San Diego, CA, USA, Springer LNCS 4858 pp. 30-41 (Dec 2007). DOI
PDF;
Journal version in Internet Mathematics (see above), special issue for WINE 2007.

E. Elkind, L.A. Goldberg, P.W. Goldberg and M.J. Wooldridge. A Tractable and Expressive Class of Marginal Contribution Nets and Its Applications. Procs. of the 7th Int’l Conf on Autonomous Agents and Multiagent Systems (AAMAS) Estoril, Portugal (May 2008).
Conference programme; PDF

E. Elkind, L.A. Goldberg, P.W. Goldberg and M.J. Wooldridge. Computational Complexity of Weighted Threshold Games. Procs. of the 22nd AAAI Conference on AI Vancouver, BC, Canada, pp. 718-723 (July 2007).
conference procs; PDF

E. Elkind, L.A. Goldberg and P.W. Goldberg. Computing Good Nash Equilibria in Graphical Games. Procs. of the 8th ACM Conference on Electronic Commerce (ACM EC) San Diego, CA, USA, pp. 162-171 (2007). DOI
Full version on ArXiv; PDF

E. Elkind, L.A. Goldberg and P.W. Goldberg. Frugality Ratios and Improved Truthful Mechanisms for Vertex Cover. Procs. of the 8th ACM Conference on Electronic Commerce (ACM EC) San Diego, CA, USA, pp. 336-345 (2007). DOI
Full version on ArXiv;

E. Elkind, L.A. Goldberg and P.W. Goldberg. Nash Equilibria in Graphical Games on Trees Revisited. Procs. of the 7th ACM Conference on Electronic Commerce (ACM EC) Ann Arbor, Michigan, USA, pp. 100-109 (2006). DOI
earlier version in ECCC

C. Daskalakis, P.W. Goldberg and C.H. Papadimitriou. The Complexity of Computing a Nash Equilibrium. Procs. of the 38th Symp. on Theory of Computing (STOC) Seattle, Washington, USA, pp. 71-78 (May 2006). DOI
draft of the journal version
earlier version in ECCC

P.W. Goldberg and C.H. Papadimitriou. Reducibility Among Equilibrium Problems. Procs. of the 38th Symp. on Theory of Computing (STOC) Seattle, Washington, USA, pp. 61-70 (May 2006). DOI
STOC procs PDF; earlier version in ECCC

P. Berenbrink, T.K. Friedetzky, L.A. Goldberg, P.W. Goldberg, R. Martin. Distributed Selfish Load Balancing. Procs. of the 17th ACM-SIAM Symp. on Discrete Algorithms (SODA) (2006) 354-363. DOI
postscript; PDF; gzipped postscript (A journal version of this paper is available, see above).

N. Palmer and P.W. Goldberg. PAC-learnability of Probabilistic Deterministic Finite State Automata in terms of Variation Distance. Procs of the 16th Algorithmic Learning Theory (ALT) conference, Oct ’05, LNAI 3734, pp. 157-170. DOI of procs DOI
PDF

P.W. Goldberg. Bounds for the Convergence Rate of Randomized Local Search in a Multiplayer, Load-balancing Game. Procs of the 23rd Annual ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing (PODC) July ’04. pp. 131-140.
postscript; PDF; gzipped postscript.

M. Adler, P. Berenbrink, T. Friedetzky, L.A. Goldberg, P.W. Goldberg and M. Paterson. A Proportionate Fair Scheduling Rule with Good Worst-case Performance Procs of SPAA 2003, pp 101-8. June 7-9, San Diego, USA.
postscript; A journal submission of this paper is below.

S. Cenk Sahinalp, Evan Eichler, Paul Goldberg, Petra Berenbrink, Tom Friedetzky, Funda Ergun. Statistical Identification of Uniformly Mutated Segments within Repeats Procs of the 2002 Combinatorial Pattern Matching conference (Fukuoka, Japan, July 3-5 2002) LNCS 2373, pp. 249-261

P. Boonmee, P.W. Goldberg, NJ Saunders, SA Jarvis. A Computational Framework for the Detection and Identification of Horizontal Gene Transfer in Bacteria. The International Conference on Bioinformatics (InCoB 2002), Bangkok, Thailand. 6-8th February 2002.

P.W. Goldberg. When Can Two Unsupervised Learners Achieve PAC Separation? Procs of the 2001 COLT-EUROCOLT conference (Amsterdam, Netherlands, July 2001), LNAI 2111 pp. 303-319
postscript; PDF; gzipped postscript. A journal version improves and extends this work; it is entitled "Some Discriminant-based PAC Algorithms", above.

P.W. Goldberg. Estimating A Boolean Perceptron From Its Average Satisfying Assignment: A Bound on the Precision Required. Procs of the 2001 COLT-EUROCOLT conference (Amsterdam, Netherlands, July 2001), LNAI 2111 pp. 116-127
gzipped postscript; The journal version is above; it corrects a mistake in the proof.

P.W. Goldberg and S. Kwek. The Precision of Query Points as a Resource for Learning Convex Polytopes with Membership Queries. Procs of the 2000 COLT conference pp. 225-235 (Morgan-Kaufmann)

P.W. Goldberg. Learning Fixed-dimension Linear Thresholds from Fragmented Data. Procs of the 1999 Conference on Computational Learning Theory, pp. 88-99 July 1999.

L.A. Goldberg, P.W. Goldberg, M.S. Paterson, P. Pevzner, C. Sahinalp, E. Sweedyk. The Complexity of Gene Placement. procs. of Symp. on Discrete Algorithms , pp. 386-395, Jan. 1999.

L.A. Goldberg, P.W. Goldberg, M. Cryan. Evolutionary Trees can be Learned in Polynomial Time in the Two-State General Markov Model. 39th Symp. on Foundations of Computer Science , pp. 436-445, Nov. 1998.

P.W. Goldberg, C.K.I. Williams, C.M. Bishop. Regression with Input-dependent Noise: A Gaussian Process Treatment. Advances in Neural Information Processing Systems, pp. 493-499, (Dec. 1997).

L.A. Goldberg, P.W. Goldberg, C.A. Phillips, G. Sorkin. Constructing Computer Virus Phylogenies. In Proceedings of the seventh annual symposium on Combinatorial Pattern Matching (1996), 26pp.

L.A. Goldberg, P.W. Goldberg, C.A. Phillips, Z Sweedyk, T. Warnow. Minimizing Phylogenetic Number to find Good Evolutionary Trees. In Proceedings of the sixth annual symposium on Combinatorial Pattern Matching (1995), 26pp.

P.W. Goldberg and S.A. Goldman. Learning One-Dimensional Geometrical Patterns Under One-Sided Random Misclassification Noise. In Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, pages 246--255. July 1994. (Also presented at the 1993 Computational Learning and Natural Learning Workshop, September 1993. Provincetown, MA.)

P.W. Goldberg, S.A. Goldman, H.D. Mathias. Learning Unions of Boxes with Membership and Equivalence Queries. In Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, pages 198-207. July 1994.

P.W. Goldberg and M.R. Jerrum. Bounding the Vapnik-Chervonenkis Dimension of Concept Classes Parameterized by Real Numbers. In Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, pages 361-369. July 1993.

Other Papers

N. Chen, X. Deng, P.W. Goldberg and J. Zhang. On Revenue Maximization with Sharp Multi-Unit Demands available on arXiv. (Oct 2012)

P. Goldberg. A Survey of PPAD-Completeness for Computing Nash Equilibria Surveys in Combinatorics 2011 (London Mathematical Society Lecture Note Series 392) pp. 51-82, Cambridge University Press; Available on arxiv March 2011.

P. Briest, P.W. Goldberg and H. Röglin. Approximate Equilibria in Games with Few Players available on arXiv.

Heiner Ackermann, Paul W. Goldberg, Vahab S. Mirrokni, Heiko Röglin, and Berthold Vöcking Uncoordinated Two-Sided Markets RWTH-Aachen Dept. Computer Science Tech Rept. 2007-22.

E. Elkind, L.A. Goldberg and P.W. Goldberg. Frugality Ratios And Improved Truthful Mechanisms for Vertex Cover available on arXiv.

N. Palmer and P.W. Goldberg. PAC Classification Based on PAC Estimates of Label Class Distributions University of Warwick research report CS-RR-411 (last updated Jul 06) postscript; PDF; gzipped postscript. Also available on arXiv.

M. Adler, P. Berenbrink, T. Friedetzky, L.A. Goldberg, P.W. Goldberg and M. Paterson. A Proportionate Fair Scheduling Rule with Good Worst-case Performance
postscript; PDF; gzipped postscript.

P. Berenbrink, L.A. Goldberg, P.W. Goldberg, R. Martin. Utilitarian Resource Assignment. University of Warwick research report CS-RR-405
postscript; PDF; gzipped postscript; available from arXiv.

The Gap Between Sample Size Requirements for Learning Problems and VC-dimension Based Bounds. P.W. Goldberg. NCRG Tech. Report 97-001, Aston University.

Minimum-dilation multiple sequence alignment. J.E. Atkins, P.W. Goldberg, P. Mackenzie, C.A. Phillips and R. Ravi. Sandia National Laboratories Technical Report number SAND97-0273, 1997.

Complexity of Systems and Control Theory Problems. P.W. Goldberg, G.L. Heileman, and C. Abdallah. IMACS 95 Workshop on Computer Algebra, Albuquerque, NM, May, 1995. (Abstract)

PAC-Learning Geometrical Figures. Ph.D. dissertation, Department of Computer Science, University of Edinburgh, November 1992. 101pp.

Ground Completion. MSc thesis, Department of Computer Science, University of Edinburgh and Laboratoire de Recherche en Informatique, Université Paris-Sud, September 1989. 36pp.