Paul W. Goldberg

According to our database, Paul W. Goldberg authored at least 108 papers between 1993 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

Complexity of Unambiguous Problems in Σ^P₂.

Matan Gilboa, Paul W. Goldberg, Elias Koutsoupias, Noam Nisan

CoRR, October, 2025

Decentralized Convergence to Equilibrium Prices in Trading Networks.

Edwin Lock, Benjamin Patrick Evans, Eleonora Kreacic, Sujay Bhatt, Alec Koppel, Sumitra Ganesh, Paul W. Goldberg

Proceedings of the AAAI-25, Sponsored by the Association for the Advancement of Artificial Intelligence, February 25, 2025

2024

Solving Strong-Substitutes Product-Mix Auctions.

Elizabeth Baldwin, Paul W. Goldberg, Paul Klemperer, Edwin Lock

Math. Oper. Res., 2024

Continuous-Time Best-Response and Related Dynamics in Tullock Contests with Convex Costs.

Edith Elkind, Abheek Ghosh, Paul W. Goldberg

CoRR, 2024

The Complexity of Computing KKT Solutions of Quadratic Programs.

John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Imperfect-Recall Games: Equilibrium Concepts and Their Complexity.

Emanuel Tewolde, Brian Hu Zhang, Caspar Oesterheld, Manolis Zampetakis, Tuomas Sandholm, Paul Goldberg, Vincent Conitzer

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, 2024

2023

PPAD-complete approximate pure Nash equilibria in Lipschitz games.

Paul W. Goldberg, Matthew J. Katzman

Theor. Comput. Sci., November, 2023

Editorial from the New Co-Editors-in-Chief of ACM Transactions on Economics and Computation.

Paul Goldberg, M. Utku Ünver

ACM Trans. Economics and Comput., 2023

Substitutes markets with budget constraints: solving for competitive and optimal prices.

Simon Finster, Paul W. Goldberg, Edwin Lock

CoRR, 2023

Best-Response Dynamics in Lottery Contests.

Abheek Ghosh, Paul W. Goldberg

Proceedings of the 24th ACM Conference on Economics and Computation, 2023

The Frontier of Intractability for EFX with Two Agents.

Paul W. Goldberg, Kasper Høgh, Alexandros Hollender

Proceedings of the Algorithmic Game Theory - 16th International Symposium, 2023

Consensus Division in an Arbitrary Ratio.

Paul Goldberg, Jiawei Li

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

The Computational Complexity of Single-Player Imperfect-Recall Games.

Emanuel Tewolde, Caspar Oesterheld, Vincent Conitzer, Paul W. Goldberg

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, 2023

2022

PPAD-Complete Pure Approximate Nash Equilibria in Lipschitz Games.

Paul W. Goldberg, Matthew J. Katzman

Proceedings of the Algorithmic Game Theory - 15th International Symposium, 2022

Simultaneous Contests with Equal Sharing Allocation of Prizes: Computational Complexity and Price of Anarchy.

Edith Elkind, Abheek Ghosh, Paul W. Goldberg

Proceedings of the Algorithmic Game Theory - 15th International Symposium, 2022

Contests to Incentivize a Target Group.

Edith Elkind, Abheek Ghosh, Paul W. Goldberg

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, 2022

Complexity of Deliberative Coalition Formation.

Edith Elkind, Abheek Ghosh, Paul Goldberg

Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, 2022

2021

Equivalence of Models of Cake-Cutting Protocols.

Paul W. Goldberg, Ioana Iaru

CoRR, 2021

Contest Design with Threshold Objectives.

Edith Elkind, Abheek Ghosh, Paul W. Goldberg

Proceedings of the Web and Internet Economics - 17th International Conference, 2021

The complexity of gradient descent: CLS = PPAD ∩ PLS.

John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Lower Bounds for the Query Complexity of Equilibria in Lipschitz Games.

Paul W. Goldberg, Matthew J. Katzman

Proceedings of the Algorithmic Game Theory - 14th International Symposium, 2021

2020

Named entity recognition in electronic health records using transfer learning bootstrapped Neural Networks.

