Document Open Access Logo

Unique End of Potential Line

Authors John Fearnley, Spencer Gordon, Ruta Mehta, Rahul Savani

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.56.pdf
  • Filesize: 489 kB
  • 15 pages

Document Identifiers

Author Details

John Fearnley
  • University of Liverpool, UK
Spencer Gordon
  • California Institute of Technology, Pasadena, CA, USA
Ruta Mehta
  • University of Illinois at Urbana-Champaign, IL, USA
Rahul Savani
  • University of Liverpool, UK

Funding

  • Fearnley, John: Research supported by EPSRC grant EP/P020909/1.
  • Mehta, Ruta: Research supported by NSF grant CCF-1750436.

Acknowledgements

We thank Aviad Rubinstein and Kousha Etessami for alerting us to the work in [Qi Qi, 2012], and we thank Rasmus Ibsen Jensen for helpful comments on a preprint of this paper.

Cite AsGet BibTex

John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani. Unique End of Potential Line. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 56:1-56:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.56

Abstract

The complexity class CLS was proposed by Daskalakis and Papadimitriou in 2011 to understand the complexity of important NP search problems that admit both path following and potential optimizing algorithms. Here we identify a subclass of CLS - called UniqueEOPL - that applies a more specific combinatorial principle that guarantees unique solutions. We show that UniqueEOPL contains several important problems such as the P-matrix Linear Complementarity Problem, finding Fixed Point of Contraction Maps, and solving Unique Sink Orientations (USOs). UniqueEOPL seems to a proper subclass of CLS and looks more likely to be the right class for the problems of interest. We identify a problem - closely related to solving contraction maps and USOs - that is complete for UniqueEOPL. Our results also give the fastest randomised algorithm for P-matrix LCP.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • P-matrix linear complementarity problem
  • unique sink orientation
  • contraction map
  • TFNP
  • total search problems
  • continuous local search

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

  • This paper substantially revises and extends the work described in our previous preprint "End of Potential Line" arXiv:1804.03450 [John Fearnley et al., 2018]. The full version of the paper is available at https://arxiv.org/abs/1811.03841.

