Sep 18 – 29, 2023
Institut Henri Poincaré
Europe/Paris timezone

Superpolynomial lower bounds against low-depth algebraic circuits by Sébastien Tavenas

Sep 26, 2023, 11:00 AM
1h
Amphithéâtre Hermite / Darboux (Institut Henri Poincaré)

Amphithéâtre Hermite / Darboux

Institut Henri Poincaré

11 rue Pierre et Marie Curie 75005 Paris

Description

Abstract. An algebraic circuit computes a polynomial using addition and multiplication operators. Understanding the power of algebraic circuits has close connections to understanding general computation. Despite this, not many lower bounds are known for even simple Sigma Pi Sigma (product-depth 1) circuits. Before our work, the best known lower bound for product-depth 1 circuit was (slightly less than) cubic. No lower bounds were known for general product-depth 2 circuits.
In this work, we show the first superpolynomial lower bound for low-product-depth algebraic circuits. In the talk, we discuss the main results and present the proof ideas used in the proof of the superpolynomial lower bound for product-depth 1 circuits.
This talk is based on joint work with Nutan Limaye and Srikanth Srinivasan.

Presentation materials

There are no materials yet.