Luka Gligic, Andrey Kormilitzin, Paul Goldberg, Alejo J. Nevado-Holgado

Neural Networks, 2020

Learning Strong Substitutes Demand via Queries.

Paul W. Goldberg, Edwin Lock, Francisco J. Marmolejo Cossío

Proceedings of the Web and Internet Economics - 16th International Conference, 2020

Consensus Halving for Sets of Items.

Paul W. Goldberg, Alexandros Hollender, Ayumi Igarashi, Pasin Manurangsi, Warut Suksompong

Proceedings of the Web and Internet Economics - 16th International Conference, 2020

Contiguous Cake Cutting: Hardness Results and Approximation Algorithms.

Paul W. Goldberg, Alexandros Hollender, Warut Suksompong

Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, 2020

2019

The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich.

Aris Filos-Ratsikas, Paul W. Goldberg

SIAM J. Comput., 2019

The complexity of splitting necklaces and bisecting ham sandwiches.

Aris Filos-Ratsikas, Paul W. Goldberg

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

The Hairy Ball Problem is PPAD-Complete.

Paul W. Goldberg, Alexandros Hollender

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Multi-Unit Bilateral Trade.

Matthias Gerstgrasser, Paul W. Goldberg, Bart de Keijzer, Philip Lazos, Alexander Skopalik

Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, 2019

2018

The Complexity of Multi-source Variants of the End-of-Line Problem, and the Concise Mutilated Chessboard.

Alexandros Hollender, Paul W. Goldberg

Electron. Colloquium Comput. Complex., 2018

Few-shot Learning for Named Entity Recognition in Medical Text.

Maximilian Hofer, Andrey Kormilitzin, Paul W. Goldberg, Alejo J. Nevado-Holgado

CoRR, 2018

Learning Convex Partitions and Computing Game-Theoretic Equilibria from Best Response Queries.

Paul W. Goldberg, Francisco J. Marmolejo Cossío

Proceedings of the Web and Internet Economics - 14th International Conference, 2018

Consensus halving is PPA-complete.

Aris Filos-Ratsikas, Paul W. Goldberg

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Hardness Results for Consensus-Halving.

Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Paul W. Goldberg, Jie Zhang

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

Towards a Unified Complexity Theory of Total Functions.

Paul W. Goldberg, Christos H. Papadimitriou

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

2017

Game Theory Meets Computational Learning Theory (Dagstuhl Seminar 17251).

Paul W. Goldberg, Yishay Mansour, Paul Dütting

Dagstuhl Reports, 2017

Fixed Price Approximability of the Optimal Gain from Trade.

Riccardo Colini-Baldeschi, Paul W. Goldberg, Bart de Keijzer, Stefano Leonardi, Stefano Turchetta

Proceedings of the Web and Internet Economics - 13th International Conference, 2017

Approximately Efficient Two-Sided Combinatorial Auctions.

Riccardo Colini-Baldeschi, Paul W. Goldberg, Bart de Keijzer, Stefano Leonardi, Tim Roughgarden, Stefano Turchetta

Proceedings of the 2017 ACM Conference on Economics and Computation, 2017

TFNP: An Update.

Paul W. Goldberg, Christos H. Papadimitriou

Proceedings of the Algorithms and Complexity - 10th International Conference, 2017

Equilibria in Sequential Allocation.

Haris Aziz, Paul Goldberg, Toby Walsh

Proceedings of the Algorithmic Decision Theory - 5th International Conference, 2017

2016

On revenue maximization with sharp multi-unit demands.

Ning Chen, Xiaotie Deng, Paul W. Goldberg, Jinshan Zhang

J. Comb. Optim., 2016

EATCS Fellows 2017 - Call for Nominations.

Paul Goldberg

Bull. EATCS, 2016

Preference Elicitation in Matching Markets via Interviews: A Study of Offline Benchmarks.

Baharak Rastegari, Paul Goldberg, David F. Manlove

CoRR, 2016

Multi-Unit Bayesian Auction with Demand or Budget Constraints.

Xiaotie Deng, Paul W. Goldberg, Bo Tang, Jinshan Zhang

