Unifying known lower bounds via geometric complexity theory
From MaRDI portal
Publication:2351393
DOI10.1007/s00037-015-0103-xzbMath1329.68123arXiv1304.6333OpenAlexW2055240703WikidataQ59412423 ScholiaQ59412423MaRDI QIDQ2351393
Publication date: 23 June 2015
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1304.6333
representation theorylower boundscircuit complexityalgebraic complexityalgebraic geometrygeometric complexity theory
Group actions on varieties or schemes (quotients) (14L30) Actions of groups on commutative rings; invariant theory (13A50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring ⋮ Some complete and intermediate polynomials in algebraic complexity theory ⋮ A Homological Theory of Functions: Nonuniform Boolean Complexity Separation and VC Dimension Bound Via Algebraic Topology, and a Homological Farkas Lemma ⋮ Barriers for Rank Methods in Arithmetic Complexity ⋮ The method of shifted partial derivatives cannot separate the permanent from the determinant ⋮ Geometric complexity theory V: Efficient algorithms for Noether normalization ⋮ Unnamed Item ⋮ Unifying known lower bounds via geometric complexity theory ⋮ Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
Uses Software
Cites Work
- Multi-linear formulas for permanent and determinant are of super-polynomial size
- Natural proofs
- Decision tree complexity and Betti numbers
- Algorithms in real algebraic geometry
- Depth-3 arithmetic circuits over fields of characteristic zero
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Complexity of linear circuits and geometry
- Geometry of orbits of permanents and determinants
- The rank of \(n \times n\) matrix multiplication is at least \(3n^2 - 2\sqrt{2}n^{\frac{3}{2}} - 3n\)
- Arithmetic circuits: the chasm at depth four gets wider
- Unimodality via Kronecker products
- Limits on alternation trading proofs for time-space lower bounds
- Nonvanishing of Kronecker coefficients for rectangular shapes.
- Lower bounds and separations for constant depth multilinear circuits
- VPSPACE and a transfer theorem over the reals
- An improved time-space lower bound for tautologies
- An insertion algorithm for catabolizability
- Matrix multiplication via arithmetic progressions
- Time-space tradeoffs for counting NP solutions modulo integers
- Rank and optimal computation of generic tensors
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Lower bounds for polynomials with algebraic coefficients
- Relations between exact and approximate bilinear algorithms. Applications
- The complexity of partial derivatives
- \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication
- Algebraic geometry I: algebraic curves, algebraic manifolds and schemes. Transl. from the Russian by D. Coray and V. N. Shokurov
- Hardness vs randomness
- The Magma algebra system. I: The user language
- Lower bounds on arithmetic circuits via partial derivatives
- A hierarchy for nondeterministic time complexity
- Time-space tradeoffs for satisfiability
- Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields.
- The complexity of factors of multivariate polynomials
- Lower bound for the approximative complexity
- Permanent does not have succinct polynomial size arithmetic circuits of constant depth
- Hypersurfaces with degenerate duals and the geometric complexity theory program
- Unifying known lower bounds via geometric complexity theory
- Lower bounds for the circuit size of partially homogeneous polynomials
- Inductive time-space lower bounds for SAT and related problems
- Characterizing Valiant's algebraic complexity classes
- Éléments de géométrie algébrique. IV: Étude locale des schémas et des morphismes de schémas. (Première partie). Rédigé avec la colloboration de J. Dieudonné
- Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
- Geometric Complexity Theory I: An Approach to thePvs.NPand Related Problems
- Natural Proofs versus Derandomization
- Arithmetic Circuits: A Chasm at Depth 3
- Marginal hitting sets imply super-polynomial lower bounds for permanent
- Improved Bounds for Reduction to Depth 4 and Depth 3
- Tensor-rank and lower bounds for arithmetic formulas
- Using Elimination Theory to construct Rigid Matrices
- New lower bounds for the border rank of matrix multiplication
- Invariant Hilbert schemes
- On P vs. NP and geometric complexity theory
- An Overview of Mathematical Issues Arising in the Geometric Complexity Theory Approach to $\mathbf{VP}\neq\mathbf{VNP}$
- Nonuniform ACC Circuit Lower Bounds
- Circuit-size lower bounds and non-reducibility to sparse sets
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- The border rank of the multiplication of $2\times 2$ matrices is seven
- A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
- Time-space lower bounds for satisfiability
- Geometry and the complexity of matrix multiplication
- Symmetry, Representations, and Invariants
- Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties
- Complexity of some parametric integer and network programming problems
- Relative bilinear complexity and matrix multiplication.
- Computational complexity of parametric linear programming
- Partial and Total Matrix Multiplication
- Semi-Algebraic Local-Triviality in Semi-Algebraic Mappings
- Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains
- Lower Bounds in a Parallel Model without Bit Operations
- Sums of Like Powers of Multivariate Linear Forms
- A Uniform Circuit Lower Bound for the Permanent
- A bad network problem for the simplex method and other minimum cost flow algorithms
- Polynomials with Rational Coefficients Which are Hard to Compute
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
- Geometric Complexity Theory IV: nonstandard quantum group for the Kronecker problem
- On the Computational Complexity of Algorithms
- Deciding Positivity of Littlewood--Richardson Coefficients
- Multiplying matrices faster than coppersmith-winograd
- Equations for Lower Bounds on Border Rank
- New Lower Bounds for the Rank of Matrix Multiplication
- Geometric complexity theory and tensor rank
- Explicit lower bounds via geometric complexity theory
- Approaching the Chasm at Depth Four
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
