Larger Corner-Free Sets from Combinatorial Degenerations
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Larger Corner-Free Sets from Combinatorial Degenerations. / Christandl, Matthias; Fawzi, Omar ; Ta, Hoang ; Zuiddam, Jeroen.
13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. p. 1-20 48 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 215).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Larger Corner-Free Sets from Combinatorial Degenerations
AU - Christandl, Matthias
AU - Fawzi, Omar
AU - Ta, Hoang
AU - Zuiddam, Jeroen
PY - 2022
Y1 - 2022
N2 - 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).
AB - 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).
U2 - 10.4230/LIPIcs.ITCS.2022.48
DO - 10.4230/LIPIcs.ITCS.2022.48
M3 - Article in proceedings
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 1
EP - 20
BT - 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik
T2 - 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Y2 - 31 January 2022 through 2 February 2022
ER -
ID: 290726290