Matrix rigidity of random Toeplitz matrices

DOI10.1007/s00037-016-0144-9zbMath1398.68237OpenAlexW2510425678WikidataQ64386969 ScholiaQ64386969MaRDI QIDQ1653338

Avishay Tal, Oded Goldreich

Publication date: 3 August 2018

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-016-0144-9

zbMATH Keywords

matrix rigiditymulti-linear circuitsmulti-linear functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random matrices (algebraic aspects) (15B52) Randomized algorithms (68W20) Toeplitz, Cauchy, and related matrices (15B05)

Related Items (3)

Fourier and Circulant Matrices are Not Rigid ⋮ Improved bounds on the an-complexity of \(O(1)\)-linear functions ⋮ On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions

Cites Work

• Unnamed Item
• Unnamed Item
• A remark on matrix rigidity
• A note on matrix rigidity
• A method for obtaining more than quadratic effective lower estimates of complexity of \(\pi\) schemes
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Complexity Lower Bounds using Linear Algebra
• An improved exponential-time algorithm for k -SAT
• Lower bounds on the bounded coefficient complexity of bilinear maps
• Simple Constructions of Almost k-wise Independent Random Variables
• On the Complexity of Matrix Product
• Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields
• Matrix rigidity of random toeplitz matrices
• On ε‐biased generators in NC⁰
• Computational Complexity

This page was built for publication: Matrix rigidity of random Toeplitz matrices