References

  1. Ilan Adler and Sushil Verma. The Linear Complementarity Problem, Lemke Algorithm, Perturbation, and the Complexity Class PPAD. Technical report, Manuscript, Depatrment of IEOR, University of California, Berkeley, CA 94720, 2011. Google Scholar
  2. David Aldous. Minimization algorithms and random walk on the d-cube. The Annals of Probability, pages 403-413, 1983. Google Scholar
  3. Stefan Banach. Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales. Fundamenta Mathematicae, 3(1):133-181, 1922. Google Scholar
  4. Nir Bitansky, Omer Paneth, and Alon Rosen. On the Cryptographic Hardness of Finding a Nash Equilibrium. In Proc. of FOCS, pages 1480-1498, 2015. Google Scholar
  5. Nir Bitansky, Omer Paneth, and Alon Rosen. On the cryptographic hardness of finding a Nash equilibrium. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 1480-1498. IEEE, 2015. Google Scholar
  6. Ch. Boonyasiriwat, Kris Sikorski, and Ch. Xiong. A note on two fixed point problems. J. Complexity, 23(4-6):952-961, 2007. Google Scholar
  7. Xi Chen and Xiaotie Deng. On algorithms for discrete and approximate Brouwer fixed points. In Proc. of STOC, pages 323-330, 2005. Google Scholar
  8. Xi Chen and Xiaotie Deng. Matching algorithmic bounds for finding a Brouwer fixed point. J. ACM, 55(3):13:1-13:26, 2008. Google Scholar
  9. Xi Chen and Xiaotie Deng. On the complexity of 2D discrete fixed point problem. Theor. Comput. Sci., 410(44):4448-4456, 2009. Google Scholar
  10. Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player Nash equilibria. J. ACM, 56(3):14, 2009. Google Scholar
  11. Anne Condon. The complexity of stochastic games. Information and Computation, 96(2):203-224, 1992. Google Scholar
  12. Richard W Cottle, Jong-Shi Pang, and Richard E Stone. The Linear Complementarity Problem. SIAM, 2009. Google Scholar
  13. Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing a Nash equilibrium. SIAM Journal on Computing, 39(1):195-259, 2009. Google Scholar
  14. Constantinos Daskalakis and Christos Papadimitriou. Continuous Local Search. In Proc. of SODA, pages 790-804, 2011. Google Scholar
  15. Constantinos Daskalakis, Christos Tzamos, and Manolis Zampetakis. A Converse to Banach’s Fixed Point Theorem and its CLS Completeness. In Proc. of STOC, 2018. Google Scholar
  16. Xiaotie Deng, Qi Qi, Amin Saberi, and Jie Zhang. Discrete Fixed Points: Models, Complexities, and Applications. Math. Oper. Res., 36(4):636-652, 2011. Google Scholar
  17. Jérôme Dohrau, Bernd Gärtner, Manuel Kohler, Jiří Matoušek, and Emo Welzl. ARRIVAL: a zero-player graph game in #1∩ #1. In A journey through discrete mathematics, pages 367-374. Springer, Cham, 2017. Google Scholar
  18. Kousha Etessami and Mihalis Yannakakis. On the Complexity of Nash Equilibria and Other Fixed Points. SIAM J. Comput., 39(6):2531-2597, 2010. Google Scholar
  19. Alex Fabrikant, Christos Papadimitriou, and Kunal Talwar. The complexity of pure Nash equilibria. In Proc. of STOC, pages 604-612. ACM, 2004. Google Scholar
  20. John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani. CLS: new problems and completeness. CoRR, abs/1702.06017, 2017. URL: http://arxiv.org/abs/1702.06017.
  21. John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani. End of Potential Line. CoRR, abs/1804.03450, 2018. URL: http://arxiv.org/abs/1804.03450.
  22. John Fearnley and Rahul Savani. The complexity of all-switches strategy improvement. In Proc. of SODA, pages 130-139, 2016. Google Scholar
  23. Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick. A subexponential lower bound for the Random Facet algorithm for Parity Games. In Proc. of SODA, pages 202-216, 2011. Google Scholar
  24. Martin Gairing and Rahul Savani. Computing Stable Outcomes in Hedonic Games. In Proc. of SAGT, pages 174-185, 2010. Google Scholar
  25. Sanjam Garg, Omkant Pandey, and Akshayaram Srinivasan. Revisiting the cryptographic hardness of finding a Nash equilibrium. In Annual Cryptology Conference, pages 579-604. Springer, 2016. Google Scholar
  26. Bernd Gärtner. The Random-Facet simplex algorithm on combinatorial cubes. Random Struct. Algorithms, 20(3):353-381, 2002. Google Scholar
  27. Bernd Gärtner, Thomas Dueholm Hansen, Pavel Hubáček, Karel Král, Hagar Mosaad, and Veronika Slívová. ARRIVAL: next stop in CLS. In Proc. of ICALP, pages 60:1-60:13, 2018. Google Scholar
  28. Bernd Gärtner and Ingo Schurr. Linear programming and unique sink orientations. In Proc. of SODA, pages 749-757, 2006. URL: http://dl.acm.org/citation.cfm?id=1109557.1109639.
  29. Bernd Gärtner and Antonis Thomas. The Complexity of Recognizing Unique Sink Orientations. In Proc. of STACS, pages 341-353, 2015. Google Scholar
  30. Thomas Dueholm Hansen and Rasmus Ibsen-Jensen. The complexity of interior point methods for solving discounted turn-based stochastic games. In Conference on Computability in Europe, pages 252-262, 2013. Google Scholar
  31. Thomas Dueholm Hansen, Mike Paterson, and Uri Zwick. Improved upper bounds for Random-Edge and Random-Jump on abstract cubes. In Proc. of SODA, pages 874-881, 2014. Google Scholar
  32. Michael D. Hirsch, Christos H. Papadimitriou, and Stephen A. Vavasis. Exponential lower bounds for finding Brouwer fix points. J. Complexity, 5(4):379-416, 1989. Google Scholar
  33. Kathy Williamson Hoke. Completely unimodal numberings of a simple polytope. Discrete Applied Mathematics, 20(1):69-81, 1988. Google Scholar
  34. Z. Huang, Leonid Khachiyan, and Krzysztof Sikorski. Approximating fixed points of weakly contracting mappings. J. Complexity, 15:200-213, 1999. Google Scholar
  35. Z. Huang, Leonid G. Khachiyan, and Christopher (Krzysztof) Sikorski. Approximating Fixed Points of Weakly Contracting Mappings. J. Complexity, 15(2):200-213, 1999. Google Scholar
  36. Pavel Hubáček and Eylon Yogev. Hardness of continuous local search: Query complexity and cryptographic lower bounds. In Proc. of SODA, pages 1352-1371, 2017. Google Scholar
  37. Emil Jeřábek. Integer factoring and modular square roots. Journal of Computer and System Sciences, 82(2):380-394, 2016. Google Scholar
  38. David S Johnson, Christos H Papadimitriou, and Mihalis Yannakakis. How easy is local search? Journal of Computer and System Sciences, 37(1):79-100, 1988. Google Scholar
  39. Gil Kalai. Three Puzzles on Mathematics, Computation, and Games. CoRR, abs/1801.02602, 2018. URL: http://arxiv.org/abs/1801.02602.
  40. Masakazu Kojima, Nimrod Megiddo, Toshihito Noma, and Akiko Yoshise. A unified approach to interior point algorithms for linear complementarity problems, volume 538. Springer Science &Business Media, 1991. Google Scholar
  41. Masakazu Kojima, Nimrod Megiddo, and Yinyu Ye. An interior point potential reduction algorithm for the linear complementarity problem. Mathematical Programming, 54(1-3):267-279, 1992. Google Scholar
  42. Carlton E Lemke. Bimatrix equilibrium points and mathematical programming. Management science, 11(7):681-689, 1965. Google Scholar
  43. Jiří Matoušek and Tibor Szabó. Random Edge Can Be Exponential on Abstract Cubes. In Proc. of FOCS, pages 92-100, 2004. Google Scholar
  44. Nimrod Megiddo and Christos H Papadimitriou. On total functions, existence theorems and computational complexity. Theoretical Computer Science, 81(2):317-324, 1991. Google Scholar
  45. Ruta Mehta. Constant rank bimatrix games are PPAD-hard. In Proc. of STOC, pages 545-554, 2014. Google Scholar
  46. Walter D Morris Jr. Randomized pivot algorithms for P-matrix linear complementarity problems. Mathematical programming, 92(2):285-296, 2002. Google Scholar
  47. Katta G Murty. Computational complexity of complementary pivot methods. In Complementarity and fixed point problems, pages 61-73. Springer, 1978. Google Scholar
  48. A. Nemirovsky and D. B. Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley, New York, 1983. Google Scholar
  49. Christos H Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences, 48(3):498-532, 1994. Google Scholar
  50. Anuj Puri. Theory of hybrid systems and discrete event systems. PhD thesis, University of California at Berkeley, 1996. Google Scholar
  51. Qi Qi. Computational efficiency in internet economics and resource allocation. PhD thesis, Stanford University, 2012. Google Scholar
  52. Aviad Rubinstein. Settling the Complexity of Computing Approximate Two-Player Nash Equilibria. In Proc. of FOCS, pages 258-265, 2016. Google Scholar
  53. Alejandro A Schäffer and Mihalis Yannakakis. Simple local search problems that are hard to solve. SIAM journal on Computing, 20(1):56-87, 1991. Google Scholar
  54. Ingo Schurr and Tibor Szabó. Finding the Sink Takes Some Time: An Almost Quadratic Lower Bound for Finding the Sink of Unique Sink Oriented Cubes. Discrete & Computational Geometry, 31(4):627-642, 2004. Google Scholar
  55. Ingo Schurr and Tibor Szabó. Jumping Doesn't Help in Abstract Cubes. In Proc. of IPCO, pages 225-235, 2005. Google Scholar
  56. Spencer Shellman and Krzysztof Sikorski. A recursive algorithm for the infinity-norm fixed point problem. Journal of Complexity, 19(6):799-834, 2003. Google Scholar
  57. Krzysztof Sikorski. Optimal solution of Nonlinear Equations. Oxford Press, New York, 200. Google Scholar
  58. Krzysztof Sikorski. Computational complexity of fixed points. Journal of Fixed Point Theory and Applications, 6(2):249-283, 2009. Google Scholar
  59. Alan Stickney and Layne Watson. Digraph models of Bard-type algorithms for the linear complementarity problem. Mathematics of Operations Research, 3(4):322-333, 1978. Google Scholar
  60. Tibor Szabó and Emo Welzl. Unique Sink Orientations of Cubes. In Proc. of FOCS, pages 547-555, 2001. Google Scholar
  61. Antonis Thomas. Exponential Lower Bounds for History-Based Simplex Pivot Rules on Abstract Cubes. In Proc. of ESA, pages 69:1-69:14, 2017. Google Scholar
  62. Uri Zwick and Mike Paterson. The complexity of mean payoff games on graphs. Theoretical Computer Science, 158(1-2):343-359, 1996. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact