On the public citation graph
Top-down lower bounds for depth-three circuits
0 signed · 47 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.
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.
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.1007/bf01137685openalex-snapshot
Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
inferredcites →https://doi.org/10.1007/bf01200404openalex-snapshot
On lower bounds for read-k-times branching programs
inferredcites →https://doi.org/10.1007/bf01744431openalex-snapshot
Parity, circuits, and the polynomial-time hierarchy
inferredcites →https://doi.org/10.1007/bfb0030341openalex-snapshot
A topological view of some problems in complexity theory
inferredcites →https://doi.org/10.1016/0168-0072(83)90038-6openalex-snapshot
∑11-Formulae on finite structures
inferredcites →https://doi.org/10.1109/sfcs.1985.49openalex-snapshot
Separating the polynomial-time hierarchy by oracles
inferredcites →https://doi.org/10.1112/jlms/s1-35.1.85openalex-snapshot
Intersection Theorems for Systems of Sets
inferredcites →https://doi.org/10.1137/0403021openalex-snapshot
Monotone Circuits for Connectivity Require Super-Logarithmic Depth
inferredcites →https://doi.org/10.1145/100216.100253openalex-snapshot
Monotone circuits for matching require linear depth
inferredcites →https://doi.org/10.1145/28395.28404openalex-snapshot
Algebraic methods in the theory of lower bounds for Boolean circuit complexity
inferredcites →https://doi.org/10.1145/800057.808717openalex-snapshot
On monotone formulae with restricted depth
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1007/978-3-030-43662-9_6openalex-snapshot
On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions
inferred← citeshttps://doi.org/10.1007/978-3-031-98740-3_19openalex-snapshot
Reconstructing Sets of Strings from Their k-Way Projections: Algorithms & Complexity
inferred← citeshttps://doi.org/10.1007/978-3-319-60080-2_16openalex-snapshot
Symmetric-Key Broadcast Encryption: The Multi-sender Case
inferred← citeshttps://doi.org/10.1007/978-3-642-24508-4openalex-snapshot
Boolean Function Complexity: Advances and Frontiers
inferred← citeshttps://doi.org/10.1007/978-3-662-48054-0_25openalex-snapshot
A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time
inferred← citeshttps://doi.org/10.1007/s00037-018-0175-5openalex-snapshot
Query-to-Communication Lifting for PNP
inferred← citeshttps://doi.org/10.1007/s00037-019-00177-4openalex-snapshot
Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds
inferred← citeshttps://doi.org/10.1016/j.ejc.2024.104041openalex-snapshot
A generalization of diversity for intersecting families
inferred← citeshttps://doi.org/10.1016/j.ic.2024.105192openalex-snapshot
Depth-3 circuits for inner product
inferred← citeshttps://doi.org/10.1016/j.ipl.2006.06.008openalex-snapshot
The complexity of depth-3 circuits computing symmetric Boolean functions
inferred← citeshttps://doi.org/10.1016/j.jcta.2017.11.019openalex-snapshot
A degree version of the Hilton–Milner theorem
inferred← citeshttps://doi.org/10.1016/s0304-3975(99)00185-1openalex-snapshot
Some structural properties of low-rank matrices related to computational complexity
inferred← citeshttps://doi.org/10.1070/rm9905openalex-snapshot
Extremal problems in hypergraph colourings
inferred← citeshttps://doi.org/10.1109/ccc.1997.612325openalex-snapshot
Finite limits and monotone computations: the lower bounds criterion
inferred← citeshttps://doi.org/10.1109/focs.2006.27openalex-snapshot
Explicit Exclusive Set Systems with Applications to Broadcast Encryption
inferred← citeshttps://doi.org/10.1109/focs57990.2023.00063openalex-snapshot
Top-Down Lower Bounds for Depth-Four Circuits
inferred← citeshttps://doi.org/10.1109/isit54713.2023.10206832openalex-snapshot
On the Information Capacity of Nearest Neighbor Representations
inferred← citeshttps://doi.org/10.1109/isit57864.2024.10619486openalex-snapshot
Nearest Neighbor Representations of Neural Circuits
inferred← citeshttps://doi.org/10.1137/1.9781611973099.77openalex-snapshot
A Satisfiability Algorithm for AC 0
inferred← citeshttps://doi.org/10.1137/15m1018319openalex-snapshot
Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation
inferred← citeshttps://doi.org/10.1145/2591796.2591828openalex-snapshot
Formulas vs. circuits for small distance connectivity
inferred← citeshttps://doi.org/10.1145/2591796.2591856openalex-snapshot
Toward better formula lower bounds
inferred← citeshttps://doi.org/10.1145/3531130.3533371openalex-snapshot
The Regular Languages of First-Order Logic with One Alternation
inferred← citeshttps://doi.org/10.1145/3812802openalex-snapshot
Depth-3 Circuit Lower Bounds for \(k\) -OV
inferred← citeshttps://doi.org/10.4213/rm9905openalex-snapshot
Экстремальные задачи в раскрасках гиперграфов
inferred← citeshttps://doi.org/10.4230/lipics.approx-random.2019.56openalex-snapshot
String Matching: Communication, Circuits, and Learning
inferred← citeshttps://doi.org/10.48550/arxiv.1107.3127openalex-snapshot
A Satisfiability Algorithm for AC$^0$
inferred← citeshttps://doi.org/10.48550/arxiv.1504.08235openalex-snapshot
A shortcut to (sun)flowers: Kernels in logarithmic space or linear time
inferred← citeshttps://doi.org/10.48550/arxiv.1703.00494openalex-snapshot
Chvátal's conjecture for downsets of small rank
inferred← citeshttps://doi.org/10.48550/arxiv.1705.03588openalex-snapshot
A Duality Between Depth-Three Formulas and Approximation by Depth-Two
inferred← citeshttps://doi.org/10.48550/arxiv.2101.01757openalex-snapshot
A preliminary result for generalized intersecting families
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.