2023 - T3 - WS1 - Fundamental algorithms and algorithmic complexity

Collection 2023 - T3 - WS1 - Fundamental algorithms and algorithmic complexity

Organizer(s) van der Hoeven, Joris ; Giesbrecht, Mark ; Koiran, Pascal ; Villard, Gilles
Date(s) 25/09/2023 - 29/09/2023
linked URL https://indico.math.cnrs.fr/event/8113/
7 17

Superpolynomial lower bounds against low-depth algebraic circuits

By Sébastien Tavenas

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.

Information about the video

Citation data

  • DOI 10.57987/IHP.2023.T3.WS1.007
  • Cite this video Tavenas, Sébastien (26/09/2023). Superpolynomial lower bounds against low-depth algebraic circuits. IHP. Audiovisual resource. DOI: 10.57987/IHP.2023.T3.WS1.007
  • URL https://dx.doi.org/10.57987/IHP.2023.T3.WS1.007

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow




Register

  • Bookmark videos
  • Add videos to see later &
    keep your browsing history
  • Comment with the scientific
    community
  • Get notification updates
    for your favorite subjects
Give feedback