×

zbMATH — the first resource for mathematics

Goldberg, Paul W.

Compute Distance To:
Author ID: goldberg.paul-w Recent zbMATH articles by "Goldberg, Paul W."
Published as: Goldberg, Paul; Goldberg, Paul W.
External Links: MGP · Wikidata
Documents Indexed: 61 Publications since 1995, including 1 Book

Publications by Year

Citations contained in zbMATH

43 Publications have been cited 388 times in 318 Documents Cited by Year
The complexity of computing a Nash equilibrium. Zbl 1185.91019
Daskalakis, Constantinos; Goldberg, Paul W.; Papadimitriou, Christos H.
95
2009
The complexity of computing a Nash equilibrium. Zbl 1301.68142
Daskalakis, Constantinos; Goldberg, Paul W.; Papadimitriou, Christos H.
64
2006
On the computational complexity of weighted voting games. Zbl 1185.91081
Elkind, Edith; Goldberg, Leslie Ann; Goldberg, Paul W.; Wooldridge, Michael
30
2009
Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers. Zbl 0831.68087
Goldberg, Paul W.; Jerrum, Mark R.
23
1995
Reducibility among equilibrium problems. Zbl 1301.68161
Goldberg, Paul W.; Papadimitriou, Christos H.
16
2006
Uncoordinated two-sided matching markets. Zbl 1216.68200
Ackermann, Heiner; Goldberg, Paul W.; Mirrokni, Vahab S.; Röglin, Heiko; Vöcking, Berthold
13
2011
Learning equilibria of games via payoff queries. Zbl 1351.91008
Fearnley, John; Gairing, Martin; Goldberg, Paul W.; Savani, Rahul
11
2015
Approximate well-supported Nash equilibria below two-thirds. Zbl 1284.91018
Fearnley, John; Goldberg, Paul W.; Savani, Rahul; Sørensen, Troels Bjerre
11
2012
Evolutionary trees can be learned in polynomial time in the two-state general Markov model. Zbl 1052.68061
Cryan, Mary; Goldberg, Leslie Ann; Goldberg, Paul W.
11
2001
A tractable and expressive class of marginal contribution nets and its applications. Zbl 1175.91022
Elkind, Edith; Goldberg, Leslie Ann; Goldberg, Paul W.; Wooldridge, Michael
10
2009
Bounds for the convergence rate of randomized local search in a multiplayer load-balancing game. Zbl 1321.68082
Goldberg, Paul W.
8
2004
Exact learning of discretized geometric concepts. Zbl 0915.68087
Bshouty, Nader H.; Goldberg, Paul W.; Goldman, Sally A.; Mathias, H. David
8
1998
Utilitarian resource assignment. Zbl 1124.91042
Berenbrink, Petra; Goldberg, Leslie Ann; Goldberg, Paul W.; Martin, Russell
7
2006
Distributed selfish load balancing. Zbl 1141.68018
Berenbrink, Petra; Friedetzky, Tom; Goldberg, Leslie Ann; Goldberg, Paul W.; Hu, Zengjian; Martin, Russell
6
2007
Minimizing phylogenetic number to find good evolutionary trees. Zbl 0880.92030
Goldberg, Leslie Ann; Goldberg, Paul W.; Phillips, Cynthia A.; Sweedyk, Elizabeth; Warnow, Tandy
6
1996
Decentralized dynamics for finite opinion games. Zbl 1414.91072
Ferraioli, Diodato; Goldberg, Paul W.; Ventre, Carmine
5
2016
Distributed selfish load balancing. Zbl 1192.68094
Berenbrink, Petra; Friedetzky, Tom; Goldberg, Leslie Ann; Goldberg, Paul; Hu, Zengjian; Martin, Russell
5
2006
Consensus halving is PPA-complete. Zbl 1428.68162
Filos-Ratsikas, Aris; Goldberg, Paul W.
4
2018
Decentralized dynamics for finite opinion games. Zbl 1284.91019
Ferraioli, Diodato; Goldberg, Paul W.; Ventre, Carmine
4
2012
A bound on the precision required to estimate a Boolean perceptron from its average satisfying assignment. Zbl 1115.68092
Goldberg, Paul W.
4
2006
Construction computer virus phylogenies. Zbl 0891.68045
Goldberg, Leslie Ann; Goldberg, Paul W.; Phillips, Cynthia A.; Sorkin, Gregory B.
4
1998
Towards a unified complexity theory of total functions. Zbl 1393.68053
Goldberg, Paul W.; Papadimitriou, Christos H.
3
2018
Query complexity of approximate equilibria in anonymous games. Zbl 1404.91009
Goldberg, Paul W.; Turchetta, Stefano
3
2015
On the communication complexity of approximate Nash equilibria. Zbl 1290.91017
Goldberg, Paul W.; Pastink, Arnoud
3
2014
On the approximation performance of fictitious play in finite games. Zbl 1300.91004
Goldberg, Paul W.; Savani, Rahul; Sørensen, Troels Bjerre; Ventre, Carmine
3
2013
Pricing ad slots with consecutive multi-unit demand. Zbl 1319.91080
Deng, Xiaotie; Goldberg, Paul; Sun, Yang; Tang, Bo; Zhang, Jinshan
3
2013
The complexity of the homotopy method, equilibrium selection and Lemke-Howson solutions. Zbl 1292.91013
Goldberg, Paul W.; Papadimitriou, Christos H.; Savani, Rahul
3
2011
A unified approach to congestion games and two-sided markets. Zbl 1194.91030
Ackermann, Heiner; Goldberg, Paul W.; Mirrokni, Vahab S.; Röglin, Heiko; Vöcking, Berthold
3
2008
PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance. Zbl 1143.68024
Palmer, Nick; Goldberg, Paul W.
3
2007
Some discriminant-based PAC algorithms. Zbl 1222.68097
Goldberg, Paul W.
3
2006
Contiguous cake cutting: hardness results and approximation algorithms. Zbl 07269303
Goldberg, Paul W.; Hollender, Alexandros; Suksompong, Warut
2
2020
On revenue maximization with sharp multi-unit demands. Zbl 1341.91101
Chen, Ning; Deng, Xiaotie; Goldberg, Paul W.; Zhang, Jinshan
2
2016
PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance. Zbl 1143.68421
Palmer, Nick; Goldberg, Paul W.
2
2005
The complexity of splitting necklaces and bisecting ham sandwiches. Zbl 1433.68157
Filos-Ratsikas, Aris; Goldberg, Paul W.
1
2019
Query complexity of approximate equilibria in anonymous games. Zbl 1376.91018
Goldberg, Paul W.; Turchetta, Stefano
1
2017
TFNP: an update. Zbl 06751046
Goldberg, Paul W.; Papadimitriou, Christos H.
1
2017
Approximate well-supported Nash equilibria below two-thirds. Zbl 1347.91008
Fearnley, John; Goldberg, Paul W.; Savani, Rahul; Sørensen, Troels Bjerre
1
2016
Logarithmic query complexity for approximate Nash computation in large games. Zbl 1403.91032
Goldberg, Paul W.; Marmolejo Cossío, Francisco J.; Wu, Zhiwei Steven
1
2016
Revenue maximization in a Bayesian double auction market. Zbl 1360.91093
Deng, Xiaotie; Goldberg, Paul; Tang, Bo; Zhang, Jinshan
1
2014
Shortest paths with bundles and non-additive weights is hard. Zbl 1382.68091
Goldberg, Paul W.; McCabe, Antony
1
2013
On the communication complexity of approximate Nash equilibria. Zbl 1284.91021
Goldberg, Paul W.; Pastink, Arnoud
1
2012
A survey of PPAD-completeness for computing Nash equilibria. Zbl 1223.91017
Goldberg, Paul W.
1
2011
When can two unsupervised learners achieve PAC separation? Zbl 0992.68112
Goldberg, Paul W.
1
2001
Contiguous cake cutting: hardness results and approximation algorithms. Zbl 07269303
Goldberg, Paul W.; Hollender, Alexandros; Suksompong, Warut
2
2020
The complexity of splitting necklaces and bisecting ham sandwiches. Zbl 1433.68157
Filos-Ratsikas, Aris; Goldberg, Paul W.
1
2019
Consensus halving is PPA-complete. Zbl 1428.68162
Filos-Ratsikas, Aris; Goldberg, Paul W.
4
2018
Towards a unified complexity theory of total functions. Zbl 1393.68053
Goldberg, Paul W.; Papadimitriou, Christos H.
3
2018
Query complexity of approximate equilibria in anonymous games. Zbl 1376.91018
Goldberg, Paul W.; Turchetta, Stefano
1
2017
TFNP: an update. Zbl 06751046
Goldberg, Paul W.; Papadimitriou, Christos H.
1
2017
Decentralized dynamics for finite opinion games. Zbl 1414.91072
Ferraioli, Diodato; Goldberg, Paul W.; Ventre, Carmine
5
2016
On revenue maximization with sharp multi-unit demands. Zbl 1341.91101
Chen, Ning; Deng, Xiaotie; Goldberg, Paul W.; Zhang, Jinshan
2
2016
Approximate well-supported Nash equilibria below two-thirds. Zbl 1347.91008
Fearnley, John; Goldberg, Paul W.; Savani, Rahul; Sørensen, Troels Bjerre
1
2016
Logarithmic query complexity for approximate Nash computation in large games. Zbl 1403.91032
Goldberg, Paul W.; Marmolejo Cossío, Francisco J.; Wu, Zhiwei Steven
1
2016
Learning equilibria of games via payoff queries. Zbl 1351.91008
Fearnley, John; Gairing, Martin; Goldberg, Paul W.; Savani, Rahul
11
2015
Query complexity of approximate equilibria in anonymous games. Zbl 1404.91009
Goldberg, Paul W.; Turchetta, Stefano
3
2015
On the communication complexity of approximate Nash equilibria. Zbl 1290.91017
Goldberg, Paul W.; Pastink, Arnoud
3
2014
Revenue maximization in a Bayesian double auction market. Zbl 1360.91093
Deng, Xiaotie; Goldberg, Paul; Tang, Bo; Zhang, Jinshan
1
2014
On the approximation performance of fictitious play in finite games. Zbl 1300.91004
Goldberg, Paul W.; Savani, Rahul; Sørensen, Troels Bjerre; Ventre, Carmine
3
2013
Pricing ad slots with consecutive multi-unit demand. Zbl 1319.91080
Deng, Xiaotie; Goldberg, Paul; Sun, Yang; Tang, Bo; Zhang, Jinshan
3
2013
Shortest paths with bundles and non-additive weights is hard. Zbl 1382.68091
Goldberg, Paul W.; McCabe, Antony
1
2013
Approximate well-supported Nash equilibria below two-thirds. Zbl 1284.91018
Fearnley, John; Goldberg, Paul W.; Savani, Rahul; Sørensen, Troels Bjerre
11
2012
Decentralized dynamics for finite opinion games. Zbl 1284.91019
Ferraioli, Diodato; Goldberg, Paul W.; Ventre, Carmine
4
2012
On the communication complexity of approximate Nash equilibria. Zbl 1284.91021
Goldberg, Paul W.; Pastink, Arnoud
1
2012
Uncoordinated two-sided matching markets. Zbl 1216.68200
Ackermann, Heiner; Goldberg, Paul W.; Mirrokni, Vahab S.; Röglin, Heiko; Vöcking, Berthold
13
2011
The complexity of the homotopy method, equilibrium selection and Lemke-Howson solutions. Zbl 1292.91013
Goldberg, Paul W.; Papadimitriou, Christos H.; Savani, Rahul
3
2011
A survey of PPAD-completeness for computing Nash equilibria. Zbl 1223.91017
Goldberg, Paul W.
1
2011
The complexity of computing a Nash equilibrium. Zbl 1185.91019
Daskalakis, Constantinos; Goldberg, Paul W.; Papadimitriou, Christos H.
95
2009
On the computational complexity of weighted voting games. Zbl 1185.91081
Elkind, Edith; Goldberg, Leslie Ann; Goldberg, Paul W.; Wooldridge, Michael
30
2009
A tractable and expressive class of marginal contribution nets and its applications. Zbl 1175.91022
Elkind, Edith; Goldberg, Leslie Ann; Goldberg, Paul W.; Wooldridge, Michael
10
2009
A unified approach to congestion games and two-sided markets. Zbl 1194.91030
Ackermann, Heiner; Goldberg, Paul W.; Mirrokni, Vahab S.; Röglin, Heiko; Vöcking, Berthold
3
2008
Distributed selfish load balancing. Zbl 1141.68018
Berenbrink, Petra; Friedetzky, Tom; Goldberg, Leslie Ann; Goldberg, Paul W.; Hu, Zengjian; Martin, Russell
6
2007
PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance. Zbl 1143.68024
Palmer, Nick; Goldberg, Paul W.
3
2007
The complexity of computing a Nash equilibrium. Zbl 1301.68142
Daskalakis, Constantinos; Goldberg, Paul W.; Papadimitriou, Christos H.
64
2006
Reducibility among equilibrium problems. Zbl 1301.68161
Goldberg, Paul W.; Papadimitriou, Christos H.
16
2006
Utilitarian resource assignment. Zbl 1124.91042
Berenbrink, Petra; Goldberg, Leslie Ann; Goldberg, Paul W.; Martin, Russell
7
2006
Distributed selfish load balancing. Zbl 1192.68094
Berenbrink, Petra; Friedetzky, Tom; Goldberg, Leslie Ann; Goldberg, Paul; Hu, Zengjian; Martin, Russell
5
2006
A bound on the precision required to estimate a Boolean perceptron from its average satisfying assignment. Zbl 1115.68092
Goldberg, Paul W.
4
2006
Some discriminant-based PAC algorithms. Zbl 1222.68097
Goldberg, Paul W.
3
2006
PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance. Zbl 1143.68421
Palmer, Nick; Goldberg, Paul W.
2
2005
Bounds for the convergence rate of randomized local search in a multiplayer load-balancing game. Zbl 1321.68082
Goldberg, Paul W.
8
2004
Evolutionary trees can be learned in polynomial time in the two-state general Markov model. Zbl 1052.68061
Cryan, Mary; Goldberg, Leslie Ann; Goldberg, Paul W.
11
2001
When can two unsupervised learners achieve PAC separation? Zbl 0992.68112
Goldberg, Paul W.
1
2001
Exact learning of discretized geometric concepts. Zbl 0915.68087
Bshouty, Nader H.; Goldberg, Paul W.; Goldman, Sally A.; Mathias, H. David
8
1998
Construction computer virus phylogenies. Zbl 0891.68045
Goldberg, Leslie Ann; Goldberg, Paul W.; Phillips, Cynthia A.; Sorkin, Gregory B.
4
1998
Minimizing phylogenetic number to find good evolutionary trees. Zbl 0880.92030
Goldberg, Leslie Ann; Goldberg, Paul W.; Phillips, Cynthia A.; Sweedyk, Elizabeth; Warnow, Tandy
6
1996
Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers. Zbl 0831.68087
Goldberg, Paul W.; Jerrum, Mark R.
23
1995
all top 5

