Paul Goldberg

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

The unifying theme of my research is the rigorous mathematical analysis of algorithms, and computational challenges for which we are interested in designing algorithms. Until around the year 2001 the main emphasis was on computational learning theory, subsequently the emphasis has been computational game theory. Most of my work in game theory splits into 3 lines:

*Equilibrium computation*, which in turn has in turn attracted my interest in more abstract computational complexity questions. More details follow below.*Market intermediation*, how a middleman or intermediary can facilitate trade- Search for game-theoretic equilibria using
*query protocols*, where an algorithm can query individual payoffs of a game, or best-response behaviour of the players (see WINE 2018 paper with F Marmolejo-Cossío).

*The Complexity of Computing a Nash Equilibrium* (2006,09) is the
best-known paper I have co-authored; it’s not
the paper that started my interest in Algorithmic Game Theory, but it
affected much of my subsequent work. This paper,
showing that computation of Nash equilibrium is complete for the
complexity class PPAD, raised questions about what classes of games
are “hard” to solve and which are easy, also in what sense can we
convince ourselves that “PPAD-complete” indicate
hardness. A more general research theme is: TFNP is a class of problems
that seem to be hard but are (very) unlikely to be NP-hard, so we want
to understand the “complexity landscape” of this
interesting region between P and NP. PPAD is just a small part of this
picture…

A recent paper below that I would highlight is *The Complexity of
Splitting Necklaces and Bisecting Ham Sandwiches*, showing that
two important (and reasonably easy-to-understand) computational
problems are complete for the class PPA, whose definition is similar
to PPAD, but more is known about the hardness indicated by PPA-completeness.
Another contribution to the above-mentioned complexity landscape of
TFNP is *The Hairy Ball Problem is PPAD-Complete*, identifying
the complexity of the computational problem associated with the
classical “hairy ball theorem” and in the process,
showing equivalence of the End-of-line problem (that characterises
PPAD) with certain natural variants of it.

Elizabeth Baldwin, Paul W. Goldberg, Paul Klemperer, Edwin Lock.
**Solving Strong-Substitutes Product-Mix Auctions.**
*CoRR*:
ArXiv:1909.07313
(uploaded in Sept 2019)

Also here
as Nuffield College working paper 2019-W08.

Paul W. Goldberg.
**The Complexity of the Path-following Solutions of Two-dimensional Sperner/Brouwer Functions.**
*CoRR*:
ArXiv:1506.04882
(uploaded in June 2015)

Luka Gligic, Andrey Kormilitzin, Paul Goldberg, Alejo Nevado-Holgado.
**
Named entity recognition in electronic health records using transfer learning bootstrapped Neural Networks.
**
*Neural Networks*, in press (2019).

ScienceDirect link;
DOI 10.1016/j.neunet.2019.08.032.

Paul W. Goldberg, Francisco Marmolejo Cossío, and Steven Wu.
**
Logarithmic Query Complexity for Approximate Nash Computation in Large Games.
**
*Theory of Computing Systems*, **63**(1), pp. 26–53 (2019).

Springer link;
DOI 10.1007/s00224-018-9851-8.

Links to conference (SAGT 2016) and CoRR versions are below.

Paul W. Goldberg and C.H. Papadimitriou.
**Towards a Unified Complexity Theory of Total Functions.**
*Journal of Computer and System Sciences*, **94**, pp. 167–192 (2018).

link;
DOI 10.1016/j.jcss.2017.12.003

*Electronic Colloquium on Computational Complexity*,
Report TR17-056,
link;
PDF
(April 2017)

Links to conference (ITCS 2018) version below.

Paul W. Goldberg and Stefano Turchetta.
**Query Complexity of Approximate Equilibria in Anonymous Games.**
*Journal of Computer and System Sciences*, **90**, pp. 80–98 (2017).

link;
DOI 10.1016/j.jcss.2017.07.002.

(earlier version on arxiv: *CoRR*:
ArXiv:1412.6455
(first uploaded in Dec 2014; last revision 5 May 2016))

Links to conference (WINE 2015) version below.

Xiaotie Deng, Paul W. Goldberg, Yang Sun, Bo Tang and Jinshan Zhang.
**
Pricing Ad Slots with Consecutive Multi-unit Demand.
**
*Autonomous Agents and Multi-Agent Systems*,
**31**(3) pp. 584–605 (2017).

link;
DOI 10.1007/s10458-016-9335-7
;
full text view-only link.

