Ham Sandwich is Equivalent to Borsuk-Ulam

Authors Karthik C. S., Arpan Saha



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2017.24.pdf
  • Filesize: 0.53 MB
  • 15 pages

Document Identifiers

Author Details

Karthik C. S.
Arpan Saha

Cite AsGet BibTex

Karthik C. S. and Arpan Saha. Ham Sandwich is Equivalent to Borsuk-Ulam. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.SoCG.2017.24

Abstract

The Borsuk-Ulam theorem is a fundamental result in algebraic topology, with applications to various areas of Mathematics. A classical application of the Borsuk-Ulam theorem is the Ham Sandwich theorem: The volumes of any n compact sets in R^n can always be simultaneously bisected by an (n-1)-dimensional hyperplane. In this paper, we demonstrate the equivalence between the Borsuk-Ulam theorem and the Ham Sandwich theorem. The main technical result we show towards establishing the equivalence is the following: For every odd polynomial restricted to the hypersphere f:S^n->R, there exists a compact set A in R^{n+1}, such that for every x in S^n we have f(x)=vol(A cap H^+) - vol(A cap H^-), where H is the oriented hyperplane containing the origin with x as the normal. A noteworthy aspect of the proof of the above result is the use of hyperspherical harmonics. Finally, using the above result we prove that there exist constants n_0, epsilon_0>0 such that for every n>= n_0 and epsilon <= epsilon_0/sqrt{48n}, any query algorithm to find an epsilon-bisecting (n-1)-dimensional hyperplane of n compact set in [-n^4.51,n^4.51]^n, even with success probability 2^-Omega(n), requires 2^Omega(n) queries.
Keywords
  • Ham Sandwich theorem
  • Borsuk-Ulam theorem
  • Query Complexity
  • Hyperspherical Harmonics

Metrics

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