Comput. Intell., 2016

Logarithmic Query Complexity for Approximate Nash Computation in Large Games.

Paul W. Goldberg, Francisco J. Marmolejo Cossío, Zhiwei Steven Wu

Proceedings of the Algorithmic Game Theory - 9th International Symposium, 2016

Revenue Maximization for Market Intermediation with Correlated Priors.

Matthias Gerstgrasser, Paul W. Goldberg, Elias Koutsoupias

Proceedings of the Algorithmic Game Theory - 9th International Symposium, 2016

Preference Elicitation in Matching Markets via Interviews: A Study of Offline Benchmarks (Extended Abstract).

Baharak Rastegari, Paul Goldberg, David F. Manlove

Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, 2016

Social Welfare in One-Sided Matching Mechanisms.

George Christodoulou, Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Paul W. Goldberg, Jie Zhang, Jinshan Zhang

Proceedings of the Autonomous Agents and Multiagent Systems - AAMAS 2016 Workshops, - Best Papers, 2016

Social Welfare in One-Sided Matching Mechanisms: (Extended Abstract).

George Christodoulou, Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Paul W. Goldberg, Jie Zhang, Jinshan Zhang

Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, 2016

2015

The Complexity of the Path-following Solutions of Two-dimensional Sperner/Brouwer Functions.

Paul W. Goldberg

CoRR, 2015

Welfare Ratios in One-Sided Matching Mechanisms.

George Christodoulou, Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Paul W. Goldberg, Jie Zhang, Jinshan Zhang

CoRR, 2015

Query Complexity of Approximate Equilibria in Anonymous Games.

Paul W. Goldberg, Stefano Turchetta

Proceedings of the Web and Internet Economics - 11th International Conference, 2015

Algorithmic Game Theory (Tutorial).

Paul W. Goldberg

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

Auction Design with a Revenue Target.

Paul W. Goldberg, Bo Tang

Proceedings of the Algorithmic Game Theory - 8th International Symposium, 2015

2014

Bounds for the query complexity of approximate equilibria.

Paul W. Goldberg, Aaron Roth

Proceedings of the ACM Conference on Economics and Computation, 2014

2013

Learning equilibria of games via payoff queries.

John Fearnley, Martin Gairing, Paul Goldberg, Rahul Savani

Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013

Pricing Ad Slots with Consecutive Multi-unit Demand.

Xiaotie Deng, Paul W. Goldberg, Yang Sun, Bo Tang, Jinshan Zhang

Proceedings of the Algorithmic Game Theory - 6th International Symposium, 2013

Shortest Paths with Bundles and Non-additive Weights Is Hard.

Paul W. Goldberg, Antony McCabe

Proceedings of the Algorithms and Complexity, 8th International Conference, 2013

Using lotteries to approximate the optimal revenue.

Paul W. Goldberg, Carmine Ventre

Proceedings of the International conference on Autonomous Agents and Multi-Agent Systems, 2013

2012

On the Communication Complexity of Approximate Nash Equilibria.

Paul W. Goldberg, Arnoud Pastink

Proceedings of the Algorithmic Game Theory - 5th International Symposium, 2012

Commodity Auctions and Frugality Ratios.

Paul W. Goldberg, Antony McCabe

Proceedings of the Algorithmic Game Theory - 5th International Symposium, 2012

Decentralized Dynamics for Finite Opinion Games.

Diodato Ferraioli, Paul W. Goldberg, Carmine Ventre

Proceedings of the Algorithmic Game Theory - 5th International Symposium, 2012

Approximate Well-Supported Nash Equilibria Below Two-Thirds.

John Fearnley, Paul W. Goldberg, Rahul Savani, Troels Bjerre Sørensen

Proceedings of the Algorithmic Game Theory - 5th International Symposium, 2012

Revenue Maximization in a Bayesian Double Auction Market.

Xiaotie Deng, Paul W. Goldberg, Bo Tang, Jinshan Zhang

Proceedings of the Algorithms and Computation - 23rd International Symposium, 2012

2011

A Survey of PPAD-Completeness for Computing Nash Equilibria

Paul W. Goldberg