D. Ferraioli, P.W. Goldberg and C. Ventre.
**
Decentralized Dynamics for Finite Opinion Games.
**
*Theoretical Computer Science* **648** pp. 96–115 (Oct 2016).
DOI 10.1016/j.tcs.2016.08.011
PDF;

Paul W. Goldberg and Aaron Roth.
**Bounds for the Query Complexity of Approximate Equilibria.**
*ACM Transactions on Economics and Computation* **4**(4)
pp. 24:1–25 (Aug. 2016).
(special issue for ACM-EC 2014)
PDF (local copy);
ACM
DL link;
DOI 10.1145/2956582.
Links to conference and arxiv versions are below.

John Fearnley, Martin Gairing, Paul W. Goldberg, and Rahul Savani.
**Learning Equilibria of Games via Payoff Queries.**
*Journal of Machine Learning Research* **16** pp. 1305–1344 (2015).
PDF (local copy);
PDF at JMLR.
Links to conference and arxiv versions are below.

John Fearnley, Paul W. Goldberg, Rahul Savani and Troels Bjerre Sørensen.
**Approximate Well-supported Nash Equilibria Below Two-thirds.**
*Algorithmica* **76**(2) pp. 297–319 (2016). (first online July 2015)
PDF (local copy);
Springer link
DOI 10.1007/s00453-015-0029-3
Links to conference and arxiv versions are below.

Ning Chen, Xiaotie Deng, Paul W. Goldberg, and Jinshan Zhang.
**On Revenue Maximization with Sharp Multi-Unit Demands.**
*Journal of Combinatorial Optimization* **31**(3)
pp. 1174–1205 (2016, first online Dec 2014).
PDF (local copy);
Online First link;
DOI link.

Xiaotie Deng, Paul W. Goldberg, Bo Tang, and Jinshan Zhang.
**Multi-unit Bayesian Auction with Demand or Budget Constraints.**
*Computational Intelligence* **32**(3) pp. 366–368.
PDF (local copy);
DOI link
(August 2016, first published online in 2014).

Xiaotie Deng, Paul W. Goldberg, Bo Tang, and Jinshan Zhang.
**Revenue Maximization in a Bayesian Double Auction Market.**
*Theoretical Computer Science* **539**: 1–12 (2014)

PDF (local copy);
link;
DOI link;
(journal version of ISAAC 2012 paper, below)

Paul W. Goldberg and Arnoud Pastink.
**On the Communication Complexity of Approximate Nash Equilibria.**
*Games and Economic Behavior*, **85**, pp. 19–31 (May 2014)

PDF (local copy);
link;
DOI link
(journal version of SAGT 2012 paper, below)

Leslie A. Goldberg, Paul W. Goldberg, Piotr Krysta, and Carmine Ventre.
**Ranking Games that have Competitiveness-based Strategies.**
*Theoretical Computer Science*
**476** pp.24–37 (2013).
Journal version of ACM-EC 2010 paper below.
DOI;

Available on arxiv

Paul W. Goldberg, Troels Bjerre Sørensen, Rahul Savani, and Carmine Ventre.
**On the Approximation Performance of Fictitious Play in Finite Games.**
*International Journal of Game Theory* **42**(4) pp.1059–1083 (2013)
DOI;
Springer link;
PDF

Paul W. Goldberg, Christos H. Papadimitriou, and Rahul Savani.
**The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions**
*ACM Transactions on Economics and Computation* **1**(2) pp.9:1–9:25 (2013)
DOI;
PDF

Heiner Ackermann, Paul W. Goldberg, Vahab Mirrokni, Heiko Röglin, and Berthold 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)

Edith Elkind, Leslie A. Goldberg, Paul W. Goldberg, and Michael 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)

Edith Elkind, Leslie A. Goldberg, Paul W. Goldberg, and Michael J. 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)

Constantinos Daskalakis, Paul W. Goldberg, and Christos 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).

Constantinos Daskalakis, Paul W. Goldberg, and Christos 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) pp. 439–457 (2008).
PDF;
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), pp. 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), pp. 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), pp. 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, pp. 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, pp. 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*, **26**(1) (Jan. 98) pp. 188–208.

PDF (final version);
PDF (earlier version);
DOI link;

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

PDF;
DOI link.

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

PDF;
DOI: 10.1007/BF00115300
DOI: 10.1023/A:1018396106080

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),
pp. 139–152.
Tech. report 287/93, Dept. of Computer Science, Tel Aviv
University (1993), 18pp.

