Document Open Access Logo

Larger Corner-Free Sets from Combinatorial Degenerations

Authors Matthias Christandl, Omar Fawzi, Hoang Ta, Jeroen Zuiddam

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.48.pdf
  • Filesize: 0.74 MB
  • 20 pages

Document Identifiers

Author Details

Matthias Christandl
  • Department of Mathematical Sciences, University of Copenhagen, Denmark
Omar Fawzi
  • Univ. Lyon, ENS Lyon, UCBL, CNRS, Inria, LIP, France
Hoang Ta
  • Univ. Lyon, ENS Lyon, UCBL, CNRS, Inria, LIP, France
Jeroen Zuiddam
  • Korteweg-de Vries Institute for Mathematics, University of Amsterdam, The Netherlands

Funding

  • Christandl, Matthias: European Research Council (ERC Grant Agreement No. 818761), the VILLUM FONDEN via the QMATH Centre of Excellence (Grant No. 10059) and the QuantERA ERA-NET Cofund in Quantum Technologies implemented within the European Union’s Horizon 2020 Programme (QuantAlgo project) via the Innovation Fund Denmark.
  • Fawzi, Omar: European Research Council (ERC Grant Agreement No. 851716).
  • Ta, Hoang: European Research Council (ERC Grant Agreement No. 851716), LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program "Investissements d’Avenir" (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR).

Cite AsGet BibTex

Matthias Christandl, Omar Fawzi, Hoang Ta, and Jeroen Zuiddam. Larger Corner-Free Sets from Combinatorial Degenerations. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 48:1-48:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.48

Abstract

There is a large and important collection of Ramsey-type combinatorial problems, closely related to central problems in complexity theory, that can be formulated in terms of the asymptotic growth of the size of the maximum independent sets in powers of a fixed small hypergraph, also called the Shannon capacity. An important instance of this is the corner problem studied in the context of multiparty communication complexity in the Number On the Forehead (NOF) model. Versions of this problem and the NOF connection have seen much interest (and progress) in recent works of Linial, Pitassi and Shraibman (ITCS 2019) and Linial and Shraibman (CCC 2021). We introduce and study a general algebraic method for lower bounding the Shannon capacity of directed hypergraphs via combinatorial degenerations, a combinatorial kind of "approximation" of subgraphs that originates from the study of matrix multiplication in algebraic complexity theory (and which play an important role there) but which we use in a novel way. Using the combinatorial degeneration method, we make progress on the corner problem by explicitly constructing a corner-free subset in F₂ⁿ × F₂ⁿ of size Ω(3.39ⁿ/poly(n)), which improves the previous lower bound Ω(2.82ⁿ) of Linial, Pitassi and Shraibman (ITCS 2019) and which gets us closer to the best upper bound 4^{n - o(n)}. Our new construction of corner-free sets implies an improved NOF protocol for the Eval problem. In the Eval problem over a group G, three players need to determine whether their inputs x₁, x₂, x₃ ∈ G sum to zero. We find that the NOF communication complexity of the Eval problem over F₂ⁿ is at most 0.24n + 𝒪(log n), which improves the previous upper bound 0.5n + 𝒪(log n).

Subject Classification

ACM Subject Classification
  • Theory of computation → Communication complexity
  • Theory of computation → Algebraic complexity theory
  • Mathematics of computing → Discrete mathematics
Keywords
  • Corner-free sets
  • communication complexity
  • number on the forehead
  • combinatorial degeneration
  • hypergraphs
  • Shannon capacity
  • eval problem

Metrics

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

Related Versions

