Document Open Access Logo

Optimal Tiling of the Euclidean Space Using Permutation-Symmetric Bodies

Authors Mark Braverman, Dor Minzer

PDF
Thumbnail PDF

File

LIPIcs.CCC.2021.5.pdf
  • Filesize: 1.07 MB
  • 48 pages

Document Identifiers

Author Details

Mark Braverman
  • Department of Computer Science, Princeton University, NJ, USA
Dor Minzer
  • Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, USA

Funding

  • Braverman, Mark: Research supported in part by the NSF Alan T. Waterman Award, Grant No. 1933331, a Packard Fellowship in Science and Engineering, and the Simons Collaboration on Algorithms and Geometry.

Cite As Get BibTex

Mark Braverman and Dor Minzer. Optimal Tiling of the Euclidean Space Using Permutation-Symmetric Bodies. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 5:1-5:48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.CCC.2021.5

Abstract

What is the least surface area of a permutation-symmetric body B whose ℤⁿ translations tile ℝⁿ? Since any such body must have volume 1, the isoperimetric inequality implies that its surface area must be at least Ω(√n). Remarkably, Kindler et al. showed that for general bodies B this is tight, i.e. that there is a tiling body of ℝⁿ whose surface area is O(√n).
In theoretical computer science, the tiling problem is intimately related to the study of parallel repetition theorems (which are an important component in PCPs), and more specifically in the question of whether a "strong version" of the parallel repetition theorem holds. Raz showed, using the odd cycle game, that strong parallel repetition fails in general, and subsequently these ideas were used in order to construct non-trivial tilings of ℝⁿ.
In this paper, motivated by the study of a symmetric parallel repetition, we consider the permutation-symmetric variant of the tiling problem in ℝⁿ. We show that any permutation-symmetric body that tiles ℝⁿ must have surface area at least Ω(n/√{log n}), and that this bound is tight, i.e. that there is a permutation-symmetric tiling body of ℝⁿ with surface area O(n/√{log n}). We also give matching bounds for the value of the symmetric parallel repetition of Raz’s odd cycle game.
Our result suggests that while strong parallel repetition fails in general, there may be important special cases where it still applies.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • PCP
  • Parallel Repetition
  • Tilings

Metrics

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

Related Versions