DOI: 10.1089/cmb.1995.2.139

P.W. Goldberg and M.R. Jerrum.
**Bounding the Vapnik-Chervonenkis Dimension of Concept Classes
Parameterized by Real Numbers.**
*Machine Learning*, 18, pp. 131–148, (1995)
(special issue for COLT 93).

PDF;
DOI: 10.1007/BF00993408

Paul W. Goldberg, Alexandros Hollender, and Warut Suksompong.
**Contiguous Cake Cutting: Hardness Results and Approximation Algorithms.**
AAAI 2020:
34th AAAI Conference on Artificial Intelligence, pp. TBA (Feb 2020).

*arxiv preprint*
ArXiv:1911.05416
(last uploaded in Jan 2020);
PDF (local copy).

Paul W. Goldberg and Alexandros Hollender.
**The Hairy Ball Problem is PPAD-Complete.**
ICALP 2019:
Procs. of
46th International Colloquium on Automata, Languages and Programming, pp. 65:1–65:14 (July 2019).

DOI: 10.4230/LIPIcs.ICALP.2019.65

*arxiv preprint*
ArXiv:1902.07657
(last uploaded in May 2019)

Aris Filos-Ratsikas and Paul W. Goldberg.
**The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches.**
STOC 2019:
51st Annual ACM SIGACT Symposium on the Theory of Computing, pp. 638–649 (June 2019).

DOI: 10.1145/3313276.3316334

*arxiv preprint*
ArXiv:1805.12559
(last uploaded in Nov 2018)
PDF (local copy);

Matthias Gerstgrasser, Paul W. Goldberg, Bart de Keijzer, Philip
Lazos, and Alexander Skopalik.
**Multi-unit Bilateral Trade.**
Procs. of 33rd AAAI, pp. 1973–1980, (2019).

DOI: 10.1609/aaai.v33i01.33011973

*arxiv preprint*
ArXiv:1811.05130

Paul W. Goldberg and Francisco J. Marmolejo-Cossío.
**Learning Convex Partitions and Computing Game-theoretic Equilibria from Best Response Queries.**
*Procs of 14th WINE*, LNCS 11316, pp. 168–187, (Dec. 2018).

DOI: 10.1007/978-3-030-04612-5_12

Full version:
*CoRR*:
ArXiv:1807.06170
(uploaded in July 2018)

Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Paul W. Goldberg, and Jie Zhang.
**Hardness Results for Consensus-Halving.**
*Procs. of 43rd
International Symposium on Mathematical Foundations of Computer
Science (MFCS 2018)* pp. 24:1–24:16 (August 2018).

Links:
proceedings web site;
DOI 10.4230/LIPIcs.MFCS.2018.24;
local copy

*arxiv preprint* ArXiv:1609.05136
(uploaded in Sept 2016)

Aris Filos-Ratsikas and Paul W. Goldberg.
**Consensus Halving is PPA-Complete.**
*Procs. of the 50th STOC symposium*, pp. 51–64 (June 2018).

Links:
local copy (PDF);
DOI: 10.1145/3188745.3188880

*arxiv preprint* ArXiv:1711.04503
(uploaded in Nov 2017)

Paul W. Goldberg and C.H. Papadimitriou.
**Towards a Unified Complexity Theory of Total Functions.**
*Procs. of the 9th Innovations in Theoretical Computer Science
(ITCS) conference*, pp. 37:1–37:20 (January 2018).

paper available at
Proceedings website;
link to PDF;
DOI 10.4230/LIPIcs.ITCS.2018.37;
Conference website

Riccardo Colini-Baldeschi, Paul Goldberg, Bart de Keijzer, Stefano
Leonardi, Stefano Turchetta.
**
Fixed Price Approximability of the Optimal Gain From Trade.
**
*Procs
of 13th
International Conference on Web and Internet Economics
(WINE)*, LNCS 10660, pp. 146–160 (Dec, 2017).
DOI 10.1007/978-3-319-71924-5_11;
local copy (PDF);
ArXiv:1710.08394.

Haris Aziz, Paul W. Goldberg and Toby Walsh.
**
Equilibria in Sequential Allocation.
**
*Procs of 5th ADT* LNAI
10576, pp. 270–283 (Oct, 2017).

DOI: 10.1007/978-3-319-67504-6_19;
ArXiv:1705.09444.

