[iasmath-seminars] Theoretical Computer Science/Discrete Math Seminars -- Week of October 9, 2017

[Anthony Pulido]

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:	http://www.math.ias.edu/seminars/abstract?event=128775



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:	http://www.math.ias.edu/seminars/abstract?event=129007

1 Barriers for rank methods in arithmetic complexity
    Rafael Oliveira

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.

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.

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

  * 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.)
  * 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.)

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.

Joint work with Klim Efremenko, Ankit Garg and Avi Wigderson

http://www.math.ias.edu/seminars/abstract?event=128775

2 Structural aspects of the null-cone problem in invariant theory
    Ankit Garg

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).

http://www.math.ias.edu/seminars/abstract?event=129007

Computer Science/Discrete Math Seminars can be found on our web page:

http://www.math.ias.edu/csdm
http://www.math.ias.edu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://imap.math.ias.edu/pipermail/iasmathsemo/attachments/20171004/3ff4d097/attachment.html>