Min-rank conjecture for log-depth circuits
From MaRDI portal
Publication:657911
DOI10.1016/j.jcss.2009.09.003zbMath1247.94074OpenAlexW1997575430WikidataQ123282575 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 completionCayley graphspartial matrixerror-correcting codesBoolean circuitsmatrix rigiditymin-ranksum-sets
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (2)
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
This page was built for publication: Min-rank conjecture for log-depth circuits
