Algorithms and Complexity in Algebraic Geometry Boot Camp 2014
2014-09-02..2014-09-05
Berkeley, United States
| title | author | length |
|---|---|---|
| Introduction to Geometric Complexity Theory I | Laurent Manivel | 01h 19m |
Compares determinant and permanent by giving explicit constructions and bounds: a graph-theoretic adjacency-weighted graph with 2^n−1 vertices yields a formula… | ||
| Circuits of Bounded Depth | Klim Efremenko | 01h 31m |
Claims an exponential lower bound: any depth-d arithmetic circuit computing the n×n determinant needs size at least exp(Ω(n^{1/d})), proven by exhibiting… | ||
| Solving Polynomials I | Jonathan Hauenstein | 01h 12m |
Compares symbolic elimination (Gröbner/resultant reductions to easier systems) with numeric homotopy continuation and path tracking, using homotopy… | ||
| Writing Down Polynomials via Representation Theory I | Christian Ikenmeyer | 01h 14m |
Christian Ikenmeyer, Texas A&M University
Algebraic Geometry Boot Camp
http://simons.berkeley.edu/talks/christian-ikenmeyer-2014-09-02 | ||
| Tensor Decomposition I | Luke Oeding | 01h 09m |
Defines nonsymmetric tensors as multidimensional arrays or elements of A⊗B⊗C, emphasizes NP‑hardness but constant‑time solvability for fixed dimensions, and… | ||
| Matrix Multiplication | Virginia Vassilevska Williams | 01h 44m |
Asks how fast N×N multiplication can be done and connects concrete algebraic claims to algorithms: uses rank vs border rank (Strassen shows 2×2 rank ≤7; a… | ||
| Real Algebraic Geometry | Cynthia Vinzant | 01h 15m |
Real solutions to polynomial equalities behave non-generic: a univariate quadratic has 0 or 2 real roots, two plane cubics can meet in up to 9 real points and… | ||
| Tensors vs Entanglement | Matthias Christandl | 01h 22m |
Quick primer on entanglement transformability: bipartite states are comparable by Schmidt coefficients majorization (Nielsen) so LOCC conversion iff the… | ||
| Introduction to Geometric Complexity Theory II | Laurent Manivel | 01h 08m |
Program reframes permanent-versus-determinant as whether the padded permanent lies in the orbit closure of det under GL_{n^2+1} and uses algebraic geometry… | ||
| Solving Polynomials II | Jonathan Hauenstein | 01h 16m |
Homotopy continuation constructs explicit start systems and traces solution paths so each isolated root receives exactly as many paths as its multiplicity… | ||
| Matrix Rigidity | Satya Lokam | 01h 37m |
Defines rigidity as the minimum entries to change to drop rank to R and ties large rigidity for R = εN to impossibility of depth‑log N, linear‑size linear… | ||
| Tensor Decomposition II | Luke Oeding | 01h 12m |
Claims that low border rank is certified by specific minors and by two families of equations (flattenings plus Strassen-type polynomials), and gives a concrete… | ||
| Matrix Factorizations | Dave Eisenbud | 01h 34m |
Defines a matrix factorization concretely as matrix factorization = (A,B) with AB = f·Id, proves nontrivial MFs exist for any power series f in the maximal… | ||
| Writing Down Polynomials via Representation Theory II | Christian Ikenmeyer | 01h 12m |
Constructs explicit highest-weight tensors for Sym^d(Sym^n(C^{n^2})^) and writes polynomials as symmetric tensor contraction so evaluation becomes a sum of… | ||
| Condition | Peter Bürgisser | 01h 32m |
Peter Bürgisser, University of Berlin
Algebraic Geometry Boot Camp
http://simons.berkeley.edu/talks/peter-burgisser-2014-09-05 | ||
| nothing matches | ||