CoRR, 2011

The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions.

Paul W. Goldberg, Christos H. Papadimitriou, Rahul Savani

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

On the Approximation Performance of Fictitious Play in Finite Games.

Paul W. Goldberg, Rahul Savani, Troels Bjerre Sørensen, Carmine Ventre

Proceedings of the Algorithms - ESA 2011, 2011

2010

Ranking games that have competitiveness-based strategies.

Leslie Ann Goldberg, Paul W. Goldberg, Piotr Krysta, Carmine Ventre

Proceedings of the Proceedings 11th ACM Conference on Electronic Commerce (EC-2010), 2010

How Do You Like Your Equilibrium Selection Problems? Hard, or Very Hard?

Paul W. Goldberg

Proceedings of the Algorithmic Game Theory - Third International Symposium, 2010

2009

Editorial: Math. Log. Quart. 4/2009.

Paul W. Goldberg, Jörg Rothe

Math. Log. Q., 2009

On the computational complexity of weighted voting games.

Edith Elkind, Leslie Ann Goldberg, Paul W. Goldberg, Michael J. Wooldridge

Ann. Math. Artif. Intell., 2009

2008

Approximate Equilibria in Games with Few Players

Patrick Briest, Paul W. Goldberg, Heiko Röglin

CoRR, 2008

Uncoordinated two-sided matching markets.

Heiner Ackermann, Paul W. Goldberg, Vahab S. Mirrokni, Heiko Röglin, Berthold Vöcking

Proceedings of the Proceedings 9th ACM Conference on Electronic Commerce (EC-2008), 2008

A tractable and expressive class of marginal contribution nets and its applications.

Edith Elkind, Leslie Ann Goldberg, Paul W. Goldberg, Michael J. Wooldridge

Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2008), 2008

On the Dimensionality of Voting Games.

Edith Elkind, Leslie Ann Goldberg, Paul W. Goldberg, Michael J. Wooldridge

Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, 2008

2007

The Price of Selfish Stackelberg Leadership in a Network Game

Paul W. Goldberg, Pattarawit Polpinit

CoRR, 2007

A Unified Approach to Congestion Games and Two-Sided Markets.

Heiner Ackermann, Paul W. Goldberg, Vahab S. Mirrokni, Heiko Röglin, Berthold Vöcking

Proceedings of the Internet and Network Economics, Third International Workshop, 2007

Frugality ratios and improved truthful mechanisms for vertex cover.

Edith Elkind, Leslie Ann Goldberg, Paul W. Goldberg

Proceedings of the Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), 2007

Computing good nash equilibria in graphical games.

Edith Elkind, Leslie Ann Goldberg, Paul W. Goldberg

Proceedings of the Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), 2007

Computational Complexity of Weighted Threshold Games.

Edith Elkind, Leslie Ann Goldberg, Paul W. Goldberg, Michael J. Wooldridge

Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, 2007

2006

A Bound on the Precision Required to Estimate a Boolean Perceptron from Its Average Satisfying Assignment.

Paul W. Goldberg

SIAM J. Discret. Math., 2006

Some Discriminant-Based PAC Algorithms.

Paul W. Goldberg

J. Mach. Learn. Res., 2006

Utilitarian resource assignment.

Petra Berenbrink, Leslie Ann Goldberg, Paul W. Goldberg, Russell A. Martin

J. Discrete Algorithms, 2006

PAC Classification based on PAC Estimates of Label Class Distributions

Nick Palmer, Paul W. Goldberg

CoRR, 2006

Reducibility among equilibrium problems.

Paul W. Goldberg, Christos H. Papadimitriou

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

The complexity of computing a Nash equilibrium.

Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Distributed selfish load balancing.

Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg, Paul W. Goldberg, Zengjian Hu, Russell A. Martin

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Nash equilibria in graphical games on trees revisited.

Edith Elkind, Leslie Ann Goldberg, Paul W. Goldberg

Proceedings of the Proceedings 7th ACM Conference on Electronic Commerce (EC-2006), 2006

2005

PAC-Learnability of Probabilistic Deterministic Finite State Automata in Terms of Variation Distance.

