Complexity of linear circuits and geometry

DOI10.1007/s10208-015-9258-8zbMath1345.68157arXiv1310.1362OpenAlexW1984256153MaRDI QIDQ300885

Fulvio Gesmundo, Jonathan D. Hauenstein, Christian Ikenmeyer, Joseph M. Landsberg

Publication date: 29 June 2016

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1310.1362

zbMATH Keywords

discrete Fourier transformVandermonde matrixCauchy matrixmatrix rigidity

Mathematics Subject Classification ID

Numerical methods for discrete and fast Fourier transforms (65T50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Toeplitz, Cauchy, and related matrices (15B05)

Related Items (4)

New applications of the polynomial method: The cap set conjecture and beyond ⋮ Algebraic compressed sensing ⋮ Geometric complexity theory: an introduction for geometers ⋮ Unifying known lower bounds via geometric complexity theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A remark on matrix rigidity
• On matrix rigidity and locally self-correctable codes
• A note on matrix rigidity
• Rigidity of a simple extended lower triangular matrix
• The red book of varieties and schemes. Includes the Michigan lectures (1974) on ``Curves and their Jacobians.
• Improved lower bounds on the rigidity of Hadamard matrices
• On the rigidity of Vandermonde matrices
• Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
• Algebraic Geometry. I: Complex projective varieties.
• Matrix rigidity
• The connection between representation theory and Schubert calculcus
• Using Elimination Theory to construct Rigid Matrices
• Degrees of Projections of Rank Loci
• Complexity Lower Bounds using Linear Algebra
• Lower Bounds on Matrix Rigidity Via a Quantum Argument
• Superconcentrators
• Theory and Applications of Models of Computation

This page was built for publication: Complexity of linear circuits and geometry