Skip to main content
Share Your Experience: Take the 2024 Developer Survey
7 votes
Accepted

Is End-of-Monotone-Line PPAD-complete?

Your problem is equivalent to End-of-Metered-Line. This can be shown by reducing your problem to End-of-Potential-Line (see https://arxiv.org/abs/1702.06017). This is a version of End-of-the-Line ...
jfearnley's user avatar
6 votes

Proof refutation: Amateur reviews of ambitious CoRR papers

If you make an arXiv trackback you will not be ignored, in the sense that future readers of the ambitious arXiv paper may check the trackbacks. You even get a mild form of peer review for your posts, ...
Bjørn Kjos-Hanssen's user avatar
5 votes
Accepted

Does PPAD really capture the notion of finding another unbalanced vertex?

The problems have been proved to be equivalent (and thus PPAD-complete), see Section 8 in The Hairy Ball Problem is PPAD-Complete by Paul W. Goldberg and Alexandros Hollender.
domotorp's user avatar
  • 14k
4 votes

Does PPAD really capture the notion of finding another unbalanced vertex?

This is an interesting question, and I can only give a partial answer. It is easy to see that the construction on p. 505 of Papadimitriou’s paper shows the equivalence of AUV with its special case ...
Emil Jeřábek's user avatar
4 votes
Accepted

END OF THE LINE problem finding a node with in-degree $0$ or out-degree $0$ depending on the initial node

This class was defined in Papadimitriou's original 1994 paper, that also introduced the class PPAD, and it is known as PPADS. There is an oracle separation between the two classes. For a recent paper ...
domotorp's user avatar
  • 14k
3 votes

How hard is Hex from a symmetric position?

Finding a winning move in symmetric positions in Hex is PSPACE-complete First, let's define our problem, and call it SYMHEXMOVE: Take as an input: a symmetric Hex position Output: any move which is ...
Kevin Wang's user avatar
3 votes
Accepted

What does $\#P\subseteq FP^{PPAD}$ imply?

First, $\mathrm{PPAD\subseteq FP^{NP}}$, hence $\mathrm{\#P^{PPAD}\subseteq\#P^{NP}\subseteq FP^{\#P}}$. Moreover, $\mathrm{PPAD}$ is closed under Turing reductions, i.e., $\mathrm{FP^{PPAD}\subseteq ...
Emil Jeřábek's user avatar
2 votes

Proof refutation: Amateur reviews of ambitious CoRR papers

The ScienceOpen website has a page for most arXiv articles (e.g., here), and it has an option where you can post your own review of any preprint. I do not know if they are recommendable or not (but ...
a3nm's user avatar
  • 9,419

Only top scored, non community-wiki answers of a minimum length are eligible