Nick Palmer, Paul W. Goldberg

Proceedings of the Algorithmic Learning Theory, 16th International Conference, 2005

2004

Identifying Uniformly Mutated Segments within Repeats.

Süleyman Cenk Sahinalp, Evan E. Eichler, Paul W. Goldberg, Petra Berenbrink, Tom Friedetzky, Funda Ergün

J. Bioinform. Comput. Biol., 2004

Bounds for the convergence rate of randomized local search in a multiplayer load-balancing game.

Paul W. Goldberg

Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, 2004

2003

A proportionate fair scheduling rule with good worst-case performance.

Micah Adler, Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg, Paul W. Goldberg, Mike Paterson

Proceedings of the SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2003

2002

Statistical Identification of Uniformly Mutated Segments within Repeats.

Süleyman Cenk Sahinalp, Evan E. Eichler, Paul W. Goldberg, Petra Berenbrink, Tom Friedetzky, Funda Ergün

Proceedings of the Combinatorial Pattern Matching, 13th Annual Symposium, 2002

2001

When Can Two Unsupervised Learners Achieve PAC Separation?

Paul W. Goldberg

Proceedings of the Computational Learning Theory, 2001

Estimating a Boolean Perceptron from Its Average Satisfying Assignment: A Bound on the Precision Required.

Paul W. Goldberg

Proceedings of the Computational Learning Theory, 2001

2000

The Precision of Query Points as a Resource for Learning Convex Polytopes with Membership Queries.

Paul W. Goldberg, Stephen Kwek

Proceedings of the Thirteenth Annual Conference on Computational Learning Theory (COLT 2000), June 28, 2000

1999

The Complexity of Gene Placement.

Leslie Ann Goldberg, Paul W. Goldberg, Mike Paterson, Pavel A. Pevzner, Süleyman Cenk Sahinalp, Elizabeth Sweedyk

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Learning Fixed-Dimension Linear Thresholds from Fragmented Data.

Paul W. Goldberg

Proceedings of the Twelfth Annual Conference on Computational Learning Theory, 1999

1998

Exact Learning of Discretized Geometric Concepts.

Nader H. Bshouty, Paul W. Goldberg, Sally A. Goldman, H. David Mathias

SIAM J. Comput., 1998

Evolutionary Trees can be Learned in Polynomial Time in the Two-State General Markov Model.

Mary Cryan, Leslie Ann Goldberg, Paul W. Goldberg

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997

Regression with Input-dependent Noise: A Gaussian Process Treatment.

Paul W. Goldberg, Christopher K. I. Williams, Christopher M. Bishop

Proceedings of the Advances in Neural Information Processing Systems 10, 1997

1996

PAC Learning of One-Dimensional Patterns.

Paul W. Goldberg, Sally A. Goldman, Stephen D. Scott

Mach. Learn., 1996

Constructing Computer Virus Phylogenies.

Leslie Ann Goldberg, Paul W. Goldberg, Cynthia A. Phillips, Gregory B. Sorkin

Proceedings of the Combinatorial Pattern Matching, 7th Annual Symposium, 1996

1995

Four Strikes Against Physical Mapping of DNA.

Paul W. Goldberg, Martin Charles Golumbic, Haim Kaplan, Ron Shamir

J. Comput. Biol., 1995

Minimizing Phylogenetic Number to find Good Evolutionary Trees.

Leslie Ann Goldberg, Paul W. Goldberg, Cynthia A. Phillips, Elizabeth Sweedyk, Tandy J. Warnow

Proceedings of the Combinatorial Pattern Matching, 6th Annual Symposium, 1995

1994

Learning Unions of Boxes with Membership and Equivalence Queries.

Paul W. Goldberg, Sally A. Goldman, H. David Mathias

Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994

Learning One-Dimensional Geometric Patterns Under One-Sided Random Misclassification Noise.

Paul W. Goldberg, Sally A. Goldman

Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994

1993

Bounding the Vapnik-Chervonenkis Dimension of Concept Classes Parameterized by Real Numbers.

Paul Goldberg, Mark Jerrum

Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, 1993