Cited by 549 Authors

19 Goldberg, Paul W.
10 Fearnley, John
10 Hoefer, Martin
10 Spirakis, Paul G.
9 Savani, Rahul
8 Papadimitriou, Christos Harilaos
7 Deligkas, Argyrios
7 Ferraioli, Diodato
7 Wooldridge, Michael J.
6 Bachrach, Yoram
6 Brandt, Felix
6 Deng, Xiao-Tie
6 Greco, Gianluigi
6 Mehta, Ruta
6 Serna, Maria José
5 Auletta, Vincenzo
5 Bilò, Vittorio
5 Fischer, Felix
5 Persiano, Giuseppe
5 Servedio, Rocco A.
4 Anshelevich, Elliot
4 Anthony, Martin H. G.
4 Chen, Xi
4 Conitzer, Vincent
4 Dang, Chuangyin
4 Daskalakis, Constantinos
4 Diakonikolas, Ilias
4 Fischer, Simon
4 Fotakis, Dimitris A.
4 Kontogiannis, Spyros C.
4 Molinero, Xavier
4 Pasquale, Francesco
4 Rosenschein, Jeffrey S.
4 Scarcello, Francesco
4 Ye, Yinyu
3 Berenbrink, Petra
3 Elkind, Edith
3 Harrenstein, Paul
3 Huang, Chien-Chung
3 Jiang, Albert Xin
3 Leyton-Brown, Kevin
3 Markakis, Evangelos
3 Marmolejo Cossío, Francisco J.
3 Mavronicolas, Marios
3 Monien, Burkhard
3 Moran, Shlomo
3 Ortiz, Luis E.
3 Snir, Sagi
3 Sontag, Eduardo D.
3 Sørensen, Troels Bjerre
3 Suksompong, Warut
3 Vazirani, Vijay V.
3 Ventre, Carmine
3 Wagner, Lisa Sabine
3 Wojtczak, Dominik
3 Zick, Yair
2 Ackermann, Heiner
2 Ågotnes, Thomas
2 Balle, Borja
2 Barman, Siddharth
2 Bartlett, Peter L.
2 Ben-David, Shai
2 Bi, Dianjie
2 Blum, Avrim L.
2 Bshouty, Nader H.
2 Buss, Sam
2 Castro, Jorge E.
2 Chalkiadakis, Georgios
2 Chan, Hau
2 Chen, Ning
2 Corley, H. W. jun.
2 Czumaj, Artur
2 De, Anindya K.
2 Della Vedova, Gianluca
2 Du, Ye
2 Endriss, Ulle
2 Fanelli, Angelo
2 Fasoulakis, Michail
2 Filmus, Yuval
2 Gabarró, Joaquim
2 Gairing, Martin
2 Garg, Jugal
2 Gavaldà, Ricard
2 Goldberg, Leslie Ann
2 Goldman, Sally A.
2 Hansen, Kristoffer Arnsfelt
2 Hermelin, Danny
2 Hollender, Alexandros
2 Holzer, Markus
2 Hubáček, Pavel
2 Hui, Pan
2 Jurdziński, Marcin
2 Kar, Koushik
2 Kleinberg, Jon Michael
2 Kleinberg, Robert D.
2 Koiran, Pascal
2 Komargodski, Ilan
2 Koutsoupias, Elias
2 Kratsch, Stefan
2 Kurz, Sascha
...and 449 more Authors
all top 5

