Matrix rigidity of random toeplitz matrices

DOI10.1145/2897518.2897633zbMath1373.68271OpenAlexW2413166304WikidataQ130371170 ScholiaQ130371170MaRDI QIDQ5361821

Avishay Tal, Oded Goldreich

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2897518.2897633

zbMATH Keywords

matrix rigiditymulti-linear circuitsmulti-linear functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Matrices over special rings (quaternions, finite fields, etc.) (15B33) Random matrices (algebraic aspects) (15B52) Toeplitz, Cauchy, and related matrices (15B05)

Related Items (3)

Matrix rigidity of random Toeplitz matrices ⋮ Fourier and circulant matrices are not rigid ⋮ Efficient Construction of Rigid Matrices Using an NP Oracle

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