Riccardo Colini-Baldeschi, Paul Goldberg, Bart de Keijzer, Stefano
Leonardi, Tim Roughgarden, and Stefano Turchetta.
**Approximately Efficient Two-Sided Combinatorial Auctions.**
In EC ’17
Proceedings of the 18th ACM Conference on Economics and Computation
pp. 591–608.
Cambridge, Massachusetts, USA, June 26–30, 2017
link;
DOI link;
PDF (local copy);
ArXiv:1611.05342
(uploaded in Nov 2016)

Paul W. Goldberg and Christos H. Papadimitriou.
**
TFNP: An Update.
**
*Procs of 10th CIAC*
LNCS 10236, pp. 3–9, (May, 2017).

link;
PDF (local copy),
DOI link.

Matthias Gerstgrasser, Paul W. Goldberg, and Elias Koutsoupias.
**
Revenue Maximization for Market Intermediation with Correlated Priors
**
*Procs of 9th SAGT*
LNCS 9928, pp. 273–285, (Sept. 2016).

PDF (local copy),
DOI link.

Paul W. Goldberg, Francisco Marmolejo Cossío, and Steven Wu.
**
Logarithmic Query Complexity for Approximate Nash Computation in Large Games
**
PDF,
DOI link.
*Procs of 9th SAGT*
LNCS 9928, pp. 3–14, (Sept. 2016).
Full version:
ArXiv:1610.08906
(uploaded in Oct 2016)

Baharak Rastegari, Paul Goldberg, David Manlove.
**Preference Elicitation in Matching Markets via Interviews: A Study of
Offline Benchmarks.**
*2-page summary in AAMAS.* (2016)
AAMAS procs (2pp) (camera ready version).
EXPLORE workshop procs (camera ready version);
ArXiv full version.
EXPLORE workshop program

George Christodoulou, Aris Filos-Ratsikas, Soren Kristoffer Stiil
Frederiksen, Paul W. Goldberg, Jie Zhang, and Jinshan Zhang.
**Social Welfare in One-Sided Matching Mechanisms.**
*2-page summary in AAMAS.* (2016)

AAMAS procs (2pp) (camera ready version);

There’s a longer version in the AAMAS 2016 workshops (best
papers) volume (the paper was presented at the EXPLORE workshop) associated with
AAMAS, which should be cited as follows.
In: Osman N., Sierra C. (eds) Autonomous Agents and Multiagent
Systems. AAMAS 2016. Lecture Notes in Computer Science, vol 10002,
pp. 30–50. Springer.

DOI link.
EXPLORE workshop procs (camera ready version);
EXPLORE workshop program.
In LNAI 10002 (AAMAS 2016 workshops, best papers)

earlier version on arxiv (same authors):
**Welfare Ratios in One-Sided Matching Mechanisms.**
*CoRR*:
ArXiv:1502.03849
(uploaded in Feb 2015)

Paul W. Goldberg and Stefano Turchetta.
**Query Complexity of Approximate Equilibria in Anonymous Games.**
*Procs of 11th WINE*
LNCS 9470, pp. 357–369 (Dec. 2015).
proceedings version;
DOI link.

Paul W. Goldberg and Bo Tang.
**
Auction Design with a Revenue Target.
**
*Procs of 8th SAGT*
LNCS 9347, pp. 137–149 (2015).
proceedings version;
DOI link.

Paul W. Goldberg and Aaron Roth.
**
Bounds for the Query Complexity of Approximate Equilibria.
**
*Procs of ACM-EC* pp. 639–656 (2014).
proceedings version;
DOI link;
(earlier version: ECCC Technical Report
number 136 (Sept. 2013))

Xiaotie Deng, Paul W. Goldberg, Yang Sun, Bo Tang and Jinshan Zhang.
**
Pricing Ad Slots with Consecutive Multi-unit Demand.
**
*Procs of SAGT*
LNCS 8146, pp. 255–266 (2013).
proceedings version (PDF, local copy);
link;
DOI 10.1007/978-3-642-41392-6_22.

John Fearnley, Martin Gairing, Paul W. Goldberg, and Rahul Savani.
**
Learning Equilibria of Games via Payoff Queries.
**
*Procs of ACM-EC* pp. 397–414 (2013).
proceedings version;
available on arXiv.

Paul W. Goldberg and Carmine Ventre.
**
Using Lotteries to Approximate the Optimal Revenue.
**
Proceedings of 12th AAMAS, pp. 643–650 (2013).
link to AAMAS paper

Available on arxiv