References

  1. Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, and Phuong Nguyen. The NOF multiparty communication complexity of composed functions. Computational Complexity, 24(3):645-694, 2015. URL: https://doi.org/10.1007/s00037-013-0078-4.
  2. Josh Alman and Virginia Vassilevska Williams. Further limitations of the known approaches for matrix multiplication. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), pages 25:1-25:15, 2018. URL: https://doi.org/10.4230/LIPIcs.ITCS.2018.25.
  3. Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), pages 522-539, 2021. URL: https://doi.org/10.1137/1.9781611976465.32.
  4. Noga Alon, Amir Shpilka, and Christopher Umans. On sunflowers and matrix multiplication. computational complexity, 22(2):219-243, 2013. URL: https://doi.org/10.1007/s00037-013-0060-1.
  5. Noga Alon and Adi Shraibman. Algorithmic number on the forehead protocols yielding dense Ruzsa-Szemerédi graphs and hypergraphs, 2020. URL: http://arxiv.org/abs/2001.00387.
  6. László Babai, Anna Gál, Peter G. Kimmel, and Satyanarayana V. Lokam. Communication complexity of simultaneous messages. SIAM J. Comput., 33(1):137-166, 2004. URL: https://doi.org/10.1137/S0097539700375944.
  7. Michael Bateman and Nets Hawk Katz. New bounds on cap sets. J. Amer. Math. Soc., 25(2):585-613, 2012. URL: https://doi.org/10.1090/S0894-0347-2011-00725-X.
  8. Paul Beame, Matei David, Toniann Pitassi, and Philipp Woelfel. Separating deterministic from nondeterministic NOF multiparty communication complexity. In International Colloquium on Automata, Languages, and Programming (ICALP 2007), pages 134-145, 2007. URL: https://doi.org/10.1007/978-3-540-73420-8_14.
  9. Richard Beigel, William Gasarch, and James Glenn. The multiparty communication complexity of Exact-T: Improved bounds and new problems. In International Symposium on Mathematical Foundations of Computer Science (MFCS 2006), pages 146-156, 2006. URL: https://doi.org/10.1007/11821069_13.
  10. Richard Beigel and Jun Tarui. On ACC. Computational Complexity, 4(4):350-366, 1994. URL: https://doi.org/10.1007/BF01263423.
  11. E. Bidamon and H. Meyniel. On the Shannon capacity of a directed graph. European J. Combin., 6(4):289-290, 1985. URL: https://doi.org/10.1016/S0195-6698(85)80042-1.
  12. Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Eric Naslund, William F. Sawin, and Chris Umans. On cap sets and the group-theoretic approach to matrix multiplication. Discrete Anal., 2017. URL: https://doi.org/10.19086/da.1245.
  13. Jop Briët. Subspaces of tensors with high analytic rank, 2019. URL: http://arxiv.org/abs/1908.04169.
  14. Peter Bürgisser, Michael Clausen, and M. Amin Shokrollahi. Algebraic complexity theory, volume 315 of Grundlehren der Mathematischen Wissenschaften. Springer-Verlag, Berlin, 1997. URL: https://doi.org/10.1007/978-3-662-03338-8.
  15. Ashok K. Chandra, Merrick L. Furst, and Richard J. Lipton. Multi-party protocols. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC 1983), pages 94-99, 1983. URL: https://doi.org/10.1145/800061.808737.
  16. Arkadev Chattopadhyay and Michael E. Saks. The power of super-logarithmic number of players. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014), volume 28, pages 596-603, 2014. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.596.
  17. Matthias Christandl, Omar Fawzi, Hoang Ta, and Jeroen Zuiddam. Larger corner-free sets from combinatorial degenerations, 2021. URL: http://arxiv.org/abs/2111.08262.
  18. Matthias Christandl, Péter Vrana, and Jeroen Zuiddam. Universal points in the asymptotic spectrum of tensors. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), pages 289-296, 2018. URL: https://doi.org/10.1145/3188745.3188766.
  19. Matthias Christandl, Péter Vrana, and Jeroen Zuiddam. Asymptotic tensor rank of graph tensors: beyond matrix multiplication. Comput. Complex., 28(1):57-111, 2019. URL: https://doi.org/10.1007/s00037-018-0172-8.
  20. H. Cohn, R. Kleinberg, B. Szegedy, and C. Umans. Group-theoretic algorithms for matrix multiplication. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), pages 379-388, 2005. URL: https://doi.org/10.1109/SFCS.2005.39.
  21. Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 1-6. ACM, 1987. Google Scholar
  22. Ernie Croot, Vsevolod F. Lev, and Péter Pál Pach. Progression-free sets in ℤ₄ⁿ are exponentially small. Annals of Mathematics, pages 331-337, 2017. URL: https://doi.org/10.4007/annals.2017.185.1.7.
  23. Harm Derksen. The G-stable rank for tensors, 2020. URL: http://arxiv.org/abs/2002.08435.
  24. Yves Edel. Extensions of generalized product caps. Designs, Codes and Cryptography, 31(1):5-14, 2004. URL: https://doi.org/10.1023/A:1027365901231.
  25. Jordan S. Ellenberg and Dion Gijswijt. On large subsets of 𝔽ⁿ_q with no three-term arithmetic progression. Ann. of Math., 185(1):339-343, 2017. URL: https://doi.org/10.4007/annals.2017.185.1.8.
  26. L. Gargano, J. Körner, and U. Vaccaro. Sperner capacities. Graphs and Combinatorics, 9(1):31-46, 1993. URL: https://doi.org/10.1007/BF01195325.
  27. L. Gargano, J. Körner, and U. Vaccaro. Qualitative independence and sperner problems for directed graphs. Journal of Combinatorial Theory, Series A, 61(2):173-192, 1992. URL: https://doi.org/10.1016/0097-3165(92)90016-N.
  28. W. T. Gowers and J. Wolf. Linear forms and higher-degree uniformity for functions on 𝔽ⁿ_p. Geom. Funct. Anal., 21(1):36-69, 2011. URL: https://doi.org/10.1007/s00039-010-0106-3.
  29. Vince Grolmusz. The BNS lower bound for multi-party protocols in nearly optimal. Inf. Comput., 112(1):51-54, 1994. URL: https://doi.org/10.1006/inco.1994.1051.
  30. Willem H. Haemers. On some problems of lovász concerning the shannon capacity of a graph. IEEE Trans. Inf. Theory, 25(2):231-232, 1979. URL: https://doi.org/10.1109/TIT.1979.1056027.
  31. Robert Kleinberg, William Sawin, and David Speyer. The growth rate of tri-colored sum-free sets. Discrete Anal., 2018. URL: https://doi.org/10.19086/da.3734.
  32. Swastik Kopparty, Guy Moshkovitz, and Jeroen Zuiddam. Geometric Rank of Tensors and Subrank of Matrix Multiplication. In Proceedings of the 35th Computational Complexity Conference (CCC 2020), pages 35:1-35:21, 2020. URL: https://doi.org/10.4230/LIPIcs.CCC.2020.35.
  33. Michael Lacey and William McClain. On an argument of Shkredov on two-dimensional corners. Online Journal of Analytic Combinatorics, 2007. URL: http://arxiv.org/abs/math/0510491.
  34. Nati Linial, Toni Pitassi, and Adi Shraibman. On the communication complexity of high-dimensional permutations. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), 124, page 54:1–54:20, 2019. URL: https://doi.org/10.4230/LIPIcs.ITCS.2019.54.
  35. Nati Linial and Adi Shraibman. An improved protocol for the exactly-n problem. In Valentine Kabanets, editor, 36th Computational Complexity Conference (CCC 2021), volume 200, pages 2:1-2:8, 2021. URL: https://doi.org/10.4230/LIPIcs.CCC.2021.2.
  36. Nati Linial and Adi Shraibman. Larger corner-free sets from better NOF Exactly-n protocols, 2021. URL: http://arxiv.org/abs/2102.00421.
  37. László Lovász. On the shannon capacity of a graph. IEEE Trans. Inf. Theory, 25(1):1-7, 1979. URL: https://doi.org/10.1109/TIT.1979.1055985.
  38. Shachar Lovett. The analytic rank of tensors and its applications. Discrete Anal., 2019. URL: http://arxiv.org/abs/1806.09179.
  39. Roy Meshulam. On subsets of finite abelian groups with no 3-term arithmetic progressions. Journal of Combinatorial Theory, Series A, 71(1):168-172, 1995. URL: https://doi.org/10.1016/0097-3165(95)90024-1.
  40. Eric Naslund. The partition rank of a tensor and k-right corners in 𝔽_qⁿ. Journal of Combinatorial Theory, Series A, 174:105190, 2020. URL: https://doi.org/10.1016/j.jcta.2019.105190.
  41. Eric Naslund and Will Sawin. Upper bounds for sunflower-free sets. Forum of Mathematics, Sigma, 5, 2017. URL: https://doi.org/10.1017/fms.2017.12.
  42. Claude E. Shannon. The zero error capacity of a noisy channel. IRE Trans. Inf. Theory, 2(3):8-19, 1956. URL: https://doi.org/10.1109/TIT.1956.1056798.
  43. I. D. Shkredov. On a generalization of Szemerédi’s theorem. Proc. London Math. Soc., 93(3):723-760, 2006. URL: https://doi.org/10.1017/S0024611506015991.
  44. I. D. Shkredov. On a problem of Gowers. Izvestiya: Mathematics, 70(2):385-425, 2006. URL: https://doi.org/10.1070/im2006v070n02abeh002316.
  45. Adi Shraibman. A note on multiparty communication complexity and the Hales–Jewett theorem. Information Processing Letters, 139:44-48, 2018. URL: https://doi.org/10.1016/j.ipl.2018.07.002.
  46. Volker Strassen. Relative bilinear complexity and matrix multiplication. J. Reine Angew. Math., 375/376:406-443, 1987. URL: https://doi.org/10.1515/crll.1987.375-376.406.
  47. Volker Strassen. Degeneration and complexity of bilinear maps: some asymptotic spectra. J. Reine Angew. Math, 413:127–180, 1991. URL: https://doi.org/10.1515/crll.1991.413.127.
  48. Terence Tao. A symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound. Tao’s blog post, 2016. URL: https://terrytao.wordpress.com.
  49. Terence Tao and Will Sawin. Notes on the “slice rank” of tensors. Tao’s blog post, 2016. URL: https://terrytao.wordpress.com/2016/08/24/notes-on-the-slice-rank-of-tensors/.
  50. Emanuele Viola. Guest column: Non-abelian combinatorics and communication complexity. SIGACT News, 50(3):52-74, 2019. URL: https://doi.org/10.1145/3364626.3364637.
  51. Andrew Chi-Chih Yao. Some complexity questions related to distributive computing. In Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing (STOC 1979), pages 209-213, 1979. URL: https://doi.org/10.1145/800135.804414.
  52. Yufei Zhao. Graph theory and additive combinatorics. Lecture Notes, 2019. URL: https://yufeizhao.com/gtac/.
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