Paul W. Goldberg

According to our database1, Paul W. Goldberg authored at least 75 papers between 1993 and 2019.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

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

2018
The Complexity of Multi-source Variants of the End-of-Line Problem, and the Concise Mutilated Chessboard.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Learning Convex Partitions and Computing Game-Theoretic Equilibria from Best Response Queries.
Proceedings of the Web and Internet Economics - 14th International Conference, 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

Towards a Unified Complexity Theory of Total Functions.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

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

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

Approximately Efficient Two-Sided Combinatorial Auctions.
Proceedings of the 2017 ACM Conference on Economics and Computation, 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
On revenue maximization with sharp multi-unit demands.
J. Comb. Optim., 2016

EATCS Fellows 2017 - Call for Nominations.
Bulletin of the EATCS, 2016

Multi-Unit Bayesian Auction with Demand or Budget Constraints.
Computational Intelligence, 2016

Logarithmic Query Complexity for Approximate Nash Computation in Large Games.
Proceedings of the Algorithmic Game Theory - 9th International Symposium, 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
Query Complexity of Approximate Equilibria in Anonymous Games.
Proceedings of the Web and Internet Economics - 11th International Conference, 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
Bounds for the query complexity of approximate equilibria.
Proceedings of the ACM Conference on Economics and Computation, 2014

2013
Learning equilibria of games via payoff queries.
Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013

Pricing Ad Slots with Consecutive Multi-unit Demand.
Proceedings of the Algorithmic Game Theory - 6th International Symposium, 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
On the Communication Complexity of Approximate Nash Equilibria.
Proceedings of the Algorithmic Game Theory - 5th International Symposium, 2012

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

Decentralized Dynamics for Finite Opinion Games.
Proceedings of the Algorithmic Game Theory - 5th International Symposium, 2012

Approximate Well-Supported Nash Equilibria Below Two-Thirds.
Proceedings of the Algorithmic Game Theory - 5th International Symposium, 2012

Revenue Maximization in a Bayesian Double Auction Market.
Proceedings of the Algorithms and Computation - 23rd International Symposium, 2012

2011
The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

On the Approximation Performance of Fictitious Play in Finite Games.
Proceedings of the Algorithms - ESA 2011, 2011

2010
Ranking games that have competitiveness-based strategies.
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?
Proceedings of the Algorithmic Game Theory - Third International Symposium, 2010

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

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

2008
Uncoordinated two-sided matching markets.
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.
Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2008), 2008

On the Dimensionality of Voting Games.
Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, 2008

2007
A Unified Approach to Congestion Games and Two-Sided Markets.
Proceedings of the Internet and Network Economics, Third International Workshop, 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. Discrete Math., 2006

Some Discriminant-Based PAC Algorithms.
Journal of Machine Learning Research, 2006

Utilitarian resource assignment.
J. Discrete Algorithms, 2006

Nash Equilibria in Graphical Games on Trees Revisited
Electronic Colloquium on Computational Complexity (ECCC), 2006

Reducibility among equilibrium problems.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

The complexity of computing a Nash equilibrium.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Distributed selfish load balancing.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Nash equilibria in graphical games on trees revisited.
Proceedings of the Proceedings 7th ACM Conference on Electronic Commerce (EC-2006), 2006

2005
The complexity of computing a Nash equilibrium
Electronic Colloquium on Computational Complexity (ECCC), 2005

Reducibility Among Equilibrium Problems
Electronic Colloquium on Computational Complexity (ECCC), 2005

PAC-Learnability of Probabilistic Deterministic Finite State Automata in Terms of Variation Distance.
Proceedings of the Algorithmic Learning Theory, 16th International Conference, 2005

2004
Identifying Uniformly Mutated Segments within Repeats.
J. Bioinformatics and Computational Biology, 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
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

1999
The Complexity of Gene Placement.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Learning Fixed-Dimension Linear Thresholds from Fragmented Data.
Proceedings of the Twelfth Annual Conference on Computational Learning Theory, 1999

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

Evolutionary Trees can be Learned in Polynomial Time in the Two-State General Markov Model.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 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.
Machine Learning, 1996

Constructing Computer Virus Phylogenies.
Proceedings of the Combinatorial Pattern Matching, 7th Annual Symposium, 1996

1995
Four Strikes Against Physical Mapping of DNA.
Journal of Computational Biology, 1995

Minimizing Phylogenetic Number to find Good Evolutionary Trees.
CPM, 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

1993
Bounding the Vapnik-Chervonenkis Dimension of Concept Classes Parameterized by Real Numbers.
Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, 1993


  Loading...