On the public citation graph

Communication in bounded depth circuits

0 signed · 77 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.

Claim with ORCID

Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.

See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/3-540-08353-7_135openalex-snapshot

Graph-theoretic arguments in low-level complexity

inferredcites →https://doi.org/10.1016/0022-0000(82)90056-3openalex-snapshot

Superconcentrators of depth 2

inferredcites →https://doi.org/10.1016/0304-3975(93)90332-nopenalex-snapshot

On shifting networks

inferredcites →https://doi.org/10.1016/s0022-0000(05)80027-3openalex-snapshot

Superconcentrators of depths 2 and 3; odd levels help (rarely)

inferredcites →https://doi.org/10.1109/sfcs.1991.185394openalex-snapshot

Lower bounds for polynomial evaluation and interpolation problems

inferredcites →https://doi.org/10.1137/0603041openalex-snapshot

Rearrangeable Networks with Limited Depth

inferredcites →https://doi.org/10.1145/800061.808731openalex-snapshot

Superconcentrators, generalizers and generalized connectors with limited depth

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1006/jcss.2001.1786openalex-snapshot

Spectral Methods for Matrix Rigidity with Applications to Size–Depth Trade-offs and Communication Complexity

inferred← citeshttps://doi.org/10.1007/11672142_30openalex-snapshot

Tradeoffs in Depth-Two Superconcentrators

inferred← citeshttps://doi.org/10.1007/3-540-60922-9_50openalex-snapshot

The “log rank” conjecture for modular communication complexity

inferred← citeshttps://doi.org/10.1007/978-1-4613-0281-0_14openalex-snapshot

Notes on the Complexity of Switching Networks

inferred← citeshttps://doi.org/10.1007/978-3-030-79416-3_5openalex-snapshot

Real $$\tau $$-Conjecture for Sum-of-Squares: A Unified Approach to Lower Bound and Derandomization

inferred← citeshttps://doi.org/10.1007/978-3-031-49193-1_30openalex-snapshot

On the Minimum Depth of Circuits with Linear Number of Wires Encoding Good Codes

inferred← citeshttps://doi.org/10.1007/978-3-319-06686-8_6openalex-snapshot

On Lower Bounds for Multiplicative Circuits and Linear Circuits in Noncommutative Domains

inferred← citeshttps://doi.org/10.1007/978-3-540-73001-9_44openalex-snapshot

Circuit Complexity of Regular Languages

inferred← citeshttps://doi.org/10.1007/978-3-540-79709-8_15openalex-snapshot

Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates

inferred← citeshttps://doi.org/10.1007/978-3-642-10631-6_17openalex-snapshot

Hilbert’s Thirteenth Problem and Circuit Complexity

inferred← citeshttps://doi.org/10.1007/978-3-642-24508-4openalex-snapshot

Boolean Function Complexity: Advances and Frontiers

inferred← citeshttps://doi.org/10.1007/bf02311250openalex-snapshot

Improved lower bounds on the rigidity of Hadamard matrices

inferred← citeshttps://doi.org/10.1007/bfb0029945openalex-snapshot

Communication complexity

inferred← citeshttps://doi.org/10.1007/s00037-007-0226-9openalex-snapshot

Polynomial Identity Testing for Depth 3 Circuits

inferred← citeshttps://doi.org/10.1007/s00037-011-0021-5openalex-snapshot

On a Theorem of Razborov

inferred← citeshttps://doi.org/10.1007/s00037-021-00205-2openalex-snapshot

Lower Bounds for Matrix Factorization

inferred← citeshttps://doi.org/10.1007/s00224-008-9133-yopenalex-snapshot

Entropy of Operators or why Matrix Multiplication is Hard for Depth-Two Circuits

inferred← citeshttps://doi.org/10.1007/s00224-009-9180-zopenalex-snapshot

Circuit Complexity of Regular Languages

inferred← citeshttps://doi.org/10.1007/s00224-026-10294-7openalex-snapshot

Real $$\tau $$-Conjecture for Sum-of-squares: A Unified Approach to Lower Bound and Derandomization

inferred← citeshttps://doi.org/10.1007/s10878-011-9402-6openalex-snapshot

Constructions of given-depth and optimal multirate rearrangeably nonblocking distributors

inferred← citeshttps://doi.org/10.1016/0012-365x(94)00115-yopenalex-snapshot

Some combinatorial-algebraic problems from complexity theory

inferred← citeshttps://doi.org/10.1016/0304-3975(93)90332-nopenalex-snapshot

On shifting networks

inferred← citeshttps://doi.org/10.1016/j.disc.2009.07.011openalex-snapshot

Representing (0, 1)-matrices by boolean circuits

inferred← citeshttps://doi.org/10.1016/j.jcss.2009.09.003openalex-snapshot

Min-rank conjecture for log-depth circuits

inferred← citeshttps://doi.org/10.1016/j.jcta.2016.06.004openalex-snapshot

High girth augmented trees are huge

inferred← citeshttps://doi.org/10.1016/j.tcs.2008.09.029openalex-snapshot

A nonlinear lower bound for constant depth arithmetical circuits via the discrete uncertainty principle

inferred← citeshttps://doi.org/10.1016/s0020-0190(97)00190-7openalex-snapshot

A remark on matrix rigidity

inferred← citeshttps://doi.org/10.1016/s0022-0000(02)00021-1openalex-snapshot

Affine projections of symmetric polynomials

inferred← citeshttps://doi.org/10.1016/s0022-0000(05)80027-3openalex-snapshot

Superconcentrators of depths 2 and 3; odd levels help (rarely)

