Min-rank conjecture for log-depth circuits

DOI10.1016/J.JCSS.2009.09.003MaRDI QIDQ657911zbMATH OpenOpenAlexWikidataFDO

Authors Georg Schnitger, Stasys 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

Boolean circuitsCayley graphserror-correcting codesmatrix completionmatrix rigiditymin-rankpartial matrixsum-sets

Mathematics Subject Classification ID

Linear codes (general theory) (94B05)

Recommendations

• The log-rank conjecture and low degree polynomials
• The log rank conjecture for modular communication complexity
• The ``log rank conjecture for modular communication complexity
• Linear Circuits over $\operatorname{GF}(2)$
• On minrank and forbidden subgraphs

Cites work

• A note on matrix rigidity
• A remark on matrix rigidity
• Boolean Circuits, Tensor Ranks, and Communication Complexity
• Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
• Communication in bounded depth circuits
• Entropy of operators or why matrix multiplication is hard for depth-two circuits
• scientific article; zbMATH DE number 5077418 (Why is no real title available?)
• scientific article; zbMATH DE number 4158856 (Why is no real title available?)
• scientific article; zbMATH DE number 4107004 (Why is no real title available?)
• scientific article; zbMATH DE number 37868 (Why is no real title available?)
• scientific article; zbMATH DE number 176871 (Why is no real title available?)
• scientific article; zbMATH DE number 3597878 (Why is no real title available?)
• Improved lower bounds on the rigidity of Hadamard matrices
• Linear Circuits over $\operatorname{GF}(2)$
• Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
• Lower Bounds on Matrix Rigidity Via a Quantum Argument
• Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
• On shifting networks
• On the rigidity of Vandermonde matrices
• Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
• Superconcentrators
• Superconcentrators of depth 2
• Superconcentrators of depths 2 and 3; odd levels help (rarely)
• The Linear Complexity of Computation

Cited in

(4)

• The function-inversion problem: barriers and opportunities
• The minrank of random graphs
• Block rigidity: strong multiplayer parallel repetition implies super-linear lower bounds for Turing machines
• On the direct sum conjecture

This page was built for publication: Min-rank conjecture for log-depth circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q657911)