Paul W. Goldberg and Antony McCabe.
**
Shortest Paths with Bundles and Non-Additive Weights is Hard.
**
*Procs of the 8th CIAC* LNCS 7878 pp. 264–275 (2013).
proceedings version;

Xiaotie Deng, Paul W. Goldberg, Bo Tang and Jinshan Zhang.
**
Revenue Maximization in a Bayesian Double Auction Market.
**
*Procs. of the 23rd ISAAC*
LNCS 7676 pp. 690–699 (Dec. 2012)
proceedings version;
link;
DOI

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;

Available on arxiv

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,
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;
DOI 10.1007/978-3-642-16170-4_2.

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.
(Vol 8 No. 1 July 2009)

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 10.1145/1250910.1250935

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 link;
Full version on ArXiv;
PDF

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).

PDF (local copy);
DOI link;
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).

PDF;
DOI 10.1145/1132516.1132527.

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)*
pp. 354–363 (2006).
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,*
LNAI 3734, pp. 157–170 (Oct. 2005).
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)*
pp. 131–140 (July 2004).

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.C. Sahinalp, E. Eichler, P.W. Goldberg, P. Berenbrink, T. Friedetzky, F. 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*
gzipped PS

P. Boonmee, P.W. Goldberg, N.J. Saunders, S.A. 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.*
gzipped .doc

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 13th Conference on Computational Learning Theory
(COLT)* pp. 225–235 (Morgan-Kaufmann) (2000).

PDF;

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).

PDF (as in proceedings);
older version

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), pp 253–270.

PDF (as in proceedings);
DOI link

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*,
pp. 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*, pp. 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*, pp. 361–369 (July 1993).

DOI 10.1145/168304.168377.

Alexandros Hollender and Paul W. Goldberg.
**The Complexity of Multi-source Variants of the End-of-Line Problem, and the Concise Mutilated Chessboard.**
*Electronic Colloquium on Computational Complexity*,
Report TR18-120
(June 2018).

Luka Gligic, Andrey Kormilitzin, Paul Goldberg, Alejo Nevado-Holgado.
**Named Entity Recognition in Electronic Health Records Using Transfer Learning Bootstrapped Neural Networks.**
*CoRR*:
ArXiv:1901.01592
(uploaded in January 2019)

Maximilian Hofer, Andrey Kormilitzin, Paul Goldberg, Alejo Nevado-Holgado.
**Few-shot Learning for Named Entity Recognition in Medical Text.**
*CoRR*:
ArXiv:1811.05468
(uploaded in November 2018)

Paul W. Goldberg, Yishay Mansour, and Paul Dütting.
**
Game Theory Meets Computational Learning Theory (Dagstuhl Seminar 17251).
**
*Dagstuhl Reports* **7**(6): pp. 68–85 (2017).
link;
DOI link;
local copy (PDF).

Paul W. Goldberg.
**
Learning Game-Theoretic Equilibria Via Query Protocols.
**
In: Díaz J., Kirousis L., Ortiz-Gracia L., Serna M. (eds)
Extended Abstracts Summer 2015.
*Trends in
Mathematics* **6**: pp. 67–72 (Feb 2017).
preprint;
link;
DOI link.

John Fearnley, Martin Gairing, Paul W. Goldberg and Rahul Savani.
**Learning Equilibria of Games via Payoff Queries**
available on arXiv. (Feb 2013)

Ning Chen, Xiaotie Deng, Paul W. Goldberg and Jinshan 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.

“Every morning when I wake up, I want to be surprised by whatever I might think up today!”

(Jan Sandström)

“Anyway, it goes like this: there’s this desert prison, see, with an old prisoner, resigned to his life, and a young one just arrived. The young one talks constantly of escape, and, after a few months, he makes a break. He’s gone a week, and then he’s brought back by the guards. He’s half dead, crazy with hunger and thirst. He describes how awful it was to the old prisoner. The endless stretches of sand, no oasis, no signs of life anywhere. The old prisoner listens for a while, then says, ‘Yep, I know. I tried to escape myself, twenty years ago.’ The young prisoner says, ‘You did? Why didn't you tell me, all these months I was planning my escape? Why didn't you let me know it was impossible?’ And the old prisoner shrugs, and says, ‘So who publishes negative results?’”

(from *A Case of Need*, by Michael Crichton)

“All day long I think of things but nothing seems to satisfy”

(from *Paranoid*, by Black Sabbath)

“Everyone knows by now that some triviality always has to occur in my work, but this time it goes beyond all bounds.”

(Gustav Mahler)