New Lower Bounds against Homogeneous Non-Commutative Circuits

2023/01/04 by Chatterjee, Prerona, Hrubeš, Pavel
#Computational Complexity (cs.CC) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2301.01676

Abstract

We give several new lower bounds on size of homogeneous non-commutative circuits. We present an explicit homogeneous bivariate polynomial of degree d which requires homogeneous non-commutative circuit of size Ω(d/log d). For an n-variate polynomial with n>1, the result can be improved to Ω(nd), if d≤ n, or Ω(nd (log n)/(log d)), if d≥ n. Under the same assumptions, we also give a quadratic lower bound for the ordered version of the central symmetric polynomial.

Related

• Observations on Symmetric Circuits
• On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant
• An exponential lower bound for homogeneous depth-5 circuits over finite fields
• On Lower Bounds for Constant Width Arithmetic Circuits
• On Lifting Lower Bounds for Noncommutative Circuits using Automata