On the public citation graph
When do extra majority gates help? Polylog (N) majority gates are equivalent to one
0 signed · 60 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.1006/inco.1994.1057openalex-snapshot
Depth Reduction for Circuits of Unbounded Fan-in
inferredcites →https://doi.org/10.1006/inco.1994.1059openalex-snapshot
Approximating Threshold Circuits by Rational Functions
inferredcites →https://doi.org/10.1007/bfb0009651openalex-snapshot
Two remarks on the power of counting
inferredcites →https://doi.org/10.1016/0020-0190(87)90036-6openalex-snapshot
Random oracles separate PSPACE from the polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/0022-0000(89)90033-0openalex-snapshot
With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/0304-3975(93)90214-eopenalex-snapshot
Probabilistic polynomials, AC0 functions and the polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/s0890-5401(03)00091-9openalex-snapshot
Some connections between bounded query classes and non-uniform complexity
inferredcites →https://doi.org/10.1109/fscs.1990.89583openalex-snapshot
ON ACC and threshold circuits
inferredcites →https://doi.org/10.1109/sct.1991.160239openalex-snapshot
PP is closed under truth-table reductions
inferredcites →https://doi.org/10.1109/sfcs.1985.49openalex-snapshot
Separating the polynomial-time hierarchy by oracles
inferredcites →https://doi.org/10.1109/sfcs.1989.63538openalex-snapshot
A note on the power of threshold circuits
inferredcites →https://doi.org/10.1145/103418.103461openalex-snapshot
The expressive power of voting polynomials
inferredcites →https://doi.org/10.1307/mmj/1028999029openalex-snapshot
Rational approximation to $| x| $.
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1006/inco.1998.2732openalex-snapshot
Threshold Circuits of Small Majority-Depth
inferred← citeshttps://doi.org/10.1006/jcss.1999.1651openalex-snapshot
Complexity Limitations on Quantum Computation
inferred← citeshttps://doi.org/10.1007/11523468_80openalex-snapshot
Lower Bounds for Circuits with Few Modular and Symmetric Gates
inferred← citeshttps://doi.org/10.1007/3-540-44666-4_28openalex-snapshot
On the Derandomization of Constant Depth Circuits
inferred← citeshttps://doi.org/10.1007/3-540-59042-0_63openalex-snapshot
Lower bounds for depth-three circuits with equals and mod-gates
inferred← citeshttps://doi.org/10.1007/3-540-62034-6_33openalex-snapshot
Circuit complexity before the dawn of the new millennium
inferred← citeshttps://doi.org/10.1007/978-1-4612-1872-2_11openalex-snapshot
Polynomials and Combinatorial Definitions of Languages
inferred← citeshttps://doi.org/10.1007/978-3-319-55911-7_14openalex-snapshot
Learning $$AC^0$$ Under k-Dependent Distributions
inferred← citeshttps://doi.org/10.1007/978-3-540-27819-1_16openalex-snapshot
Toward Attribute Efficient Learning of Decision Lists and Parities
inferred← citeshttps://doi.org/10.1007/978-3-540-27819-1_24openalex-snapshot
Learning Intersections of Halfspaces with a Margin
inferred← citeshttps://doi.org/10.1007/978-3-540-28629-5_24openalex-snapshot
Some Meet-in-the-Middle Circuit Lower Bounds
inferred← citeshttps://doi.org/10.1007/978-3-540-73545-8_44openalex-snapshot
Computing Symmetric Boolean Functions by Circuits with Few Exact Threshold Gates
inferred← citeshttps://doi.org/10.1007/978-3-642-15369-3_44openalex-snapshot
Learning and Lower Bounds for AC 0 with Threshold Gates
inferred← citeshttps://doi.org/10.1007/978-3-642-20877-5_17openalex-snapshot
NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(loglogn) Depth
inferred← citeshttps://doi.org/10.1007/978-3-642-22935-0_54openalex-snapshot
Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates
inferred← citeshttps://doi.org/10.1007/978-981-96-0668-9_20openalex-snapshot
A Satisfiability Algorithm for Depth Two Circuits with a Sub-Quadratic Number of Symmetric and Threshold Gates
inferred← citeshttps://doi.org/10.1007/bf01263421openalex-snapshot
Complex polynomials and circuit lower bounds for modular counting
inferred← citeshttps://doi.org/10.1007/bf01294257openalex-snapshot
Upper and lower bounds for some depth-3 circuit classes
inferred← citeshttps://doi.org/10.1007/bfb0023814openalex-snapshot
Complex polynomials and circuit lower bounds for modular counting
inferred← citeshttps://doi.org/10.1007/pl00001599openalex-snapshot
A complex-number Fourier technique for lower bounds on the Mod-m degree
inferred← citeshttps://doi.org/10.1007/s00493-014-3078-3openalex-snapshot
The communication complexity of addition
inferred← citeshttps://doi.org/10.1016/j.ipl.2011.12.011openalex-snapshot
Exponential lower bound for bounded depth circuits with few threshold gates
inferred← citeshttps://doi.org/10.1016/j.jcss.2007.04.012openalex-snapshot
Learning intersections of halfspaces with a margin
inferred← citeshttps://doi.org/10.1016/j.jcss.2019.04.004openalex-snapshot
Bounded depth circuits with weighted symmetric gates: Satisfiability, lower bounds and compression
inferred← citeshttps://doi.org/10.1109/ccc.1997.612310openalex-snapshot
Upper and lower bounds for some depth-3 circuit classes
inferred← citeshttps://doi.org/10.1109/ccc.2005.25openalex-snapshot
Pseudorandom Bits for Constant Depth Circuits with Few Arbitrary Symmetric Gates
inferred← citeshttps://doi.org/10.1109/sct.1993.336538openalex-snapshot
The polynomial method in circuit complexity
inferred← citeshttps://doi.org/10.1137/050640941openalex-snapshot
Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
inferred← citeshttps://doi.org/10.1137/080735096openalex-snapshot
Hardness Amplification Proofs Require Majority
inferred← citeshttps://doi.org/10.1137/1.9781611973105.46openalex-snapshot
The communication complexity of addition
inferred← citeshttps://doi.org/10.1145/2090236.2090273openalex-snapshot
On beating the hybrid argument
inferred← citeshttps://doi.org/10.1145/2591796.2591858openalex-snapshot
New algorithms and lower bounds for circuits with linear threshold gates
inferred← citeshttps://doi.org/10.1561/0400000033openalex-snapshot
On the Power of Small-Depth Computation
inferred← citeshttps://doi.org/10.1561/9781601983015openalex-snapshot
On the Power of Small-Depth Computation
inferred← citeshttps://doi.org/10.4230/lipics.ccc.2016.1openalex-snapshot
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
inferred← citeshttps://doi.org/10.48550/arxiv.1401.2444openalex-snapshot
New algorithms and lower bounds for circuits with linear threshold gates
inferred← citeshttps://doi.org/10.48550/arxiv.cs/0311042openalex-snapshot
Toward Attribute Efficient Learning Algorithms
inferred← citeshttps://doi.org/10.7282/t35d8qvqopenalex-snapshot
On circuit complexity classes and iterated matrix multiplication
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.