Paul W. Goldberg

Orcid: 0000-0002-5436-7890

Affiliations:
  • University of Oxford, Department of Computer Science, UK
  • University of Liverpool, Department of Computer Science, UK (former)


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

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Solving Strong-Substitutes Product-Mix Auctions.
Math. Oper. Res., 2024

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

The Complexity of Computing KKT Solutions of Quadratic Programs.
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Imperfect-Recall Games: Equilibrium Concepts and Their Complexity.
Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, 2024

2023
PPAD-complete approximate pure Nash equilibria in Lipschitz games.
Theor. Comput. Sci., November, 2023

Lower bounds for the query complexity of equilibria in Lipschitz games.
Theor. Comput. Sci., June, 2023

The Complexity of Gradient Descent: CLS = PPAD ∩ PLS.
J. ACM, February, 2023

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

Best-Response Dynamics in Lottery Contests.
Proceedings of the 24th ACM Conference on Economics and Computation, 2023

The Frontier of Intractability for EFX with Two Agents.
Proceedings of the Algorithmic Game Theory - 16th International Symposium, 2023

Consensus Division in an Arbitrary Ratio.
Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

The Computational Complexity of Single-Player Imperfect-Recall Games.
Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, 2023

2022
Consensus Halving for Sets of Items.
Math. Oper. Res., November, 2022

Learning Strong Substitutes Demand via Queries.
ACM Trans. Economics and Comput., 2022

PPAD-Complete Pure Approximate Nash Equilibria in Lipschitz Games.
Proceedings of the Algorithmic Game Theory - 15th International Symposium, 2022

Simultaneous Contests with Equal Sharing Allocation of Prizes: Computational Complexity and Price of Anarchy.
Proceedings of the Algorithmic Game Theory - 15th International Symposium, 2022

Contests to Incentivize a Target Group.
Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, 2022

Complexity of Deliberative Coalition Formation.
Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, 2022

2021
Learning Convex Partitions and Computing Game-theoretic Equilibria from Best-response Queries.
ACM Trans. Economics and Comput., 2021

The Hairy Ball problem is PPAD-complete.
J. Comput. Syst. Sci., 2021

Equivalence of Models of Cake-Cutting Protocols.
CoRR, 2021

Contest Design with Threshold Objectives.
Proceedings of the Web and Internet Economics - 17th International Conference, 2021

2020
Approximately Efficient Two-Sided Combinatorial Auctions.
ACM Trans. Economics and Comput., 2020

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

Contiguous Cake Cutting: Hardness Results and Approximation Algorithms.
J. Artif. Intell. Res., 2020

2019
Logarithmic Query Complexity for Approximate Nash Computation in Large Games.
Theory Comput. Syst., 2019

The complexity of splitting necklaces and bisecting ham sandwiches.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Multi-Unit Bilateral Trade.
Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, 2019

2018
Towards a unified complexity theory of total functions.
J. Comput. Syst. Sci., 2018

The Complexity of Multi-source Variants of the End-of-Line Problem, and the Concise Mutilated Chessboard.
Electron. Colloquium Comput. Complex., 2018

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

Consensus halving is PPA-complete.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Hardness Results for Consensus-Halving.
Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

2017
Query complexity of approximate equilibria in anonymous games.
J. Comput. Syst. Sci., 2017

Game Theory Meets Computational Learning Theory (Dagstuhl Seminar 17251).
Dagstuhl Reports, 2017

Pricing ad slots with consecutive multi-unit demand.
Auton. Agents Multi Agent Syst., 2017

Fixed Price Approximability of the Optimal Gain from Trade.
Proceedings of the Web and Internet Economics - 13th International Conference, 2017

TFNP: An Update.
Proceedings of the Algorithms and Complexity - 10th International Conference, 2017

Equilibria in Sequential Allocation.
Proceedings of the Algorithmic Decision Theory - 5th International Conference, 2017

2016
Decentralized dynamics for finite opinion games.
Theor. Comput. Sci., 2016

On revenue maximization with sharp multi-unit demands.
J. Comb. Optim., 2016

EATCS Fellows 2017 - Call for Nominations.
Bull. EATCS, 2016

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

Multi-Unit Bayesian Auction with Demand or Budget Constraints.
Comput. Intell., 2016

Approximate Well-supported Nash Equilibria Below Two-thirds.
Algorithmica, 2016

Revenue Maximization for Market Intermediation with Correlated Priors.
Proceedings of the Algorithmic Game Theory - 9th International Symposium, 2016

Preference Elicitation in Matching Markets via Interviews: A Study of Offline Benchmarks (Extended Abstract).
Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, 2016

Social Welfare in One-Sided Matching Mechanisms.
Proceedings of the Autonomous Agents and Multiagent Systems - AAMAS 2016 Workshops, - Best Papers, 2016

Social Welfare in One-Sided Matching Mechanisms: (Extended Abstract).
Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, 2016

2015
Learning equilibria of games via payoff queries.
J. Mach. Learn. Res., 2015

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

