<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=utf-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<pre>INSTITUTE FOR ADVANCED STUDY
School of Mathematics
Princeton, NJ 08540
Theoretical Computer Science/Discrete Math Seminars
Week of October 9, 2017
--------------
To view mathematics in titles and abstracts, please click on the talk's link.
--------------
Monday, October 9
Computer Science/Discrete Mathematics Seminar I
Topic: Barriers for rank methods in arithmetic complexity
Speaker: Rafael Oliveira, University of Toronto
Time/Room: 11:00am - 12:15pm/West Building Lecture Hall
Abstract Link: <a href="http://www.math.ias.edu/seminars/abstract?event=128775">http://www.math.ias.edu/seminars/abstract?event=128775</a>
Tuesday, October 10
Computer Science/Discrete Mathematics Seminar II
Topic: Structural aspects of the null-cone problem in invariant theory
Speaker: Ankit Garg, Microsoft Research
Time/Room: 10:30am - 12:30pm/West Building Lecture Hall
Abstract Link: <a href="http://www.math.ias.edu/seminars/abstract?event=129007">http://www.math.ias.edu/seminars/abstract?event=129007</a>
</pre>
1 Barriers for rank methods in arithmetic complexity
<br>
Rafael Oliveira
<br>
<br>
<p>Arithmetic complexity is considered (for many good reasons)
simpler to understand than Boolean complexity. And indeed, we seem
to have significantly more lower bound techniques and results in
arithmetic complexity than in Boolean complexity. Despite many
successes and rapid progress, however, foundational challenges,
like proving super-polynomial lower bounds on circuit or formula
size for explicit polynomials, or super-linear lower bounds on
explicit 3-dimensional tensors, remain elusive.</p>
<p>At the same time (and possibly for similar reasons), we have
plenty more excuses, in the form of “barrier results” for failing
to prove basic lower bounds in Boolean complexity than in
arithmetic complexity. Efforts to find barriers to arithmetic
lower bound techniques seem harder, and despite some attempts we
have no excuses of similar quality for these failures in
arithmetic complexity.</p>
<p>In this talk we will give the first unconditional barriers for
rank methods, which were long recognized as encompassing and
abstracting almost all known arithmetic lower bounds to-date,
including the most recent impressive successes. In this talk, we
will show that</p>
<ul>
<li>Rank methods cannot prove better than $\Omega_d(n^{\lfloor d/2
\rfloor})$ lower bound on the tensor rank of any $d$-dimensional
tensor of side $n$. (In particular, they cannot prove
super-linear, indeed even $> 8n$ tensor rank lower bounds for
any 3-dimensional tensors.)</li>
<li>Rank methods cannot prove better than $\Omega_d(n^{\lfloor d/2
\rfloor})$ lower bound on the Waring rank of any $n$-variate
polynomial of degree $d$. (In particular, they cannot prove such
lower bounds on stronger models, including depth-3 circuits.)</li>
</ul>
<p>The bounds above nearly match the best explicit bounds we know
for these models, and hence offer an explanation why the rank
methods got stuck there. Time permitting, we will discuss how
these techniques can be extended to barriers for other arithmetic
models.</p>
<p>Joint work with Klim Efremenko, Ankit Garg and Avi Wigderson</p>
<a href="http://www.math.ias.edu/seminars/abstract?event=128775">http://www.math.ias.edu/seminars/abstract?event=128775</a><br>
<br>
2 Structural aspects of the null-cone problem in invariant theory
<br>
Ankit Garg
<br>
<br>
<p>Invariant theory studies the actions of groups on vector spaces
and what polynomial functions remain invariant under these
actions. An important object related to a group action is the null
cone, which is the set of common zeroes of all homogeneous
invariant polynomials. I will talk about the structural aspects of
the null cone from a computational and optimization perspective.
These will include the Hilbert-Mumford and Kempf-Ness theorems
which imply that null cone membership is in NP intersect coNP
(ignoring bit-size issues). I will explain how this should be
thought of as a noncommutative generalization of linear
programming duality, which arises when the group is commutative
(group of invertible diagonal matrices aka algebraic tori).
</p>
<a href="http://www.math.ias.edu/seminars/abstract?event=129007">http://www.math.ias.edu/seminars/abstract?event=129007</a><br>
<br>
Computer Science/Discrete Math Seminars can be found on our web
page:<br>
<br>
<a href="http://www.math.ias.edu/csdm">http://www.math.ias.edu/csdm</a><br>
<a href="http://www.math.ias.edu">http://www.math.ias.edu</a>
</body>
</html>