Unifying known lower bounds via geometric complexity theory (Q2351393): Difference between revisions

From MaRDI portal

Jump to:navigation, search

Latest revision as of 04:57, 13 November 2024

scientific article

Language	Label	Description	Also known as
English	Unifying known lower bounds via geometric complexity theory	scientific article

Statements

scholarly article

0 references

Unifying known lower bounds via geometric complexity theory (English)

0 references

Joshua A. Grochow

0 references

Computational Complexity

0 references

publication date

23 June 2015

0 references

full work available at URL

https://arxiv.org/abs/1304.6333

0 references

zbMATH Keywords

lower bounds

0 references

circuit complexity

0 references

algebraic complexity

0 references

geometric complexity theory

0 references

representation theory

0 references

algebraic geometry

0 references

describes a project that uses

0 references

0 references

0 references

MaRDI profile type

MaRDI publication profile

0 references

FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science

0 references

0 references

A Uniform Circuit Lower Bound for the Permanent

0 references

Algorithms in real algebraic geometry

0 references

The complexity of partial derivatives

0 references

Relations between exact and approximate bilinear algorithms. Applications

0 references

\(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication

0 references

An insertion algorithm for catabolizability

0 references

Geometric Complexity Theory IV: nonstandard quantum group for the Kronecker problem

0 references

How to Generate Cryptographically Strong Sequences of Pseudorandom Bits

0 references

0 references

The Magma algebra system. I: The user language

0 references

Invariant Hilbert schemes

0 references

0 references

The complexity of factors of multivariate polynomials

0 references

Nonvanishing of Kronecker coefficients for rectangular shapes.

0 references

0 references

Deciding Positivity of Littlewood--Richardson Coefficients

0 references

Geometric complexity theory and tensor rank

0 references

Explicit lower bounds via geometric complexity theory

0 references

An Overview of Mathematical Issues Arising in the Geometric Complexity Theory Approach to $\mathbf{VP}\neq\mathbf{VNP}$

0 references

Limits on alternation trading proofs for time-space lower bounds

0 references

Complexity of some parametric integer and network programming problems

0 references

Sums of Like Powers of Multivariate Linear Forms

0 references

A hierarchy for nondeterministic time complexity

0 references

Matrix multiplication via arithmetic progressions

0 references

Algebraic geometry I: algebraic curves, algebraic manifolds and schemes. Transl. from the Russian by D. Coray and V. N. Shokurov

0 references

An improved time-space lower bound for tautologies

0 references

0 references

0 references

Time-space tradeoffs for satisfiability

0 references

Time-space lower bounds for satisfiability

0 references

0 references

Complexity of linear circuits and geometry

0 references

Symmetry, Representations, and Invariants

0 references

0 references

Lower bound for the approximative complexity

0 references

Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields.

0 references

0 references

Unifying known lower bounds via geometric complexity theory

0 references

É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é

0 references

Approaching the Chasm at Depth Four

0 references

Arithmetic Circuits: A Chasm at Depth 3

0 references

Semi-Algebraic Local-Triviality in Semi-Algebraic Mappings

0 references

On the Computational Complexity of Algorithms

0 references

Equations for Lower Bounds on Border Rank

0 references

0 references

Lower bounds for polynomials with algebraic coefficients

0 references

Marginal hitting sets imply super-polynomial lower bounds for permanent

0 references

Permanent does not have succinct polynomial size arithmetic circuits of constant depth

0 references

Circuit-size lower bounds and non-reducibility to sparse sets

0 references

0 references

Arithmetic circuits: the chasm at depth four gets wider

0 references

VPSPACE and a transfer theorem over the reals

0 references

Using Elimination Theory to construct Rigid Matrices

0 references

Geometry of orbits of permanents and determinants

0 references

The border rank of the multiplication of $2\times 2$ matrices is seven

0 references

Geometry and the complexity of matrix multiplication

0 references

New Lower Bounds for the Rank of Matrix Multiplication

0 references

New lower bounds for the border rank of matrix multiplication

0 references

Hypersurfaces with degenerate duals and the geometric complexity theory program

0 references

Lower bounds for the circuit size of partially homogeneous polynomials

0 references

Characterizing Valiant's algebraic complexity classes

0 references

The rank of \(n \times n\) matrix multiplication is at least \(3n^2 - 2\sqrt{2}n^{\frac{3}{2}} - 3n\)

0 references

0 references

0 references

Lower Bounds in a Parallel Model without Bit Operations

0 references

0 references

On P vs. NP and geometric complexity theory

0 references

Geometric Complexity Theory I: An Approach to the<i>P</i>vs.<i>NP</i>and Related Problems

0 references

Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties

0 references

0 references

Computational complexity of parametric linear programming

0 references

Hardness vs randomness

0 references

Lower bounds on arithmetic circuits via partial derivatives

0 references

Unimodality via Kronecker products

0 references

0 references

Multi-linear formulas for permanent and determinant are of super-polynomial size

0 references

0 references

Tensor-rank and lower bounds for arithmetic formulas

0 references

A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits

0 references

Lower bounds and separations for constant depth multilinear circuits

0 references

Lower bounds on the size of bounded depth circuits over a complete basis with logical addition

0 references

0 references

Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic

0 references

0 references

Partial and Total Matrix Multiplication

0 references

0 references

Depth-3 arithmetic circuits over fields of characteristic zero

0 references

Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten

0 references

Polynomials with Rational Coefficients Which are Hard to Compute

0 references

Rank and optimal computation of generic tensors

0 references

Relative bilinear complexity and matrix multiplication.

0 references

0 references

Improved Bounds for Reduction to Depth 4 and Depth 3

0 references

0 references

0 references

Multiplying matrices faster than coppersmith-winograd

0 references

Inductive time-space lower bounds for SAT and related problems

0 references

Time-space tradeoffs for counting NP solutions modulo integers

0 references

Natural Proofs versus Derandomization

0 references

Nonuniform ACC Circuit Lower Bounds

0 references

Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains

0 references

Decision tree complexity and Betti numbers

0 references

A bad network problem for the simplex method and other minimum cost flow algorithms

0 references

Identifiers

zbMATH Open document ID

0 references

10.1007/s00037-015-0103-x

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

zbMATH DE Number

0 references

0 references

0 references

0 references

DBLP publication ID

journals/cc/Grochow15

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2351393

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q2351393&oldid=37896111"