Paul W. Goldberg

According to our database, Paul W. Goldberg authored at least 103 papers between 1994 and 2024.

Collaborative distances:

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

2024

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

Edith Elkind, Abheek Ghosh, Paul W. Goldberg

CoRR, 2024

2023

PPAD-complete approximate pure Nash equilibria in Lipschitz games.

Paul W. Goldberg, Matthew J. Katzman

Theor. Comput. Sci., November, 2023

Lower bounds for the query complexity of equilibria in Lipschitz games.

Paul W. Goldberg, Matthew J. Katzman

Theor. Comput. Sci., June, 2023

The Complexity of Gradient Descent: CLS = PPAD ∩ PLS.

John Fearnley, Paul Goldberg, Alexandros Hollender, Rahul Savani

J. ACM, February, 2023

The Complexity of Computing KKT Solutions of Quadratic Programs.

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

CoRR, 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

Consensus Halving for Sets of Items.

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

Math. Oper. Res., November, 2022

Learning Strong Substitutes Demand via Queries.

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

ACM Trans. Economics and Comput., 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

Learning Convex Partitions and Computing Game-theoretic Equilibria from Best-response Queries.

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

ACM Trans. Economics and Comput., 2021

The Hairy Ball problem is PPAD-complete.

Paul W. Goldberg, Alexandros Hollender

J. Comput. Syst. Sci., 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

2020

Approximately Efficient Two-Sided Combinatorial Auctions.

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

ACM Trans. Economics and Comput., 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

Contiguous Cake Cutting: Hardness Results and Approximation Algorithms.

Paul W. Goldberg, Alexandros Hollender, Warut Suksompong

J. Artif. Intell. Res., 2020

2019

Logarithmic Query Complexity for Approximate Nash Computation in Large Games.

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

Theory Comput. Syst., 2019

Solving Strong-Substitutes Product-Mix Auctions.

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

CoRR, 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

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

Towards a unified complexity theory of total functions.

Paul W. Goldberg, Christos H. Papadimitriou

J. Comput. Syst. Sci., 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

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

2017

Query complexity of approximate equilibria in anonymous games.

Paul W. Goldberg, Stefano Turchetta

J. Comput. Syst. Sci., 2017

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

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

Dagstuhl Reports, 2017

Pricing ad slots with consecutive multi-unit demand.

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

Auton. Agents Multi Agent Syst., 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

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

Bounds for the Query Complexity of Approximate Equilibria.

Paul W. Goldberg, Aaron Roth

ACM Trans. Economics and Comput., 2016

Decentralized dynamics for finite opinion games.

Diodato Ferraioli, Paul W. Goldberg, Carmine Ventre

Theor. Comput. Sci., 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

Approximate Well-supported Nash Equilibria Below Two-thirds.

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

Algorithmica, 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

Learning equilibria of games via payoff queries.

John Fearnley, Martin Gairing, Paul W. Goldberg, Rahul Savani

J. Mach. Learn. Res., 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

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

Revenue maximization in a Bayesian double auction market.

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

Theor. Comput. Sci., 2014

On the communication complexity of approximate Nash equilibria.

Paul W. Goldberg, Arnoud Pastink

Games Econ. Behav., 2014

2013

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

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

ACM Trans. Economics and Comput., 2013

Ranking games that have competitiveness-based strategies.

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

Theor. Comput. Sci., 2013

On the approximation performance of fictitious play in finite games.

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

Int. J. Game Theory, 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

Commodity Auctions and Frugality Ratios.

Paul W. Goldberg, Antony McCabe

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

2011

A Survey of PPAD-Completeness for Computing Nash Equilibria

Paul W. Goldberg

CoRR, 2011

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

Uncoordinated two-sided matching markets.

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

SIGecom Exch., 2009

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

Paul W. Goldberg, Jörg Rothe

Math. Log. Q., 2009

A Tractable and Expressive Class of Marginal Contribution Nets and Its Applications.

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

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

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

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

Internet Math., 2008

Approximate Equilibria in Games with Few Players

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

CoRR, 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

PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance.

Nick Palmer, Paul W. Goldberg

Theor. Comput. Sci., 2007

Distributed Selfish Load Balancing.

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

SIAM J. Comput., 2007

The Price of Selfish Stackelberg Leadership in a Network Game

Paul W. Goldberg, Pattarawit Polpinit

CoRR, 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

Nash Equilibria in Graphical Games on Trees Revisited

Edith Elkind, Leslie Ann Goldberg, Paul W. Goldberg

Electron. Colloquium Comput. Complex., 2006

PAC Classification based on PAC Estimates of Label Class Distributions

Nick Palmer, Paul W. Goldberg

CoRR, 2006

2005

The complexity of computing a Nash equilibrium

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

Electron. Colloquium Comput. Complex., 2005

Reducibility Among Equilibrium Problems

Paul W. Goldberg, Christos H. Papadimitriou

Electron. Colloquium Comput. Complex., 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

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

Mary Cryan, Leslie Ann Goldberg, Paul W. Goldberg

SIAM J. Comput., 2001

The Complexity of Gene Placement.

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

J. Algorithms, 2001

Learning Fixed-Dimension Linear Thresholds from Fragmented Data.

Paul W. Goldberg

Inf. Comput., 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

1998

Exact Learning of Discretized Geometric Concepts.

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

SIAM J. Comput., 1998

Constructing Computer Virus Phylogenies.

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

J. Algorithms, 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

Minimizing Phylogenetic Number To Find Good Evolutionary Trees.

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

Discret. Appl. Math., 1996

1995

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

Paul W. Goldberg, Mark Jerrum

Mach. Learn., 1995

Four Strikes Against Physical Mapping of DNA.

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

J. Comput. Biol., 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