Min-rank conjecture for log-depth circuits
From MaRDI portal
Publication:657911
DOI10.1016/j.jcss.2009.09.003zbMath1247.94074WikidataQ123282575 ScholiaQ123282575MaRDI QIDQ657911
Georg Schnitger, Stasys P. Jukna
Publication date: 11 January 2012
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2009.09.003
matrix completion; Cayley graphs; partial matrix; error-correcting codes; Boolean circuits; matrix rigidity; min-rank; sum-sets
94B05: Linear codes (general theory)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A remark on matrix rigidity
- A note on matrix rigidity
- On shifting networks
- Entropy of operators or why matrix multiplication is hard for depth-two circuits
- Superconcentrators of depth 2
- Improved lower bounds on the rigidity of Hadamard matrices
- Superconcentrators of depths 2 and 3; odd levels help (rarely)
- Communication in bounded depth circuits
- On the rigidity of Vandermonde matrices
- Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
- Linear Circuits over $\operatorname{GF}(2)$
- Lower Bounds on Matrix Rigidity Via a Quantum Argument
- The Linear Complexity of Computation
- Superconcentrators
- Boolean Circuits, Tensor Ranks, and Communication Complexity
- Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
- Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
- Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform