Tensors in Computer Science and Geometry 2014
2014-11-10..2014-11-14
Berkeley, United States
[Geometric Complexity Theory 2014, Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017), Semidefinite Optimization, Approximation and Applications 2014, Functional Inequalities in Discrete Spaces with Applications 2013, Information Theory, Learning and Big Data (Simons Institute, 2015), Lattices: Geometry, Algorithms and Hardness 2020]
who it's for
computational algebraic geometers, theoretical computer scientists, quantum information researchers, numerical linear algebra researchers, machine learning researchers working on tensors, complexity theorists
topics
critical rank-one approximations; tensor identifiability tests; maximal and typical ranks; nuclear norm hardness for tensors; matrix multiplication exponent techniques; multipartite entanglement classification; entanglement polytopes via moment map; tensor decompositions for latent variable models; orthogonal tensor decomposition; smoothed analysis of tensor decompositions; generalized singular values
| title | author | length |
|---|---|---|
| The Average Number of Critical Rank-One Approximations to a Tensor | Jan Draisma | 56m |
Counts the average number of real critical rank‑one approximations to a random tensor and gives an explicit formula: the expected count equals a constant times… | ||
| The Geometry of the Identifiability of Tensors | Luca Chiantini | 53m |
Uses projective geometry and Terracini's lemma to turn identifiability into concrete tests on secant varieties and tangent spans, implements a linear-algebra… | ||
| Elementary Results on Maximal, Generic and Typical Ranks | Grigoriy Blekherman | 59m |
Defines rank relative to a projective variety and works over C and R, proves max rank ≤ 2·generic rank over C and over R max rank ≤ 2·minimal typical rank, and… | ||
| Characters of Equivariant D-modules on Veronese Cones | Claudiu Raicu | 53m |
Veronese cone (affine image of v ↦ v^d) has local cohomology supported only in the codimension degree and for n>2 fails to be a set theoretic complete… | ||
| Siegel's Theorem, Edge Coloring, and a Holant Dichotomy | Jin-Yi Cai | 55m |
Proves that for every kappa ≥ 3 the problem of counting proper k-edge‑colorings on k‑regular graphs is #P‑complete, by reducing a Tutte/top‑polynomial… | ||
| NP-hardness of Nuclear Norms for Tensors | Shmuel Friedland | 55m |
Proves that computing tensor nuclear norms and deciding weak membership of the nuclear-ball are NP-hard to approximate by reducing from graph clique number… | ||
| Matrix Multiplication: Coppersmith-Winograd and Beyond | Virginia Vassilevska Williams | 55m |
Describes a concrete route from tensors to matrix multiplication exponent: use border rank q+2 bounds on a specific Coppersmith‑Winograd family, symmetrize and… | ||
| Towards a Complete Classification of Multipartite Entanglement | Gilad Gour | 56m |
Provides a concrete program: classify SLOCC entanglement by computing SL-invariant polynomials and using their ratios to decide physical orbits, not just… | ||
| Entanglement Polytopes | David Gross | 54m |
Characterizes which collections of single‑site spectra arise from globally pure multipartite states: for each SL‑orbit closure the image of the map sending a… | ||
| Tensors and Complexity in Quantum Information Science | Akimasa Miyake | 56m |
Claims that classification of pure multipartite entanglement reduces to algebraic geometry, using SL(2,C) local actions to label SLOCC orbit closures and… | ||
| Geometry and Upper Bounds for the Complexity of Matrix Multiplication | Joseph Landsberg | 56m |
Work over the complex numbers, treat matrix multiplication as a tensor, and use algebraic geometry (secant varieties, tangents) to get concrete algorithms and… | ||
| Approaches to Bounding the Exponent of Matrix Multiplication | Chris Umans | 58m |
Surveys known strategies that upper‑bound omega: handcrafted small tensor ranks and border ranks (Strassen 2.81, Coppersmith–Winograd to 2.38), packing many… | ||
| Powers of Tensors and Fast Matrix Multiplication | François Le Gall | 49m |
Claims a tiny improvement to the best known upper bound on the matrix multiplication exponent omega by applying the laser method (version 2.3) to high powers… | ||
| Progress on Strassen's Conjecture | Enrico Carlini | 52m |
Strassen's conjecture for symmetric tensors is advanced by proving additivity for forms that are linearly computable, using apolar methods: compute f⊥, choose… | ||
| On Strassen's Conjecture | Elisa Postinghel | 53m |
Proves additivity for three-way tensor rank whenever the smallest factor dimension is at most two (c1 ≤ 2), extending earlier cases that used conciseness and… | ||
| Rank, Border Rank, Smoothable Rank and Cactus Rank | Jaroslaw Buczynksi | 01h 01m |
Defines four concrete ranks for a point in P(W) relative to a variety X — usual rank, border rank, cactus rank (linear span of any finite subscheme) and… | ||
| Cactus Varieties of Cubic Forms: Apolar Local Artinian Gorenstein Rings | Alessandra Bernardi | 45m |
Proves a dimension formula for the cactus variety of cubic forms: for length r ≥ 17 the cactus and secant varieties have the same dimension (care needed for r… | ||
| Orthogonal Tensor Decomposition | Elina Robeva | 48m |
Characterizes which symmetric tensors admit an orthogonal decomposition, proves the orthonormal factors are exactly the robust eigenvectors that attract almost… | ||
| Tensor Decomposition, Sparse Representations and Applications | Bernard Mourrain | 58m |
Recasts symmetric tensor decomposition as recovering a truncated power-series (sum of exponentials) and proves a concrete algorithm: build the truncated… | ||
| Tensor Decompositions for Estimating Latent Variable Models | Sham Kakade | 56m |
Claims that tensors yield closed‑form, polynomial‑time estimators for several latent models under mild nondegeneracy: use the method of moments, whiten the… | ||
| Learning Mixture of Gaussians using Moment Tensor | Rong Ge | 52m |
Provides a polynomial-time, polynomial-sample algorithm that recovers parameters of a smoothed mixture of K general Gaussians by converting folded empirical… | ||
| Uniqueness of Tensor Decomposition and Identifiability in Mixture Models | Aditya Bhaskara | 47m |
Proves a robust version of Kruskal’s uniqueness: if the robust Kruskal ranks of the factor matrices sum to at least 2r+2, any tensor within ε' (where ε' is… | ||
| Smoothed Analysis of Tensor Decompositions | Aravindan Vijayaraghavan | 01h 00m |
Proves polynomial-time, noise-robust tensor decomposition under a smoothed-analysis model: add small Gaussian perturbations to component vectors, flatten… | ||
| Generalized Singular Values | Harm Derksen | 56m |
Defines singular values from the geometry of two dual norms and an inner product by plotting the Pareto subfrontier (X vs Y) and reading off piecewise linear… | ||
| nothing matches | ||