Unbalancing Sets and an Almost Quadratic Lower Bound for Syntactically\n Multilinear Arithmetic Circuits

2017/08/07 by Alon, Noga, Kumar, Mrinal, Volk, Ben Lee
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1708.02037

openalex publication_date 2017/08/07 · openalex created_date 2019/08/13 · openalex updated_date 2026/07/28

Abstract

We prove a lower bound of \Ω(n²/\log² n) on the size of any\nsyntactically multilinear arithmetic circuit computing some explicit\nmultilinear polynomial f(x₁, \…, x_n). Our approach expands and improves\nupon a result of Raz, Shpilka and Yehudayoff ([RSY08]), who proved a lower\nbound of \Ω(n^4/3/\log² n) for the same polynomial. Our improvement\nfollows from an asymptotically optimal lower bound for a generalized version of\nGalvin's problem in extremal set theory.\n

Related

• Some Lower Bound Results for Set-Multilinear Arithmetic Computations
• Towards Optimal Depth Reductions for Syntactically Multilinear Circuits
• Lower Bounds for Special Cases of Syntactic Multilinear ABPs
• Arithmetic Circuit Lower Bounds via MaxRank
• Limitations of sum of products of Read-Once Polynomials