Seminar Announcement
Date: Friday, 25 April 2025
Time: 11:30 AM
Venue: Seminar Hall
New Lower Bounds against Homogeneous Non-Commutative Circuits
Prerona Chatterjee
IIT Madras.
25-04-25

---

Abstract

We give new lower bound 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 \Omega(d/log d). For an n-variate polynomial with n1, the result can be improved to \Omega(nd) if d is bounded by n, or \Omega(nd log n/log d) if d is more than n. Under the same assumptions, we also give a quadratic lower bound for the ordered version of the central symmetric polynomial.

This is a joint work with Pavel Hrubes.