Fetching the paper…
Reading the bibliography…
We study the search problem class $\mathrm{PPA}_q$ defined as a modulo-$q$ analog of the well-known $\textit{polynomial parity argument}$ class $\mathrm{PPA}$ introduced by Papadimitriou '94.
Démonstration d’une hypothèse de m. artin
Claude Chevalley · 1935
Earlier work this paper cites.
Bemerkung zur vorstehenden arbeit von herrn chevalley
Ewald Warning · 1936
Earlier work this paper cites.
On a topological generalization of a theorem of tverberg
I. Bárány, S. B. Shlosman, and A. Szücs · 1981
Earlier work this paper cites.
Regular subgraphs of almost regular graphs
Noga Alon, Shmuel Friedland, and Gil Kalai · 1984
Earlier work this paper cites.
Bisection of circle colorings
C. Goldberg and D. West · 1985
Earlier work this paper cites.
The Borsuk-Ulam theorem and bisection of necklaces
Noga Alon and Douglas B. West · 1986
Earlier work this paper cites.
Splitting necklaces
Noga Alon · 1987
Earlier work this paper cites.
How easy is local search?
David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis · 1988
Earlier work this paper cites.
On total functions, existence theorems and computational complexity
Nimrod Megiddo and Christos H. Papadimitriou · 1991
Earlier work this paper cites.
Counting classes: Thresholds, parity, mods, and fewness
Richard Beigel and John Gill · 1992
Earlier work this paper cites.
On the complexity of the parity argument and other inefficient proofs of existence
Christos H. Papadimitriou · 1994
Earlier work this paper cites.
The relative complexity of NP search problems
Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, and Toniann Pitassi · 1998
Earlier work this paper cites.
More on the relative strength of counting principles
Paul Beame and Søren Riis · 1998
Earlier work this paper cites.
Combinatorial Algorithms: Generation, Enumeration, and Search
Donald L. Kreher and Douglas R. Stinson · 1998
Cited alongside, same era.
Linear gaps between degrees for the polynomial calculus modulo distinct primes
Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, and Toniann Pitassi · 2000
Cited alongside, same era.
A sperner lemma complete for ppa
Michelangelo Grigni · 2001
Cited alongside, same era.
Relativized NP search problems and propositional proof systems
Josh Buresh-Oppenheim and Tsuyoshi Morioka · 2004
Cited alongside, same era.
On the TFNP complexity of factoring
Joshua Buresh-Oppenheim · 2006
Cited alongside, same era.
On kemnitz’conjecture concerning lattice-points in the plane
Christian Reiher · 2007
Cited alongside, same era.
Integer factoring and modular square roots
Emil Jerábek · 2015
Later among the works it cites.
Understanding PPA-Completeness
Xiaotie Deng, Jack R. Edmonds, Zhe Feng, Zhengyang Liu, Qi Qi, and Zeying Xu · 2016
Later among the works it cites.
Settling the complexity of computing approximate two-player nash equilibria
Aviad Rubinstein · 2016
Later among the works it cites.
On the polynomial parity argument complexity of the combinatorial nullstellensatz
Aleksandrs Belovs, Gábor Ivanyos, Youming Qiao, Miklos Santha, and Siyi Yang · 2017
Later among the works it cites.
Consensus halving is ppa-complete
Aris Filos-Ratsikas and Paul W. Goldberg · 2018
Later among the works it cites.
Sum-of-squares meets nash: lower bounds for finding any equilibrium
Pravesh K Kothari and Ruta Mehta · 2018
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
The complexity of computing a nash equilibrium
Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou · 2009
Cited alongside, same era.
Continuous local search
Constantinos Daskalakis and Christos H. Papadimitriou · 2011
Cited alongside, same era.
Reductions and propositional proofs for total NP search problems
Alan S. Johnson · 2011
Cited alongside, same era.
Propositional proofs and reductions between NP search problems
Samuel R. Buss and Alan S. Johnson · 2012
Cited alongside, same era.
2-d tucker is PPA complete
James Aisenberg, Maria Luisa Bonet, and Sam Buss · 2015
Cited alongside, same era.
On the cryptographic hardness of finding a nash equilibrium
Nir Bitansky, Omer Paneth, and Alon Rosen · 2015
Cited alongside, same era.
Ppp-completeness with connections to cryptography
Katerina Sotiraki, Manolis Zampetakis, and Giorgos Zirdelis · 2018
Later among the works it cites.
Finding a nash equilibrium is no easier than breaking fiat-shamir
Arka Rai Choudhuri, Pavel Hubácek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, and Guy N Rothblum · 2019
Closest in time.
The complexity of splitting necklaces and bisecting ham sandwiches
Aris Filos-Ratsikas and Paul W. Goldberg · 2019
Closest in time.
Adventures in monotone complexity and TFNP
Mika Göös, Pritish Kamath, Robert Robere, and Dmitry Sokolov · 2019
Closest in time.
The classes PPA- k k : Existence from arguments modulo k k
Alexandros Hollender · 2019
Closest in time.
White-box vs. black-box complexity of search problems: Ramsey and graph property testing
Ilan Komargodski, Moni Naor, and Eylon Yogev · 2019
Closest in time.