Strong bounds for skew corner-free sets

Michael Jaber,Shachar Lovett, Anthony Ostuni

arxiv(2024)

引用 0|浏览3
暂无评分
摘要
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
正在生成论文摘要