Document Open Access Logo

Strong Approximate Consensus Halving and the Borsuk-Ulam Theorem

Authors Eleni Batziou, Kristoffer Arnsfelt Hansen , Kasper Høgh

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.24.pdf
  • Filesize: 0.8 MB
  • 20 pages

Document Identifiers

Author Details

Eleni Batziou
  • Technical University of Munich, Germany
Kristoffer Arnsfelt Hansen
  • Aarhus University, Denmark
Kasper Høgh
  • Aarhus University, Denmark

Funding

Kristoffer Arnsfelt Hansen and Kasper Høgh: Supported by the Independent Research Fund Denmark under grant no. 9040-00433B.
  • Batziou, Eleni: Supported by the German Research Foundation (DFG) within the Research Training Group AdONE (GRK 2201).

Cite As Get BibTex

Eleni Batziou, Kristoffer Arnsfelt Hansen, and Kasper Høgh. Strong Approximate Consensus Halving and the Borsuk-Ulam Theorem. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ICALP.2021.24

Abstract

In the consensus halving problem we are given n agents with valuations over the interval [0,1]. The goal is to divide the interval into at most n+1 pieces (by placing at most n cuts), which may be combined to give a partition of [0,1] into two sets valued equally by all agents. The existence of a solution may be established by the Borsuk-Ulam theorem. We consider the task of computing an approximation of an exact solution of the consensus halving problem, where the valuations are given by distribution functions computed by algebraic circuits. Here approximation refers to computing a point that is ε-close to an exact solution, also called strong approximation. We show that this task is polynomial time equivalent to computing an approximation to an exact solution of the Borsuk-Ulam search problem defined by a continuous function that is computed by an algebraic circuit.
The Borsuk-Ulam search problem is the defining problem of the complexity class BU. We introduce a new complexity class BBU to also capture an alternative formulation of the Borsuk-Ulam theorem from a computational point of view. We investigate their relationship and prove several structural results for these classes as well as for the complexity class FIXP.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity classes
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Consensus halving
  • Computational Complexity
  • Borsuk-Ulam

Metrics

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

Related Versions

References

  1. James Aisenberg, Maria Luisa Bonet, and Sam Buss. 2-d tucker is PPA complete. J. Comput. Syst. Sci., 108:92-103, 2020. URL: https://doi.org/10.1016/j.jcss.2019.09.002.
  2. Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, and Peter Bro Miltersen. On the complexity of numerical analysis. SIAM J. Comput., 38(5):1987-2006, 2009. URL: https://doi.org/10.1137/070697926.
  3. S. Basu, R. Pollack, and M. Roy. Algorithms in Real Algebraic Geometry. Springer, second edition, 2008. Google Scholar
  4. Lenore Blum, M. Schub, and Steve Smale. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bull. Amer. Math. Soc., 21:1-46, July 1989. URL: https://doi.org/10.1090/S0273-0979-1989-15750-9.
  5. Karol Borsuk. Drei sätze über die n-dimensionale euklidische sphäre. Fundamenta Mathematicae, 20(1):177-190, 1933. URL: https://doi.org/10.4064/fm-20-1-177-190.
  6. L. E. J. Brouwer. Über abbildung von mannigfaltigkeiten. Mathematische Annalen, 71:97-115, 1911. URL: https://doi.org/10.1007/BF01456931.
  7. John Canny. Some algebraic and geometric computations in PSPACE. In STOC, pages 460-467. ACM, January 1988. URL: https://doi.org/10.1145/62212.62257.
  8. Xi Chen and Xiaotie Deng. Settling the complexity of two-player Nash equilibrium. In FOCS 2006, pages 261-272. IEEE Computer Society Press, 2006. Google Scholar
  9. 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
  10. Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos, and Paul G. Spirakis. Computing exact solutions of consensus halving and the Borsuk-Ulam theorem. In ICALP, volume 132 of LIPIcs, pages 138:1-138:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.138.
  11. Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos, and Paul G. Spirakis. Computing exact solutions of consensus halving and the Borsuk-Ulam theorem. Journal of Computer and System Sciences, 117:75-98, 2021. URL: https://doi.org/10.1016/j.jcss.2020.10.006.
  12. 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
  13. Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Paul W. Goldberg, and Jie Zhang. Hardness results for consensus-halving. In MFCS, volume 117 of LIPIcs, pages 24:1-24:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.MFCS.2018.24.
  14. Aris Filos-Ratsikas and Paul W. Goldberg. Consensus halving is PPA-complete. In STOC, pages 51-64. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188880.
  15. Aris Filos-Ratsikas and Paul W. Goldberg. The complexity of splitting necklaces and bisecting ham sandwiches. In STOC, pages 638-649. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316334.
  16. Aris Filos-Ratsikas, Alexandros Hollender, Katerina Sotiraki, and Manolis Zampetakis. Consensus-halving: Does it ever get easier? In EC, pages 381-399. ACM, 2020. URL: https://doi.org/10.1145/3391403.3399527.
  17. Paul W. Goldberg and Christos H. Papadimitriou. Towards a unified complexity theory of total functions. Journal of Computer and System Sciences, 94:167-192, 2018. URL: https://doi.org/10.1016/j.jcss.2017.12.003.
  18. Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics. Springer, 1988. Google Scholar
  19. Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci, 48(3):498-532, 1994. Google Scholar
  20. Marcus Schaefer and Daniel Štefankovič. Fixed points, Nash equilibria, and the existential theory of the reals. Theory Comput Syst, 60:172-193, November 2017. URL: https://doi.org/10.1007/s00224-015-9662-0.
  21. Forest W. Simmons and Francis Edward Su. Consensus-halving via theorems of Borsuk-Ulam and Tucker. Math. Soc. Sci., 45(1):15-25, 2003. URL: https://doi.org/10.1016/S0165-4896(02)00087-2.
  22. Francis Edward Su. Borsuk-Ulam implies Brouwer: A direct construction. The American Mathematical Monthly, 104(9):855-859, 1997. URL: https://doi.org/10.2307/2975293.
  23. Sergey P. Tarasov and Mikhail N. Vyalyi. Semidefinite programming and arithmetic circuit evaluation. Discrete Applied Mathematics, 156(11):2070-2078, 2008. URL: https://doi.org/10.1016/j.dam.2007.04.023.
  24. Alexey Yu. Volovikov. Borsuk-Ulam implies Brouwer: A direct construction revisited. Am. Math. Mon., 115(6):553-556, 2008. 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 About DROPS Imprint Privacy Contact