Min-rank conjecture for log-depth circuits
type: Item
instance of: scholarly article
title: Min-rank conjecture for log-depth circuits
zbMATH Open document ID: 1247.94074
author: Georg Schnitger
author: Stasys Jukna
published in: Journal of Computer and System Sciences
publication date: 2012-01-11T00:00:00Z
Mathematics Subject Classification ID: 94C10
Mathematics Subject Classification ID: 94B05
zbMATH DE Number: 5996364
zbMATH Keywords: Boolean circuits
zbMATH Keywords: partial matrix
zbMATH Keywords: matrix completion
zbMATH Keywords: min-rank
zbMATH Keywords: matrix rigidity
zbMATH Keywords: sum-sets
zbMATH Keywords: Cayley graphs
zbMATH Keywords: error-correcting codes
MaRDI profile type: Publication
full work available at URL: j.jcss.2009.09.003
OpenAlex ID: W1997575430
Wikidata QID: Q123282575
cites work: Superconcentrators of depths 2 and 3; odd levels help (rarely)
cites work: Linear Circuits over $\operatorname{GF}(2)$
cites work: Q3412385
cites work: Q3831127
cites work: A note on matrix rigidity
cites work: Q3487569
cites work: Entropy of operators or why matrix multiplication is hard for depth-two circuits
cites work: On the rigidity of Vandermonde matrices
cites work: Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
cites work: Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
cites work: The Linear Complexity of Computation
cites work: Superconcentrators
cites work: Superconcentrators of depth 2
cites work: Communication in bounded depth circuits
cites work: Q3990226
cites work: On shifting networks
cites work: Boolean Circuits, Tensor Ranks, and Communication Complexity
cites work: Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
cites work: Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
cites work: Improved lower bounds on the rigidity of Hadamard matrices
cites work: A remark on matrix rigidity
cites work: Lower Bounds on Matrix Rigidity Via a Quantum Argument
cites work: Q4164821
cites work: Q4036702
DOI: 10.1016/J.JCSS.2009.09.003
description: scientific article; zbMATH DE number 5996364