Seminar • Algorithms and Complexity — Can Algebraic Circuit Lower Bounds Have Easy Proofs?

Wednesday, May 27, 2020 — 10:30 AM EDT

Please note: This seminar will be given online.

Anamay Tengse
Tata Institute of Fundamental Research (TIFR)

The field of Algebraic Circuit Complexity studies how succinctly one can represent explicit multivariate polynomials. Algebraic circuits (analogous to boolean circuits) are the most natural model for computing polynomials. A central question in this field is therefore to find explicit polynomials that require “large” algebraic circuits. The best known lower bounds for general circuits are due to Baur and Strassen (1983) and Smolenksy (1997), both of which give (tight) Omega(n log d) lower bounds for an explicit n-variate polynomial of degree d. Although there has been considerable progress in proving lower bounds for simpler models, there has not been much progress for more general computational classes. This lack of progress over the last few decades leads to the following question. Are most of the current techniques incapable of proving a superpolynomial lower bound for general circuits?

Almost all the current techniques for showing a lower bound against a class of circuits C, can also be used to obtain what is called a “defining equation” for the class C that is also easy to compute. Thus, the above question is equivalent to asking whether the class of polynomials computable by polynomial-sized circuits has efficiently computable defining equations.

Based on the important work of Razborov and Rudich (1997) in the boolean world, Forbes, Shpilka, and Volk (2018), and Grochow, Kumar, Saks and Saraf (2017) introduced the framework of Algebraically Natural Proofs. They showed that under a certain derandomization assumption, such defining equations do not exist; thereby hinting towards the existence of a barrier for proving lower bounds. We show that there \emph{are} efficiently computable defining equations for the class of polynomials with bounded coefficients that are computable by polynomial-sized circuits. This provides evidence \emph{against} the existence of a barrier for proving lower bounds.

Joint work with Prerona Chatterjee (TIFR, Mumbai), Mrinal Kumar (IITB, Mumbai), C. Ramya (TIFR, Mumbai) and Ramprasad Saptharishi (TIFR, Mumbai).

To join this seminar on Zoom, please go to https://zoom.us/j/96521895099

Meeting ID: 965 2189 5099

Location
Online seminar
200 University Avenue West

Waterloo, ON N2L 3G1

July 2020

S M T W T F S
28
29
30
1
3
4
5
7
10
11
12
13
14
15
16
17
18
19
20
21
24
25
26
27
28
29
30
31
1
1. 2020 (133)
1. August (2)
2. July (11)
3. June (19)
4. May (17)
5. April (20)
6. March (17)
7. February (25)
8. January (22)
2. 2019 (255)
1. December (21)
2. November (25)
3. October (16)
4. September (20)
5. August (18)
6. July (12)
7. June (23)
8. May (23)
9. April (32)
10. March (25)
11. February (16)
12. January (24)
3. 2018 (220)
4. 2017 (36)
5. 2016 (21)
6. 2015 (36)
7. 2014 (33)
8. 2013 (23)
9. 2012 (4)
10. 2011 (1)
11. 2010 (1)
12. 2009 (1)
13. 2008 (1)