References

  1. James Aisenberg, Maria Luisa Bonet, and Sam Buss. 2-D Tucker is PPA complete. Electronic Colloquium on Computational Complexity (ECCC), 22:163, 2015. URL: http://eccc.hpi-web.de/report/2015/163.
  2. Kendall Atkinson and Weimin Han. Spherical Harmonics and Approximations on the Unit Sphere: An Introduction. Springer-Verlag Berlin Heidelberg, 2012. URL: http://dx.doi.org/10.1007/978-3-642-25983-8.
  3. Yakov Babichenko. Query complexity of approximate nash equilibria. J. ACM, 63(4):36, 2016. URL: http://dx.doi.org/10.1145/2908734.
  4. Yakov Babichenko and Aviad Rubinstein. Communication complexity of approximate nash equilibria. CoRR, abs/1608.06580, 2016. URL: http://arxiv.org/abs/1608.06580.
  5. Kim Border. Fixed Point Theorems with Applications to Economics and Game Theory. Cambridge University Press, 1989. URL: http://dx.doi.org/10.1137/1028074.
  6. Karol Borsuk. Drei sätze über die n-dimensionale euklidische sphäre. Fundamental Mathematics, 20:177-190, 1933. Google Scholar
  7. L. E. J. Brouwer. Über Abbildung von Mannigfaltigkeiten. Mathematische Annalen, 71:97-115, 1912. URL: http://eudml.org/doc/158520.
  8. Xi Chen and Xiaotie Deng. Matching algorithmic bounds for finding a brouwer fixed point. J. ACM, 55(3), 2008. URL: http://dx.doi.org/10.1145/1379759.1379761.
  9. Xi Chen and Xiaotie Deng. On the complexity of 2D discrete fixed point problem. Theor. Comput. Sci., 410(44):4448-4456, 2009. URL: http://dx.doi.org/10.1016/j.tcs.2009.07.052.
  10. Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player nash equilibria. J. ACM, 56(3), 2009. URL: http://dx.doi.org/10.1145/1516512.1516516.
  11. Xi Chen and Shang-Hua Teng. Paths beyond local search: A tight bound for randomized fixed-point computation. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pages 124-134, 2007. URL: http://dx.doi.org/10.1109/FOCS.2007.53.
  12. Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The complexity of computing a nash equilibrium. SIAM J. Comput., 39(1):195-259, 2009. URL: http://dx.doi.org/10.1137/070699652.
  13. Herbert Edelsbrunner and Roman Waupotitsch. Computing a Ham-Sandwich Cut in Two Dimensions. J. Symb. Comput., 2(2):171-178, 1986. URL: http://dx.doi.org/10.1016/S0747-7171(86)80020-7.
  14. Costas Efthimiou and Christopher Frye. Spherical harmonics in p dimensions. World Scientific, Singapore, 2014. URL: https://cds.cern.ch/record/1953578.
  15. P. Funk. Beiträge zur Theorie der Kugelfunktionen. Mathematische Annalen, 77:136-152, 1916. URL: http://eudml.org/doc/158720.
  16. Jacques Hadamard. Note sur quelques applications de l’indice de kronecker. Jules Tannery: Introduction à la théorie des fonctions d’une variable, 2:437-477, 1910. Google Scholar
  17. E. Hecke. Über orthogonal-invariante Integralgleichungen. Mathematische Annalen, 78:398-404, 1917. URL: http://eudml.org/doc/158775.
  18. 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. URL: http://dx.doi.org/10.1016/0885-064X(89)90017-4.
  19. Christian Knauer, Hans Raj Tiwary, and Daniel Werner. On the computational complexity of Ham-Sandwich cuts, Helly sets, and related problems. In 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011, March 10-12, 2011, Dortmund, Germany, pages 649-660, 2011. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2011.649.
  20. Chi-Yuan Lo, Jirí Matousek, and William L. Steiger. Algorithms for Ham-Sandwich Cuts. Discrete & Computational Geometry, 11:433-452, 1994. URL: http://dx.doi.org/10.1007/BF02574017.
  21. Jirí Matousek. Using the Borsuk-Ulam Theorem. Springer-Verlag Berlin Heidelberg, 2003. URL: http://dx.doi.org/10.1007/978-3-540-76649-0.
  22. E. J. McShane. Extension of range of functions. Bulletin of the American Mathematical Society, 40(12):837-843, 1934. Google Scholar
  23. John Nash. Non-cooperative games. Annals of Mathematics, 54(2):286-295, 1951. URL: http://www.jstor.org/stable/1969529.
  24. 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. URL: http://dx.doi.org/10.1016/S0022-0000(05)80063-7.
  25. Tim Roughgarden and Omri Weinstein. On the communication complexity of approximate fixed points. Electronic Colloquium on Computational Complexity (ECCC), 23:55, 2016. URL: http://eccc.hpi-web.de/report/2016/055.
  26. Aviad Rubinstein. Inapproximability of Nash Equilibrium. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 409-418, 2015. URL: http://dx.doi.org/10.1145/2746539.2746578.
  27. Aviad Rubinstein. Settling the complexity of computing approximate two-player Nash equilibria. CoRR, abs/1606.04550, 2016. URL: http://arxiv.org/abs/1606.04550.
  28. Hugo Steinhaus. A note on the ham sandwich theorem. Mathesis Polska, 9:26-28, 1938. Google Scholar
  29. A. H. Stone and J. W. Tukey. Generalized "sandwich" theorems. Duke Mathematical Journal, 9(2):356-359, 1942. Google Scholar
  30. Francis Edward Su. Borsuk-Ulam implies Brouwer: a direct construction. The American mathematical monthly, 104(9):855-859, 1997. Google Scholar
  31. Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices, page 210–268. Cambridge University Press, May 2012. URL: http://dx.doi.org/10.1017/CBO9780511794308.006.
  32. A. Yu. Volovikov. Brouwer, kakutani, and borsuk - ulam theorems. Mathematical Notes, 79(3):433-435, 2006. URL: http://dx.doi.org/10.1007/s11006-006-0048-0.
  33. Fuxiang Yu. On the complexity of the pancake problem. Math. Log. Q., 53(4-5):532-546, 2007. URL: http://dx.doi.org/10.1002/malq.200710016.
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