Search results for "PPAD"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
103	Xi Chen 0001, Xiaotie Deng, Shang-Hua Teng	Settling the complexity of computing two-player Nash equilibria.	J. ACM	2009	DBLP DOI BibTeX RDF	Arrow-Debreu market, Brouwer's fixed point, Lemke-Howson algorithm, PPAD-completeness, Sperner's lemma, Nash equilibrium, smoothed analysis, Two-player game
94	Xi Chen 0001, Xiaotie Deng, Shang-Hua Teng	Computing Nash Equilibria: Approximation and Smoothed Complexity.	FOCS	2006	DBLP DOI BibTeX RDF
65	Christian Borgs, Jennifer T. Chayes, Nicole Immorlica, Adam Tauman Kalai, Vahab S. Mirrokni, Christos H. Papadimitriou	The myth of the folk theorem.	STOC	2008	DBLP DOI BibTeX RDF	folk theorem, ppad, nash equilibrium
65	Edith Elkind, Leslie Ann Goldberg, Paul W. Goldberg	Nash equilibria in graphical games on trees revisited.	EC	2006	DBLP DOI BibTeX RDF	PPAD-completeness, nash equilibrium, graphical games
65	Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou	The complexity of computing a Nash equilibrium.	STOC	2006	DBLP DOI BibTeX RDF	PPAD-completeness, complexity, game theory, Nash equilibrium
56	Xi Chen 0001, Shang-Hua Teng	Spending Is Not Easier Than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria.	ISAAC	2009	DBLP DOI BibTeX RDF
56	Xi Chen 0001, Xiaotie Deng	On the Complexity of 2D Discrete Fixed Point Problem.	ICALP (1)	2006	DBLP DOI BibTeX RDF
38	Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou	The complexity of computing a Nash equilibrium.	Commun. ACM	2009	DBLP DOI BibTeX RDF
38	Kousha Etessami, Mihalis Yannakakis	On the Complexity of Nash Equilibria and Other Fixed Points (Extended Abstract).	FOCS	2007	DBLP DOI BibTeX RDF
38	Li-Sha Huang, Shang-Hua Teng	On the Approximation and Smoothed Complexity of Leontief Market Equilibria.	FAW	2007	DBLP DOI BibTeX RDF
27	Xi Chen 0001, Decheng Dai, Ye Du, Shang-Hua Teng	Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities.	FOCS	2009	DBLP DOI BibTeX RDF	Arrow-Debreu markets, PPAD-completeness, Computational complexity
27	David S. Johnson	The NP-completeness column: Finding needles in haystacks.	ACM Trans. Algorithms	2007	DBLP DOI BibTeX RDF	PPAD, game theory, local search, Nash equilibrium, fixed point, PLS
26	Paul W. Goldberg, Matthew J. Katzman	PPAD-complete approximate pure Nash equilibria in Lipschitz games.	Theor. Comput. Sci.	2023	DBLP DOI BibTeX RDF
26	John Fearnley, Paul Goldberg 0001, Alexandros Hollender, Rahul Savani	The Complexity of Gradient Descent: CLS = PPAD ∩ PLS.	J. ACM	2023	DBLP DOI BibTeX RDF
26	Mohammad Al Olaimat, Jared Martinez, Fahad Saeed, Serdar Bozdag	PPAD: a deep learning architecture to predict progression of Alzheimer's disease.	Bioinform.	2023	DBLP DOI BibTeX RDF
26	Aris Filos-Ratsikas, Kristoffer Arnsfelt Hansen, Kasper Høgh, Alexandros Hollender	PPAD-membership for Problems with Exact Rational Solutions: A General Approach via Convex Optimization.	CoRR	2023	DBLP DOI BibTeX RDF
26	Yael Tauman Kalai, Alex Lombardi, Vinod Vaikuntanathan	SNARGs and PPAD Hardness from the Decisional Diffie-Hellman Assumption.	EUROCRYPT (2)	2023	DBLP DOI BibTeX RDF
26	Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos	Pure-Circuit: Strong Inapproximability for PPAD.	CoRR	2022	DBLP DOI BibTeX RDF
26	Paul W. Goldberg, Matthew J. Katzman	PPAD-Complete Pure Approximate Nash Equilibria in Lipschitz Games.	CoRR	2022	DBLP DOI BibTeX RDF
26	Yael Tauman Kalai, Alex Lombardi, Vinod Vaikuntanathan	SNARGs and PPAD Hardness from the Decisional Diffie-Hellman Assumption.	IACR Cryptol. ePrint Arch.	2022	DBLP BibTeX RDF
26	Nir Bitansky, Arka Rai Choudhuri, Justin Holmgren, Chethan Kamath, Alex Lombardi, Omer Paneth, Ron D. Rothblum	PPAD is as Hard as LWE and Iterated Squaring.	IACR Cryptol. ePrint Arch.	2022	DBLP BibTeX RDF
26	Paul W. Goldberg, Matthew J. Katzman	PPAD-Complete Pure Approximate Nash Equilibria in Lipschitz Games.	SAGT	2022	DBLP DOI BibTeX RDF
26	Nir Bitansky, Arka Rai Choudhuri, Justin Holmgren, Chethan Kamath, Alex Lombardi, Omer Paneth, Ron D. Rothblum	PPAD is as Hard as LWE and Iterated Squaring.	TCC (2)	2022	DBLP DOI BibTeX RDF
26	Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos	Pure-Circuit: Strong Inapproximability for PPAD.	FOCS	2022	DBLP DOI BibTeX RDF
26	Alexander Grishutin, Daniil Musatov	Discrete Versions of the KKM Lemma and Their PPAD-Completeness.	CSR	2022	DBLP DOI BibTeX RDF
26	Alon Rosen, Gil Segev 0001, Ido Shahaf	Can PPAD Hardness be Based on Standard Cryptographic Assumptions?	J. Cryptol.	2021	DBLP DOI BibTeX RDF
26	Paul W. Goldberg, Alexandros Hollender	The Hairy Ball problem is PPAD-complete.	J. Comput. Syst. Sci.	2021	DBLP DOI BibTeX RDF
26	Ruta Jawale, Yael Tauman Kalai, Dakshita Khurana, Rachel Yun Zhang	SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE.	STOC	2021	DBLP DOI BibTeX RDF
26	John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani	The complexity of gradient descent: CLS = PPAD ∩ PLS.	STOC	2021	DBLP DOI BibTeX RDF
26	John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani	The Complexity of Gradient Descent: CLS = PPAD ∩ PLS.	CoRR	2020	DBLP BibTeX RDF
26	Argyrios Deligkas, John Fearnley, Rahul Savani	Tree Polymatrix Games are PPAD-hard.	CoRR	2020	DBLP BibTeX RDF
26	Alex Lombardi, Vinod Vaikuntanathan	Fiat-Shamir for Repeated Squaring with Applications to PPAD-Hardness and VDFs.	IACR Cryptol. ePrint Arch.	2020	DBLP BibTeX RDF
26	Ruta Jawale, Dakshita Khurana	Lossy Correlation Intractability and PPAD Hardness from Sub-exponential LWE.	IACR Cryptol. ePrint Arch.	2020	DBLP BibTeX RDF
26	Ruta Jawale, Yael Tauman Kalai, Dakshita Khurana, Rachel Yun Zhang	SNARGs for Bounded Depth Computations and PPAD Hardness from Sub-Exponential LWE.	IACR Cryptol. ePrint Arch.	2020	DBLP BibTeX RDF
26	Argyrios Deligkas, John Fearnley, Rahul Savani	Tree Polymatrix Games Are PPAD-Hard.	ICALP	2020	DBLP DOI BibTeX RDF
26	Alex Lombardi, Vinod Vaikuntanathan	Fiat-Shamir for Repeated Squaring with Applications to PPAD-Hardness and VDFs.	CRYPTO (3)	2020	DBLP DOI BibTeX RDF
26	Yael Tauman Kalai, Omer Paneth, Lisa Yang 0001	Delegation with Updatable Unambiguous Proofs and PPAD-Hardness.	CRYPTO (3)	2020	DBLP DOI BibTeX RDF
26	Paul W. Goldberg, Alexandros Hollender	The Hairy Ball Problem is PPAD-Complete.	CoRR	2019	DBLP BibTeX RDF
26	Arka Rai Choudhuri, Pavel Hubácek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, Guy N. Rothblum	PPAD-Hardness via Iterated Squaring Modulo a Composite.	IACR Cryptol. ePrint Arch.	2019	DBLP BibTeX RDF
26	Paul W. Goldberg, Alexandros Hollender	The Hairy Ball Problem is PPAD-Complete.	ICALP	2019	DBLP DOI BibTeX RDF
26	Sanaz Taheri Boshrooyeh, Alptekin Küpçü, Öznur Özkasap	PPAD: Privacy Preserving Group-Based ADvertising in Online Social Networks.	IACR Cryptol. ePrint Arch.	2018	DBLP BibTeX RDF
26	Ruta Mehta	Constant Rank Two-Player Games are PPAD-hard.	SIAM J. Comput.	2018	DBLP DOI BibTeX RDF
26	Sanaz Taheri Boshrooyeh, Alptekin Küpçü, Öznur Özkasap	PPAD: Privacy Preserving Group-Based ADvertising in Online Social Networks. (PDF / PS)	Networking	2018	DBLP DOI BibTeX RDF
26	Frédéric Meunier, Wolfgang Mulzer, Pauline Sarrabezolles, Yannik Stein	The Rainbow at the End of the Line - A PPAD Formulation of the Colorful Carathéodory Theorem with Applications.	SODA	2017	DBLP DOI BibTeX RDF
26	Steffen Schuldenzucker, Sven Seuken, Stefano Battiston	Finding Clearing Payments in Financial Networks with Credit Default Swaps is PPAD-complete.	ITCS	2017	DBLP DOI BibTeX RDF
26	Alon Rosen, Gil Segev 0001, Ido Shahaf	Can PPAD Hardness be Based on Standard Cryptographic Assumptions?	TCC (2)	2017	DBLP DOI BibTeX RDF
26	Alon Rosen, Gil Segev 0001, Ido Shahaf	Can PPAD Hardness be Based on Standard Cryptographic Assumptions?	Electron. Colloquium Comput. Complex.	2016	DBLP BibTeX RDF
26	Frédéric Meunier, Wolfgang Mulzer, Pauline Sarrabezolles, Yannik Stein	The Rainbow at the End of the Line - A PPAD Formulation of the Colorful Carathéodory Theorem with Applications.	CoRR	2016	DBLP BibTeX RDF
26	Ioannis Avramopoulos	Multiplicative weights, equalizers, and P=PPAD.	CoRR	2016	DBLP BibTeX RDF
26	Alon Rosen, Gil Segev 0001, Ido Shahaf	Can PPAD Hardness be Based on Standard Cryptographic Assumptions?	IACR Cryptol. ePrint Arch.	2016	DBLP BibTeX RDF
26	Yakov Babichenko, Christos H. Papadimitriou, Aviad Rubinstein	Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash.	CoRR	2015	DBLP BibTeX RDF
26	Ruta Mehta	Constant Rank Bimatrix Games are PPAD-hard.	CoRR	2014	DBLP BibTeX RDF
26	Ruta Mehta	Constant rank bimatrix games are PPAD-hard.	STOC	2014	DBLP DOI BibTeX RDF
26	Ilan Adler, Sushil Verma	A direct reduction of PPAD Lemke-verified linear complementarity problems to bimatrix games	CoRR	2013	DBLP BibTeX RDF
26	Tamás Király, Júlia Pap	PPAD-completeness of polyhedral versions of Sperner's Lemma.	Discret. Math.	2013	DBLP DOI BibTeX RDF
26	Yang Li	BQP and PPAD.	Electron. Colloquium Comput. Complex.	2011	DBLP BibTeX RDF
26	Yang D. Li	BQP and PPAD	CoRR	2011	DBLP BibTeX RDF
26	Paul W. Goldberg	A Survey of PPAD-Completeness for Computing Nash Equilibria	CoRR	2011	DBLP BibTeX RDF
26	Dömötör Pálvölgyi	2D-TUCKER Is PPAD-Complete.	WINE	2009	DBLP DOI BibTeX RDF
26	Xiaotie Deng, Ye Du	The computation of approximate competitive equilibrium is PPAD-hard.	Inf. Process. Lett.	2008	DBLP DOI BibTeX RDF
26	Shiva Kintali	Scarf is Ppad-Complete	CoRR	2008	DBLP BibTeX RDF
26	Xi Chen 0001, Xiaotie Deng	3-NASH is PPAD-Complete	Electron. Colloquium Comput. Complex.	2005	DBLP BibTeX RDF
19	Katalin Friedl, Gábor Ivanyos, Miklos Santha, Yves F. Verhoeven	On the Black-Box Complexity of Sperner's Lemma.	Theory Comput. Syst.	2009	DBLP DOI BibTeX RDF	Sperner’s lemma, Probabilistic and quantum lower bound, Deterministic algorithm, Query complexity
19	Elad Hazan, Robert Krauthgamer	How hard is it to approximate the best Nash equilibrium?	SODA	2009	DBLP DOI BibTeX RDF
19	Constantinos Daskalakis, Grant Schoenebeck, Gregory Valiant, Paul Valiant	On the complexity of Nash equilibria of action-graph games.	SODA	2009	DBLP DOI BibTeX RDF
19	Constantinos Daskalakis, Christos H. Papadimitriou	On oblivious PTAS's for nash equilibrium.	STOC	2009	DBLP DOI BibTeX RDF	anonymous games, oblivious algorithms, PTAS, bimatrix games
19	Christos H. Papadimitriou	Nash Equilibria: Where We Stand.	ESA	2007	DBLP DOI BibTeX RDF
19	Christos H. Papadimitriou	The Computation of Equilibria.	WINE	2007	DBLP DOI BibTeX RDF
19	Bruno Codenotti, Amin Saberi, Kasturi R. Varadarajan, Yinyu Ye 0001	Leontief economies encode nonzero sum two-player games.	SODA	2006	DBLP DOI BibTeX RDF
19	Xi Chen 0001, Xiaotie Deng	Settling the Complexity of Two-Player Nash Equilibrium.	FOCS	2006	DBLP DOI BibTeX RDF
19	Bruno Codenotti, Mauro Leoncini, Giovanni Resta	Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games.	ESA	2006	DBLP DOI BibTeX RDF
19	Constantinos Daskalakis, Alex Fabrikant, Christos H. Papadimitriou	The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games.	ICALP (1)	2006	DBLP DOI BibTeX RDF
19	Xi Chen 0001, Xiaotie Deng, Shang-Hua Teng	Sparse Games Are Hard.	WINE	2006	DBLP DOI BibTeX RDF
19	Xi Chen 0001, Li-Sha Huang, Shang-Hua Teng	Market Equilibria with Hybrid Linear-Leontief Utilities.	WINE	2006	DBLP DOI BibTeX RDF
19	Katalin Friedl, Gábor Ivanyos, Miklos Santha, Yves F. Verhoeven	Locally 2-Dimensional Sperner Problems Complete for the Polynomial Parity Argument Classes.	CIAC	2006	DBLP DOI BibTeX RDF
19	Katalin Friedl, Gábor Ivanyos, Miklos Santha, Yves F. Verhoeven	On the Black-Box Complexity of Sperner's Lemma.	FCT	2005	DBLP DOI BibTeX RDF
19	Rahul Savani, Bernhard von Stengel	Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game.	FOCS	2004	DBLP DOI BibTeX RDF
19	Josh Buresh-Oppenheim, Tsuyoshi Morioka	Relativized NP Search Problems and Propositional Proof Systems.	CCC	2004	DBLP DOI BibTeX RDF