Tata Institute of Fundamental Research
Lower Bounds for Shallow Circuits
STCS Seminar
Speaker:
Ramprasad Saptharishi (Tel Aviv University
Tel Aviv-Yafo
Israel)
Organiser:
Prahladh Harsha
Date:
Monday, 23 Nov 2015, 16:00 to 17:00
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: Over the last 3--4 years, there has been a sudden surge of results in arithmetic circuit lower bounds, specifically for shallow circuits (depth 3 or 4). The main motivation for studying depth-4 circuits is a result of Agrawal and Vinay (and subsequent strengthening by Koiran and Tavenas) that states that any arithmetic circuit of size s that computes an n-variate degree d polynomial can be simulated by a structured homogeneous depth-4 circuit of size n^{Omega (sqrt{d})}. Flipping this around, this implies that if we can find an explicit polynomial that requires such structured depth-4 circuits of size n^{omega(sqrt {d})}, then we would have proved lower bounds for general arithmetic circuits!
In 2013, in a joint work with Gupta, Kamath and Kayal, we showed a lower bound of 2^{Omega (sqrt{d})} for the dxd permanent or determinant using a technique called 'shifted partial derivatives' (introduced by [Kayal]). Subsequent to this result, there has been a sequence of improvements of various sorts (improving the lower bound, or dealing with a larger circuit class etc.) thereby improving our understanding of depth four circuits. The current state of the art is an n^{Omega(sqrt{d})} lower bound for the class of homogeneous depth-4circuits with no structural restrictions [Kayal-Limaye-Saha-Srinivasan, Kumar-Saraf].
In this talk, I shall give a brief overview of the progress made in the last 3 years and put the various results in context. Then, I shall present a recent work with Mrinal Kumar that gives an exponential lower bound for depth-5 circuits over small finite fields that combines the techniques developed so far with an old result of Grigoriev-Karpinski for depth-3 lower bounds.
| Speaker: | Ramprasad Saptharishi (Tel Aviv University Tel Aviv-Yafo Israel) |
| Organiser: | Prahladh Harsha |
| Date: | Monday, 23 Nov 2015, 16:00 to 17:00 |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: Over the last 3--4 years, there has been a sudden surge of results in arithmetic circuit lower bounds, specifically for shallow circuits (depth 3 or 4). The main motivation for studying depth-4 circuits is a result of Agrawal and Vinay (and subsequent strengthening by Koiran and Tavenas) that states that any arithmetic circuit of size s that computes an n-variate degree d polynomial can be simulated by a structured homogeneous depth-4 circuit of size n^{Omega (sqrt{d})}. Flipping this around, this implies that if we can find an explicit polynomial that requires such structured depth-4 circuits of size n^{omega(sqrt {d})}, then we would have proved lower bounds for general arithmetic circuits!
In 2013, in a joint work with Gupta, Kamath and Kayal, we showed a lower bound of 2^{Omega (sqrt{d})} for the dxd permanent or determinant using a technique called 'shifted partial derivatives' (introduced by [Kayal]). Subsequent to this result, there has been a sequence of improvements of various sorts (improving the lower bound, or dealing with a larger circuit class etc.) thereby improving our understanding of depth four circuits. The current state of the art is an n^{Omega(sqrt{d})} lower bound for the class of homogeneous depth-4circuits with no structural restrictions [Kayal-Limaye-Saha-Srinivasan, Kumar-Saraf].
In this talk, I shall give a brief overview of the progress made in the last 3 years and put the various results in context. Then, I shall present a recent work with Mrinal Kumar that gives an exponential lower bound for depth-5 circuits over small finite fields that combines the techniques developed so far with an old result of Grigoriev-Karpinski for depth-3 lower bounds.
In 2013, in a joint work with Gupta, Kamath and Kayal, we showed a lower bound of 2^{Omega (sqrt{d})} for the dxd permanent or determinant using a technique called 'shifted partial derivatives' (introduced by [Kayal]). Subsequent to this result, there has been a sequence of improvements of various sorts (improving the lower bound, or dealing with a larger circuit class etc.) thereby improving our understanding of depth four circuits. The current state of the art is an n^{Omega(sqrt{d})} lower bound for the class of homogeneous depth-4circuits with no structural restrictions [Kayal-Limaye-Saha-Srinivasan, Kumar-Saraf].
In this talk, I shall give a brief overview of the progress made in the last 3 years and put the various results in context. Then, I shall present a recent work with Mrinal Kumar that gives an exponential lower bound for depth-5 circuits over small finite fields that combines the techniques developed so far with an old result of Grigoriev-Karpinski for depth-3 lower bounds.