Geometric Complexity Theory 2014
2014-09-15..2014-09-19
Berkeley, United States
[Tensors in Computer Science and Geometry 2014, Neo-Classical Methods in Discrete Analysis 2013, Interactive Complexity 2018, Lattices: Geometry, Algorithms and Hardness 2020, The Classification Program of Counting Complexity, Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017)]
| title | author | length |
|---|---|---|
| Tutorial 1: The GCT Chasm I | Ketan Mulmuley | 01h 31m |
Claims that a strengthened permanent-versus-determinant conjecture forces derandomization of Noether’s Normalization for the orbit closure of the determinant… | ||
| Tutorial 2: Algorithmic Invariant Theory | Bernd Sturmfels | 01h 19m |
Defines when a group is reductive by the existence of a Reynolds operator and proves Hilbert's 1890 finite-generation for reductive matrix groups; gives the… | ||
| Tutorial 3: Geometric Invariant Theory | Laurent Manivel | 01h 22m |
States that for reductive groups the invariant ring is finitely generated, so Spec of that ring gives a categorical quotient that is constant on orbits… | ||
| Tutorial 4: GCT and Matrix Multiplication | Peter Bürgisser | 01h 28m |
Tutorial lays out concrete GCT tools for tensors: defines border rank and gives explicit criteria using polynomial highest weight vectors to test whether a… | ||
| Orbit Closures | Vladimir Popov | 01h 00m |
Gives a concrete algorithm that decides whether one linear G-orbit lies in the closure of another by producing explicit regular functions from a dominant… | ||
| Tutorial 5: The GCT Chasm II | Ketan Mulmuley | 01h 22m |
Argues concrete steps toward bridging the GCT chasm by linking determinant vs permanent complexity to explicit representation-theoretic gadgets and algorithmic… | ||
| Inequalities and Reductions for Nonzero Kronecker Coefficients | Nicolas Ressayre | 55m |
Provides explicit linear inequalities and elementary reduction algorithm rules that decide when a Kronecker coefficient can be nonzero, built from geometric… | ||
| Computing Multiplicities of Lie Group Representations | Matthias Christandl | 57m |
Algorithm computes branching multiplicities when group/homomorphism and number of diagram rows are fixed, running in poly-time for fixed rank (polynomial in… | ||
| Generalized Knuth Equivalence for Schur Positivity | Jonah Blasiak | 56m |
Generalizes Knuth equivalence inside the plactic algebra to larger quotients and shows that the noncommutative Jacobi–Trudi element J_lambda equals a positive… | ||
| Matrix Rank – Extensions, Applications and Open Problems | Avi Widgerson | 01h 00m |
Surveys concrete rank questions and what is known: matrix rigidity asks for explicit n×n A with r·s > n^{2+ε} (Hadamard gives r·s≈n^2), and no explicit… | ||
| A Survey of Counting Dichotomies and Holographic Algorithms | Jin-Yi Cai | 57m |
Survey reports that reductions to weighted perfect matching and matchgates produce unexpected polynomial-time algorithms for many #P problems on planar inputs… | ||
| Approximate Counting via Correlation Decay | Pinyan Lu | 48m |
Gives a concrete criterion (the uniqueness/contracting condition) that guarantees a deterministic FPTAS for partition functions and vertex marginals of… | ||
| Asymptotic Spectra: Old and New Insights | Markus Bläser | 58m |
Introduces the asymptotic spectrum of tensors as equivalence classes in a commutative semiring, links it to the matrix multiplication exponent ω (Strassen… | ||
| Approaches to Bounding the Exponent of Matrix Multiplication | Chris Umans | 01h 02m |
Survey describes embedding n×n multiplication into group algebras and into commutative association schemes, using the triple product property to reduce to… | ||
| Geometric Complexity Theory and Tensor Rank | Christian Ikenmeyer | 43m |
Generalizes Strassen’s degree-4 vanishing equations to degree 3k+1 polynomials that vanish on tensors of border rank ≤ 3k, producing a nontrivial lower bound… | ||
| A Study of the Representations Supported by the Orbit Closure of the Determinant | Shrawan Kumar | 01h 06m |
Compares the GL(E)-orbit closure of the determinant and the GL(E)-orbit closure of a basis-dependent permanent-like polynomial p_{m,n}, defines M̄_n (smallest… | ||
| Dealing with Orbit Closures in Representations with Finitely Many Orbits | Jerzy Weyman | 56m |
Classifies irreducible representations whose action has finitely many orbits, identifies the relevant graded piece G1 (examples like ∧^3 C^7), and converts… | ||
| Fano Schemes of Determinants and Permanents | Nathan Ilten | 42m |
Gives a precise criterion for when the Fano scheme F_k(D_n) of k-planes in the determinant hypersurface is connected: components come from compression space… | ||
| Essentially Optimal Interactive Certificates in Linear Algebra | Erich Kaltofen | 57m |
Claims interactive, essentially linear time verification procedures for integer linear-algebra outputs (rank, determinant, characteristic polynomial) using… | ||
| A Survey of Recent Results on Depth Reduction and Lower Bounds for Arithmetic Circuits | Neeraj Kayal | 56m |
Presents an explicit family — the iterated matrix multiplication polynomials (trace of product of D matrices, matrices of size about D^{10}) — and proves any… | ||
| Hilbert Functions, Shallow Circuits, and Other Approaches to GCT | Joseph Landsberg | 01h 01m |
Goal is separating permanent from determinant by finding GL-modules of polynomials that vanish on the determinant orbit closure but not on the (padded)… | ||
| Combinatorics and Complexity of Kronecker Coefficients | Greta Panova | 59m |
Defines Kronecker coefficients g(λ,μ,ν) as tensor-product multiplicities and states key complexity claims: positivity decision is conjectured polynomial but… | ||
| Plethysm and Lattice Point Counting | Mateusz Michalek | 45m |
Computes plethysm characters by translating coefficients to lattice-point counts in polytopes and uses Barvinok via the ISL library to get explicit chamber… | ||
| Wrap Session part 1 | Jerzy Weyman | 48m |
Defines quivers as directed graphs, fixes a field K, and treats representations as tuples of finite matrices with a dimension vector; constructs the canonical… | ||
| Wrap Session part 2 | Ketan Mulmuley | 01h 10m |
Argues that Newton degenerations of symbolic determinants coming from quiver semi‑invariants sit inside the orbit closure of the determinant, and constructs… | ||
| Wrap Session Discussion | 39m | |
Argues that studying elementary symmetric polynomial representations is more tractable than orbit-closure statements about determinant versus permanent, shows… | ||
| nothing matches | ||