Matrix rigidity of random Toeplitz matrices
type: Item
instance of: scholarly article
title: Matrix rigidity of random Toeplitz matrices
zbMATH Open document ID: 1398.68237
author: Oded Goldreich
author: Avishay Tal
published in: Computational Complexity
publication date: 2018-08-03T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 15B05
Mathematics Subject Classification ID: 15B52
Mathematics Subject Classification ID: 68W20
zbMATH DE Number: 6913672
zbMATH Keywords: matrix rigidity
zbMATH Keywords: multi-linear functions
zbMATH Keywords: multi-linear circuits
MaRDI profile type: Publication
full work available at URL: s00037-016-0144-9
OpenAlex ID: W2510425678
Wikidata QID: Q64386969
cites work: Simple Constructions of Almost k-wise Independent Random Variables
cites work: A method for obtaining more than quadratic effective lower estimates of complexity of \(\pi\) schemes
cites work: Lower bounds on the bounded coefficient complexity of bilinear maps
cites work: A note on matrix rigidity
cites work: Computational Complexity
cites work: Matrix rigidity of random toeplitz matrices
cites work: Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields
cites work: Complexity Lower Bounds using Linear Algebra
cites work: On ε‐biased generators in NC0
cites work: Small-Bias Probability Spaces: Efficient Constructions and Applications
cites work: An improved exponential-time algorithm for k -SAT
cites work: Q4484662
cites work: On the Complexity of Matrix Product
cites work: A remark on matrix rigidity
cites work: Q4164821
DOI: 10.1007/S00037-016-0144-9
description: scientific article; zbMATH DE number 6913672