References

  1. Perfect sets are uncountable. [Online; accessed 15-April-2020]. URL: https://mathcs.org/analysis/reals/topo/proofs/pfctuncb.html.
  2. Noga Alon and Bo'az Klartag. Economical toric spines via cheeger’s inequality. Journal of Topology and Analysis, 1(02):101-111, 2009. Google Scholar
  3. Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, and Nisheeth K. Vishnoi. Unique games on expanding constraint graphs are easy: extended abstract. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 21-28, 2008. URL: https://doi.org/10.1145/1374376.1374380.
  4. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3):501-555, 1998. URL: https://doi.org/10.1145/278298.278306.
  5. Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70-122, 1998. URL: https://doi.org/10.1145/273865.273901.
  6. Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev, and David Steurer. Rounding parallel repetitions of unique games. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 374-383, 2008. URL: https://doi.org/10.1109/FOCS.2008.55.
  7. Boaz Barak, Pravesh K. Kothari, and David Steurer. Small-set expansion in shortcode graph and the 2-to-2 conjecture. In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, pages 9:1-9:12, 2019. URL: https://doi.org/10.4230/LIPIcs.ITCS.2019.9.
  8. Boaz Barak, Anup Rao, Ran Raz, Ricky Rosen, and Ronen Shaltiel. Strong parallel repetition theorem for free projection games. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings, pages 352-365, 2009. URL: https://doi.org/10.1007/978-3-642-03685-9_27.
  9. Amey Bhangale, Ramprasad Saptharishi, Girish Varma, and Rakesh Venkat. On fortification of projection games. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015, August 24-26, 2015, Princeton, NJ, USA, pages 497-511, 2015. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.497.
  10. Mark Braverman and Ankit Garg. Small value parallel repetition for general games. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 335-340, 2015. URL: https://doi.org/10.1145/2746539.2746565.
  11. Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. On non-optimally expanding sets in grassmann graphs. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 940-951, 2018. URL: https://doi.org/10.1145/3188745.3188806.
  12. Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. Towards a proof of the 2-to-1 games conjecture? In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 376-389, 2018. URL: https://doi.org/10.1145/3188745.3188804.
  13. Irit Dinur and David Steurer. Analytical approach to parallel repetition. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 624-633, 2014. URL: https://doi.org/10.1145/2591796.2591884.
  14. Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. J. ACM, 43(2):268-292, 1996. URL: https://doi.org/10.1145/226643.226652.
  15. Uriel Feige, Guy Kindler, and Ryan O'Donnell. Understanding parallel repetition requires understanding foams. In Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), pages 179-192. IEEE, 2007. Google Scholar
  16. Lance Fortnow, John Rompel, and Michael Sipser. On the power of multi-prover interactive protocols. Theor. Comput. Sci., 134(2):545-557, 1994. URL: https://doi.org/10.1016/0304-3975(94)90251-8.
  17. Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115-1145, 1995. URL: https://doi.org/10.1145/227683.227684.
  18. Thomas Holenstein. Parallel repetition: Simplification and the no-signaling case. Theory of Computing, 5(1):141-172, 2009. URL: https://doi.org/10.4086/toc.2009.v005a008.
  19. Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the 17th Annual IEEE Conference on Computational Complexity, Montréal, Québec, Canada, May 21-24, 2002, page 25, 2002. URL: https://doi.org/10.1109/CCC.2002.1004334.
  20. Subhash Khot. Inapproximability of NP-complete problems, discrete fourier analysis, and geometry. In Proceedings of the International Congress of Mathematicians 2010, pages 2676-2697, 2010. Google Scholar
  21. Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable csps? SIAM J. Comput., 37(1):319-357, 2007. URL: https://doi.org/10.1137/S0097539705447372.
  22. Subhash Khot, Dor Minzer, and Muli Safra. On independent sets, 2-to-2 games, and Grassmann graphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 576-589, 2017. URL: https://doi.org/10.1145/3055399.3055432.
  23. Subhash Khot, Dor Minzer, and Muli Safra. Pseudorandom sets in grassmann graph have near-perfect expansion. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 592-601, 2018. URL: https://doi.org/10.1109/FOCS.2018.00062.
  24. Guy Kindler, Anup Rao, Ryan O'Donnell, and Avi Wigderson. Spherical cubes: optimal foams from computational hardness amplification. Commun. ACM, 55(10):90-97, 2012. URL: https://doi.org/10.1145/2347736.2347757.
  25. Dana Moshkovitz. Parallel repetition from fortification. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 414-423, 2014. URL: https://doi.org/10.1109/FOCS.2014.51.
  26. Anup Rao. Parallel repetition in projection games and a concentration bound. SIAM Journal on Computing, 40(6):1871-1891, 2011. Google Scholar
  27. Ran Raz. A parallel repetition theorem. SIAM J. Comput., 27(3):763-803, 1998. URL: https://doi.org/10.1137/S0097539795280895.
  28. Ran Raz. A counterexample to strong parallel repetition. SIAM Journal on Computing, 40(3):771-777, 2011. Google Scholar
  29. Antonio Ros. The isoperimetric problem. Global Theory of Minimal Surfaces. Clay Math. Proc, vol. 2:175-209, 2005. Google Scholar
  30. Jean-François Sadoc and Nicolas Rivier. Foams and emulsions, volume 354. Springer Science & Business Media, 2013. Google Scholar
  31. Shmuel Safra and Oded Schwartz. On parallel-repetition, Unique-Games and Max-Cut, 2007. Google Scholar
  32. Luis Antonio Santaló Sors and Luis A Santaló. Integral geometry and geometric probability. Cambridge university press, 2004. Google Scholar
  33. William Thomson. On the division of space with minimum partitional area. Acta Math., 11:121-134, 1887. URL: https://doi.org/10.1007/BF02612322.
  34. Luca Trevisan. On Khot’s unique games conjecture. Bull. Amer. Math. Soc. (N.S.), 49(1):91-111, 2012. URL: https://doi.org/10.1090/S0273-0979-2011-01361-1.
  35. Madhur Tulsiani, John Wright, and Yuan Zhou. Optimal strong parallel repetition for projection games on low threshold rank graphs. In International Colloquium on Automata, Languages, and Programming, pages 1003-1014. Springer, 2014. 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