Min-rank conjecture for log-depth circuits

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

zbMATH Keywords

matrix completion; Cayley graphs; partial matrix; error-correcting codes; Boolean circuits; matrix rigidity; min-rank; sum-sets

Mathematics Subject Classification ID

94B05: Linear codes (general theory)

Related Items

The minrank of random graphs, The function-inversion problem: barriers and opportunities

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item