Strong bounds for skew corner-free sets
arxiv(2024)
摘要
Motivated by applications to matrix multiplication algorithms, Pratt asked
(ITCS'24) how large a subset of [n] × [n] could be without containing a
skew-corner: three points (x,y), (x,y+h),(x+h,y') with h 0. We prove
any skew corner-free set has size at most exp(-Ω(log^1/12 n))·
n^2, nearly matching the best known lower bound of exp(-O(√(log
n)))· n^2 by Beker (arXiv'24). Our techniques generalize those of Kelley
and Meka's recent breakthrough on three-term arithmetic progression (FOCS'23),
answering a question of Beker (arXiv'24).
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要