Welfare Ratios in One-Sided Matching Mechanisms.
CoRR, 2015

Algorithmic Game Theory (Tutorial).
Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

Auction Design with a Revenue Target.
Proceedings of the Algorithmic Game Theory - 8th International Symposium, 2015

2014
Revenue maximization in a Bayesian double auction market.
Theor. Comput. Sci., 2014

On the communication complexity of approximate Nash equilibria.
Games Econ. Behav., 2014

2013
The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions.
ACM Trans. Economics and Comput., 2013

Ranking games that have competitiveness-based strategies.
Theor. Comput. Sci., 2013

On the approximation performance of fictitious play in finite games.
Int. J. Game Theory, 2013

Bounds for the Query Complexity of Approximate Equilibria.
Electron. Colloquium Comput. Complex., 2013

Shortest Paths with Bundles and Non-additive Weights Is Hard.
Proceedings of the Algorithms and Complexity, 8th International Conference, 2013

Using lotteries to approximate the optimal revenue.
Proceedings of the International conference on Autonomous Agents and Multi-Agent Systems, 2013

2012
Commodity Auctions and Frugality Ratios.
Proceedings of the Algorithmic Game Theory - 5th International Symposium, 2012

2011
Uncoordinated Two-Sided Matching Markets.
SIAM J. Comput., 2011

A Survey of PPAD-Completeness for Computing Nash Equilibria
CoRR, 2011

2010
How Do You Like Your Equilibrium Selection Problems? Hard, or Very Hard?
Proceedings of the Algorithmic Game Theory - Third International Symposium, 2010

2009
The Complexity of Computing a Nash Equilibrium.
SIAM J. Comput., 2009

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

A Tractable and Expressive Class of Marginal Contribution Nets and Its Applications.
Math. Log. Q., 2009

On the computational complexity of weighted voting games.
Ann. Math. Artif. Intell., 2009

2008
A Unified Approach to Congestion Games and Two-Sided Markets.
Internet Math., 2008

Approximate Equilibria in Games with Few Players
CoRR, 2008

On the Dimensionality of Voting Games.
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.
Theor. Comput. Sci., 2007

Distributed Selfish Load Balancing.
SIAM J. Comput., 2007

The Price of Selfish Stackelberg Leadership in a Network Game
CoRR, 2007

Frugality ratios and improved truthful mechanisms for vertex cover.
Proceedings of the Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), 2007

Computing good nash equilibria in graphical games.
Proceedings of the Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), 2007

Computational Complexity of Weighted Threshold Games.
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.
SIAM J. Discret. Math., 2006

Some Discriminant-Based PAC Algorithms.
J. Mach. Learn. Res., 2006

Utilitarian resource assignment.
J. Discrete Algorithms, 2006

Nash Equilibria in Graphical Games on Trees Revisited
Electron. Colloquium Comput. Complex., 2006

PAC Classification based on PAC Estimates of Label Class Distributions
CoRR, 2006

2005
Reducibility Among Equilibrium Problems
Electron. Colloquium Comput. Complex., 2005

2004
Identifying Uniformly Mutated Segments within Repeats.
J. Bioinform. Comput. Biol., 2004

Bounds for the convergence rate of randomized local search in a multiplayer load-balancing game.
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.
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.
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.
SIAM J. Comput., 2001

The Complexity of Gene Placement.
J. Algorithms, 2001

Learning Fixed-Dimension Linear Thresholds from Fragmented Data.
Inf. Comput., 2001

When Can Two Unsupervised Learners Achieve PAC Separation?
Proceedings of the Computational Learning Theory, 2001

Estimating a Boolean Perceptron from Its Average Satisfying Assignment: A Bound on the Precision Required.
Proceedings of the Computational Learning Theory, 2001

2000
The Precision of Query Points as a Resource for Learning Convex Polytopes with Membership Queries.
Proceedings of the Thirteenth Annual Conference on Computational Learning Theory (COLT 2000), June 28, 2000

1998
Exact Learning of Discretized Geometric Concepts.
SIAM J. Comput., 1998

Constructing Computer Virus Phylogenies.
J. Algorithms, 1998

1997
Regression with Input-dependent Noise: A Gaussian Process Treatment.
Proceedings of the Advances in Neural Information Processing Systems 10, 1997

1996
PAC Learning of One-Dimensional Patterns.
Mach. Learn., 1996

Minimizing Phylogenetic Number To Find Good Evolutionary Trees.
Discret. Appl. Math., 1996

1995
Bounding the Vapnik-Chervonenkis Dimension of Concept Classes Parameterized by Real Numbers.
Mach. Learn., 1995

Four Strikes Against Physical Mapping of DNA.
J. Comput. Biol., 1995

1994
Learning Unions of Boxes with Membership and Equivalence Queries.
Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994

Learning One-Dimensional Geometric Patterns Under One-Sided Random Misclassification Noise.
Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994


  Loading...