inferred← citeshttps://doi.org/10.1016/s0024-3795(99)00225-6openalex-snapshot

Matrix rigidity

inferred← citeshttps://doi.org/10.1016/s0024-3795(99)00226-8openalex-snapshot

Matrix rank and communication complexity

inferred← citeshttps://doi.org/10.1016/s0304-3975(00)00008-6openalex-snapshot

On the rigidity of Vandermonde matrices

inferred← citeshttps://doi.org/10.1090/dimacs/042openalex-snapshot

Advances in Switching Networks

inferred← citeshttps://doi.org/10.1109/ccc.2001.933883openalex-snapshot

Affine projections of symmetric polynomials

inferred← citeshttps://doi.org/10.1109/ccc.2012.39openalex-snapshot

Limitations of Lower-Bound Methods for the Wire Complexity of Boolean Operators

inferred← citeshttps://doi.org/10.1109/focs.2006.46openalex-snapshot

Lower bounds for circuits with MOD_m gates

inferred← citeshttps://doi.org/10.1109/focs.2019.00067openalex-snapshot

Efficient Construction of Rigid Matrices Using an NP Oracle

inferred← citeshttps://doi.org/10.1109/hpsr.2007.4281250openalex-snapshot

Constructions of Given-Depth and Optimal Multirate Rearrangeably Nonblocking Distributors

inferred← citeshttps://doi.org/10.1109/sfcs.1995.492457openalex-snapshot

Spectral methods for matrix rigidity with applications to size-depth tradeoffs and communication complexity

inferred← citeshttps://doi.org/10.1109/sfcs.1997.646148openalex-snapshot

Tight bounds for depth-two superconcentrators

inferred← citeshttps://doi.org/10.1109/tit.2013.2270275openalex-snapshot

Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates

inferred← citeshttps://doi.org/10.1109/tnet.2008.2001728openalex-snapshot

Rearrangeable and Nonblocking $[w,f]$-Distributors

inferred← citeshttps://doi.org/10.1137/05063605xopenalex-snapshot

Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits

inferred← citeshttps://doi.org/10.1137/080735850openalex-snapshot

Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits

inferred← citeshttps://doi.org/10.1137/20m1322297openalex-snapshot

Efficient Construction of Rigid Matrices Using an NP Oracle

inferred← citeshttps://doi.org/10.1137/21m1443339openalex-snapshot

Kronecker Products, Low-Depth Circuits, and Matrix Rigidity

inferred← citeshttps://doi.org/10.1137/s009753970138462xopenalex-snapshot

Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates

inferred← citeshttps://doi.org/10.1137/s0097539794264809openalex-snapshot

Boolean Circuits, Tensor Ranks, and Communication Complexity

inferred← citeshttps://doi.org/10.1137/s0895480197329508openalex-snapshot

Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators

inferred← citeshttps://doi.org/10.1145/1060590.1060629openalex-snapshot

Bounded-depth circuits

inferred← citeshttps://doi.org/10.1145/1060590.1060678openalex-snapshot

Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits

inferred← citeshttps://doi.org/10.1145/1374376.1374479openalex-snapshot

Elusive functions and lower bounds for arithmetic circuits

inferred← citeshttps://doi.org/10.1145/1455248.1455252openalex-snapshot

Weak ε-nets and interval chains

inferred← citeshttps://doi.org/10.1145/167088.167228openalex-snapshot

Modified ranks of tensors and the size of circuits

inferred← citeshttps://doi.org/10.1145/2213977.2214023openalex-snapshot

Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates

inferred← citeshttps://doi.org/10.1145/3406325.3451008openalex-snapshot

Kronecker products, low-depth circuits, and matrix rigidity

inferred← citeshttps://doi.org/10.1515/dma.2008.011openalex-snapshot

On complexity of linear operators on the class of circuits of depth 2

inferred← citeshttps://doi.org/10.1515/dma.2011.031openalex-snapshot

Lower bounds for complexity of Boolean circuits of finite depth with arbitrary elements

inferred← citeshttps://doi.org/10.1561/0400000011openalex-snapshot

Complexity Lower Bounds using Linear Algebra

inferred← citeshttps://doi.org/10.1561/0400000063openalex-snapshot

Complexity of Linear Boolean Operators

inferred← citeshttps://doi.org/10.2168/lmcs-3(1:4)2007openalex-snapshot

Logic Meets Algebra: the Case of Regular Languages

inferred← citeshttps://doi.org/10.4086/toc.2010.v006a007openalex-snapshot

inferred← citeshttps://doi.org/10.4086/toc.2019.v015a018openalex-snapshot

inferred← citeshttps://doi.org/10.4213/dm1160openalex-snapshot

Нижние оценки сложности булевых схем конечной глубины с произвольными элементами

inferred← citeshttps://doi.org/10.4213/dm994openalex-snapshot

О сложности линейных операторов в классе схем глубины 2

inferred← citeshttps://doi.org/10.4213/mzm1314openalex-snapshot

Новые нижние оценки устойчивости матриц Адамара

inferred← citeshttps://doi.org/10.4230/lipics.ccc.2020.5openalex-snapshot

Lower Bounds for Matrix Factorization

inferred← citeshttps://doi.org/10.48550/arxiv.1004.5236openalex-snapshot

Circuits with arbitrary gates for random operators

inferred← citeshttps://doi.org/10.48550/arxiv.cs/0506081openalex-snapshot

Three lines proof of the lower bound for the matrix rigidity

inferred← citeshttps://doi.org/10.70675/20c06f35z8a0dz4872z83e0z5bc2fafd8555openalex-snapshot

On the complexity of regular languages

Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.