[Colloquium] Reminder: Sen/MS Presentation/Feb 28, 2019

[Margaret Jaffey]

This is a reminder about Aritra Sen's MS Presentation tomorrow. Please
note the revised start time of 1:30 pm.

------------------------------------------------------------------------------
Date:  Thursday, February 28, 2019

Time:  1:30 PM

Place:  John Crerar Library 298

M.S. Candidate:  Aritra Sen

M.S. Paper Title: Lower bounds for Shallow Arithmetic circuits: A
Survey

Abstract:
Arithmetic complexity theory studies the problem of efficient
computation of polynomials using the basic operations of addition and
multiplication via \emph{arithmetic circuits}. Given a polynomial $f$
we are interested in finding the smallest arithmetic circuit that can
compute $f$. In 1983 in his seminal paper~\cite{valiant1983fast},
Valiant introduced the complexity classes VP and VNP, which are
algebraic analogues of the complexity classes P and NP respectively.
The problem of VP vs VNP, i.e. the separation of VP and VNP, is one of
the central problems in the field of arithmetic complexity. The VP vs
VNP problem can be solved by proving super-polynomial lower bounds for
arithmetic circuits. Most popular approaches to prove super-polynomial
lower bounds in arithmetic circuits are the Geometric Complexity
Theory program \cite{mulmuley2011p}, the real $\tau$-conjecture
\cite{burgisser2009defining}, polynomial identity testing and proving
lower bounds for small-depth or shallow circuits. This thesis focuses
on proving lower bounds for small-depth or shallow circuits. As such,
shallow circuits play an essential role in arithmetic complexity
theory, as they can simulate any circuit of any size, unlike in the
study of the Boolean case. More precisely, any degree-$d$ polynomial
that can be computed by a circuit of size $s$ can also be computed by
a depth-4 circuit with bottom fan-in bounded by $t$ and size
$s^{O(t+d/t)}$. This step is refereed to as \emph{depth reduction} in
the literature. Therefore, by proving lower bounds for small-depth
circuits, one could prove lower bounds for general circuits.

In 1997, Nisan and Wigderson introduced partial derivatives as a
strategy to prove lower bound results \cite{nisan1996lower} and
recently it has been used to prove some breakthrough lower bound
results for small-depth circuits. This thesis reviews those recent
lower bound results for some small-depth arithmetic circuits. We first
describe the general strategy to prove lower bound results using
partial derivative spaces of a polynomial, such as shifted partial
derivative space and projected shifted partial derivative space. We
then consider four concrete results where this strategy has been
applied: 1) Lower bound for depth four circuits with bounded bottom
fain-in computing the permanent by Gupta, Kamath, Kayal and
Saptharishi \cite{gupta2014approaching}; 2) Lower bound on depth four
circuits for a polynomial family in VNP by Kayal, Limaye, Saha and
Srinivasan~\cite{kayal2017exponential}, 3) An almost cubic lower bound
for depth three circuits by Kayal, Saha and
Tavenas~\cite{kayal2016almost}, and 4) Lower bound on depth four
circuits computing the iterated matrix multiplication by Kumar and
Saraf~\cite{kumar2017power}. The first lower bound result by Gupta et
al is a $\exp(\Omega({\sqrt{n}}))$ size lower bound for homogeneous
depth-4 circuits with bounded bottom fan-in of $\sqrt{n}$ computing
the permanent of a $n \times n$ matrix. Next result we consider by
Kayal et al. is a $2^{\Omega{(\sqrt{d}\log N )}}$ size lower bound for
homogeneous depth-4 formulas which computes a $N$-variate, degree-$d$
polynomial known to be in VNP. This result comes very close to the
threshold required to prove super-polynomial lower bounds for general
arithmetic circuits. If the lower bound of $2^{\Omega{(\sqrt{d}\log N
)}}$ in this result is improved to $2^{\omega{(\sqrt{d}\log N })}$
this would imply super-polynomial lower bound for general circuit and
would therefore separate VP from VNP. The third result by Kayal et
al., is an almost cubic lower bound for depth-3 circuits. Finally, we
present the result by Kumar and Saraf, which is a
$2^{\Omega{(\sqrt{n}\log n )}}$ size lower bound result for depth-4
homogeneous circuits computing iterated matrix multiplication --- the
$(1,1)$ entry in the product of n generic matrices of dimension
$n^{O(1)}$ --- which is a polynomial known to be in VP. The last
result shows that the depth reduction step discussed earlier is tight.

Aritra's advisor is Prof. Janos Simon

Login to the Computer Science Department website for details:
 https://newtraell.cs.uchicago.edu/phd/ms_announcements#aritrasen

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey            margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 156)               (773) 702-6011
The University of Chicago      http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=