Cited in 76 Serials

28 Theoretical Computer Science
20 Journal of Computer and System Sciences
17 Theory of Computing Systems
15 Algorithmica
15 Games and Economic Behavior
14 Artificial Intelligence
6 Distributed Computing
6 Mathematical Programming. Series A. Series B
5 Discrete Applied Mathematics
5 International Journal of Game Theory
5 SIAM Journal on Computing
5 Information and Computation
5 European Journal of Operational Research
5 Games
4 Information Processing Letters
4 Mathematics of Operations Research
4 Mathematical Social Sciences
4 Annals of Pure and Applied Logic
4 Machine Learning
4 Annals of Mathematics and Artificial Intelligence
4 Computer Science Review
3 Discrete Mathematics
3 Applied Mathematics and Computation
3 Journal of Economic Theory
3 Journal of Mathematical Economics
3 Mathematical Logic Quarterly (MLQ)
2 Synthese
2 Systems & Control Letters
2 Operations Research Letters
2 Social Choice and Welfare
2 SIAM Journal on Discrete Mathematics
2 Annals of Operations Research
2 The Journal of Artificial Intelligence Research (JAIR)
2 Mathematical Problems in Engineering
2 Journal of Combinatorial Optimization
2 International Game Theory Review
2 Journal of Machine Learning Research (JMLR)
2 Game Theory
1 American Mathematical Monthly
1 Information Sciences
1 Naval Research Logistics
1 Results in Mathematics
1 Transactions of the American Mathematical Society
1 Probability Theory and Related Fields
1 Journal of Cryptology
1 Queueing Systems
1 Neural Networks
1 Random Structures & Algorithms
1 The Annals of Applied Probability
1 Applied Mathematical Modelling
1 Automation and Remote Control
1 Bulletin of the American Mathematical Society. New Series
1 Computational Complexity
1 Computational Optimization and Applications
1 Formal Methods in System Design
1 Economic Theory
1 ETNA. Electronic Transactions on Numerical Analysis
1 Constraints
1 European Series in Applied and Industrial Mathematics (ESAIM): Probability and Statistics
1 Journal of Scheduling
1 Journal of the ACM
1 Annals of Combinatorics
1 International Journal of Applied Mathematics and Computer Science
1 CEJOR. Central European Journal of Operations Research
1 RAIRO. Operations Research
1 OR Spectrum
1 ACM Transactions on Computational Logic
1 Journal of Discrete Algorithms
1 Advances in Difference Equations
1 Networks and Spatial Economics
1 Optimization Letters
1 Logical Methods in Computer Science
1 Electronic Journal of Statistics
1 Theoretical Economics
1 ACM Transactions on Algorithms
1 ACM Transactions on Computation Theory

Citations by Year

Wikidata Timeline

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.