On the public citation graph
On ACC
0 signed · 178 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.1993.1033openalex-snapshot
A Circuit-Based Proof of Toda′s Theorem
inferredcites →https://doi.org/10.1006/inco.1994.1057openalex-snapshot
Depth Reduction for Circuits of Unbounded Fan-in
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/bf01744431openalex-snapshot
Parity, circuits, and the polynomial-time hierarchy
inferredcites →https://doi.org/10.1007/bfb0035785openalex-snapshot
Automata theory meets circuit complexity
inferredcites →https://doi.org/10.1016/0022-0000(89)90037-8openalex-snapshot
Bounded-width polynomial-size branching programs recognize exactly those languages in NC1
inferredcites →https://doi.org/10.1016/0168-0072(83)90038-6openalex-snapshot
∑11-Formulae on finite structures
inferredcites →https://doi.org/10.1016/0304-3975(92)90084-sopenalex-snapshot
Counting classes: thresholds, parity, mods, and fewness
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/b978-0-444-88071-0.50007-2openalex-snapshot
A Catalog of Complexity Classes
inferredcites →https://doi.org/10.1109/sct.1992.215383openalex-snapshot
Quasipolynomial size circuit classes
inferredcites →https://doi.org/10.1109/sct.1993.336538openalex-snapshot
The polynomial method in circuit complexity
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.1137/0220053openalex-snapshot
PP is as Hard as the Polynomial-Time Hierarchy
inferredcites →https://doi.org/10.1137/0221023openalex-snapshot
Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
inferredcites →https://doi.org/10.1145/129712.129771openalex-snapshot
The history and status of the P versus NP question
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/48014.63138openalex-snapshot
Finite monoids and the fine structure of NC 1
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1002/9783527670468.ch05openalex-snapshot
Computational Complexity of Graphs
inferred← citeshttps://doi.org/10.1002/jgt.20367openalex-snapshot
On set intersection representations of graphs
inferred← citeshttps://doi.org/10.1006/inco.1994.1057openalex-snapshot
Depth Reduction for Circuits of Unbounded Fan-in
inferred← citeshttps://doi.org/10.1006/inco.1998.2732openalex-snapshot
Threshold Circuits of Small Majority-Depth
inferred← citeshttps://doi.org/10.1006/inco.1998.2783openalex-snapshot
Efficient Threshold Circuits for Power Series
inferred← citeshttps://doi.org/10.1006/jcss.1995.1036openalex-snapshot
The Power of the Middle Bit of a #P Function
inferred← citeshttps://doi.org/10.1006/jcss.1999.1675openalex-snapshot
On TC0, AC0, and Arithmetic Circuits
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/10719839_21openalex-snapshot
Improved Upper Bounds on the Simultaneous Messages Complexity of the Generalized Addressing Function
inferred← citeshttps://doi.org/10.1007/11523468_94openalex-snapshot
Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity
inferred← citeshttps://doi.org/10.1007/11682462_51openalex-snapshot
Algorithms for Modular Counting of Roots of Multivariate Polynomials
inferred← citeshttps://doi.org/10.1007/3-540-36169-3_8openalex-snapshot
On Learning Embedded Midbit Functions
inferred← citeshttps://doi.org/10.1007/3-540-56503-5_54openalex-snapshot
Threshold circuits for iterated multiplication: Using AC0 for free
inferred← citeshttps://doi.org/10.1007/3-540-56503-5_56openalex-snapshot
A non-probabilistic switching lemma for the Sipser function
inferred← citeshttps://doi.org/10.1007/3-540-58715-2_130openalex-snapshot
My favorite ten complexity theorems of the past decade
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-59042-0_88openalex-snapshot
Simultaneous messages vs. communication
inferred← citeshttps://doi.org/10.1007/3-540-60217-8_19openalex-snapshot
On lower bounds for the depth of threshold circuits with weights from {−1,0,+1}
inferred← citeshttps://doi.org/10.1007/3-540-60922-9_52openalex-snapshot
Some bounds on multiparty communication complexity of pointer jumping
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/3-540-62685-9_4openalex-snapshot
Learning matrix functions over rings
inferred← citeshttps://doi.org/10.1007/978-1-4612-1388-8_12openalex-snapshot
Multiparty Communication Complexity of Finite Monoids
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-1-4615-2696-4_3openalex-snapshot
Communication Complexity and Lower Bounds for Threshold Circuits
inferred← citeshttps://doi.org/10.1007/978-3-030-36030-6_16openalex-snapshot
The Function-Inversion Problem: Barriers and Opportunities
inferred← citeshttps://doi.org/10.1007/978-3-319-15579-1_36openalex-snapshot
A Nonuniform Circuit Class with Multilayer of Threshold Gates Having Super Quasi Polynomial Size Lower Bounds Against NEXP
inferred← citeshttps://doi.org/10.1007/978-3-319-32162-2_1openalex-snapshot
$$P\mathop{ =}\limits^{?}NP$$
inferred← citeshttps://doi.org/10.1007/978-3-540-72504-6_28openalex-snapshot
Quantum Multiparty Communication Complexity and Circuit Lower Bounds
inferred← citeshttps://doi.org/10.1007/978-3-540-73420-8_14openalex-snapshot
Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity
inferred← citeshttps://doi.org/10.1007/978-3-642-03351-3_13openalex-snapshot
Depth Reduction for Circuits with a Single Layer of Modular Counting Gates
inferred← citeshttps://doi.org/10.1007/978-3-642-04414-4_19openalex-snapshot
An Algebraic Perspective on Boolean Function Learning
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-22993-0_40openalex-snapshot
Symmetric Functions Capture General Functions
inferred← citeshttps://doi.org/10.1007/978-3-642-31585-5_10openalex-snapshot
Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers
inferred← citeshttps://doi.org/10.1007/978-3-642-31594-7_2openalex-snapshot
The NOF Multiparty Communication Complexity of Composed Functions
inferred← citeshttps://doi.org/10.1007/978-3-642-32241-9_35openalex-snapshot
Lower Bounds against Weakly Uniform Circuits
inferred← citeshttps://doi.org/10.1007/978-3-642-60322-8_20openalex-snapshot
The BP-Operator and the Power of Counting Classes
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/bf01201812openalex-snapshot
On the power of generalized Mod-classes
inferred← citeshttps://doi.org/10.1007/bf01294257openalex-snapshot
Upper and lower bounds for some depth-3 circuit classes
inferred← citeshttps://doi.org/10.1007/bfb0055055openalex-snapshot
A degree-decreasing Lemma for (MOD q, MOD p) circuits
inferred← citeshttps://doi.org/10.1007/pl00001592openalex-snapshot
Circuits and multi-party protocols
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/s00037-009-0276-2openalex-snapshot
Disjointness is Hard in the Multiparty Number-on-the-Forehead Model
inferred← citeshttps://doi.org/10.1007/s00037-010-0287-zopenalex-snapshot
A New Characterization of ACC0 and Probabilistic CC0
inferred← citeshttps://doi.org/10.1007/s00037-012-0052-6openalex-snapshot
Hadamard tensors and lower bounds on multiparty communication complexity
inferred← citeshttps://doi.org/10.1007/s00037-013-0078-4openalex-snapshot
The NOF Multiparty Communication Complexity of Composed Functions
inferred← citeshttps://doi.org/10.1007/s00037-026-00296-9openalex-snapshot
A Technique for Hardness Amplification Against $$\textsf{AC}^0$$
inferred← citeshttps://doi.org/10.1007/s00153-017-0560-9openalex-snapshot
Uniform proofs of ACC representations
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-013-9476-xopenalex-snapshot
Optimal Collapsing Protocol for Multiparty Pointer Jumping
inferred← citeshttps://doi.org/10.1007/s002240000075openalex-snapshot
Isolating an Odd Number of Elements and Applications in Complexity Theory
inferred← citeshttps://doi.org/10.1007/s002240000078openalex-snapshot
Frobenius's Degree Formula and Toda's Polynomials
inferred← citeshttps://doi.org/10.1007/s00453-007-9097-3openalex-snapshot
Algorithms for Modular Counting of Roots of Multivariate Polynomials
inferred← citeshttps://doi.org/10.1007/s00453-013-9823-yopenalex-snapshot
Lower Bounds Against Weakly-Uniform Threshold Circuits
inferred← citeshttps://doi.org/10.1007/s00493-009-2667-zopenalex-snapshot
One-way multiparty communication lower bound for pointer jumping with applications
inferred← citeshttps://doi.org/10.1007/s10208-007-0245-yopenalex-snapshot
Modular Counting of Rational Points over Finite Fields
inferred← citeshttps://doi.org/10.1007/s11537-018-1727-9openalex-snapshot
Information complexity and applications
inferred← citeshttps://doi.org/10.1016/0020-0190(94)00221-jopenalex-snapshot
A note on the power of majority gates and modular gates
inferred← citeshttps://doi.org/10.1016/j.jcss.2004.01.003openalex-snapshot
The correlation between parity and quadratic polynomials mod3
inferred← citeshttps://doi.org/10.1016/j.jcss.2016.03.005openalex-snapshot
Hellinger volume and number-on-the-forehead communication complexity
inferred← citeshttps://doi.org/10.1016/j.tcs.2005.10.013openalex-snapshot
On learning embedded midbit functions
inferred← citeshttps://doi.org/10.1016/s0020-0190(98)00093-3openalex-snapshot
A lower bound for depth-3 circuits with MOD m gates
inferred← citeshttps://doi.org/10.1016/s0304-3975(97)00227-2openalex-snapshot
Non-commutative arithmetic circuits: depth reduction and size lower bounds
inferred← citeshttps://doi.org/10.1016/s0893-6080(02)00032-1openalex-snapshot
On the capabilities of neural networks using limited precision weights
inferred← citeshttps://doi.org/10.1017/s0960129508007263openalex-snapshot
Quantum multiparty communication complexity and circuit lower bounds
inferred← citeshttps://doi.org/10.1090/s0002-9947-2015-06233-3openalex-snapshot
Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
inferred← citeshttps://doi.org/10.1109/allerton.2012.6483456openalex-snapshot
Coding for interactive computation: Progress and challenges
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.2001.933885openalex-snapshot
Lower bounds for approximations by low degree polynomials over Z/sub m/
inferred← citeshttps://doi.org/10.1109/ccc.2002.1004341openalex-snapshot
The correlation between parity and quadratic polynomials mod 3
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/ccc.2007.14openalex-snapshot
Lower Bounds for Multi-Player Pointer Jumping
inferred← citeshttps://doi.org/10.1109/ccc.2008.29openalex-snapshot
Disjointness Is Hard in the Multi-party Number-on-the-Forehead Model
inferred← citeshttps://doi.org/10.1109/ccc.2008.30openalex-snapshot
Constant Width Planar Branching Programs Characterize ACC^0 in Quasipolynomial Size
inferred← citeshttps://doi.org/10.1109/ccc.2009.15openalex-snapshot
A New Characterization of ACC^0 and Probabilistic CC^0
inferred← citeshttps://doi.org/10.1109/ccc.2009.30openalex-snapshot
The Maximum Communication Complexity of Multi-Party Pointer Jumping
inferred← citeshttps://doi.org/10.1109/ccc.2011.36openalex-snapshot
Non-uniform ACC Circuit Lower Bounds
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.2007.24openalex-snapshot
Computing Equilibria in Anonymous Games
inferred← citeshttps://doi.org/10.1109/focs.2007.30openalex-snapshot
Discrepancy and the Power of Bottom Fan-in in Depth-three Circuits
inferred← citeshttps://doi.org/10.1109/focs.2007.51openalex-snapshot
A Brief Look at Pairings Based Cryptography
inferred← citeshttps://doi.org/10.1109/focs.2013.77openalex-snapshot
A Tight Bound for Set Disjointness in the Message-Passing Model
inferred← citeshttps://doi.org/10.1109/focs.2016.57openalex-snapshot
Polynomial Representations of Threshold Functions and Algorithmic Applications
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/focs46700.2020.00117openalex-snapshot
Extractors and Secret Sharing Against Bounded Collusion Protocols
inferred← citeshttps://doi.org/10.1109/focs52979.2021.00062openalex-snapshot
Quantum learning algorithms imply circuit lower bounds
inferred← citeshttps://doi.org/10.1109/sct.1992.215376openalex-snapshot
Perceptrons, PP, and the polynomial hierarchy
inferred← citeshttps://doi.org/10.1109/sct.1992.215383openalex-snapshot
Quasipolynomial size circuit classes
inferred← citeshttps://doi.org/10.1109/sct.1993.336531openalex-snapshot
On the power of generalized MOD-classes
inferred← citeshttps://doi.org/10.1109/sct.1993.336537openalex-snapshot
Lower bounds on representing Boolean functions as polynomials in Z/sub m/
inferred← citeshttps://doi.org/10.1109/sct.1993.336538openalex-snapshot
The polynomial method in circuit complexity
inferred← citeshttps://doi.org/10.1109/sct.1994.315806openalex-snapshot
Time, hardware, and uniformity
inferred← citeshttps://doi.org/10.1109/sct.1995.514863openalex-snapshot
On the structure of low sets [complexity classes]
inferred← citeshttps://doi.org/10.1109/sfcs.1993.366874openalex-snapshot
On representations by low-degree polynomials
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.1998.743459openalex-snapshot
Lower bounds for (MOD p-MOD m) circuits
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/100792779openalex-snapshot
Multiparty Communication Complexity and Threshold Circuit Size of $\ensuremath{\sfAC}^0$
inferred← citeshttps://doi.org/10.1137/130938219openalex-snapshot
Natural Proofs versus Derandomization
inferred← citeshttps://doi.org/10.1137/15m1024524openalex-snapshot
Faster All-Pairs Shortest Paths via Circuit Complexity
inferred← citeshttps://doi.org/10.1137/18m1195887openalex-snapshot
Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma
inferred← citeshttps://doi.org/10.1137/20m1322297openalex-snapshot
Efficient Construction of Rigid Matrices Using an NP Oracle
inferred← citeshttps://doi.org/10.1137/21m1418654openalex-snapshot
From Circuit Complexity to Faster All-Pairs Shortest Paths
inferred← citeshttps://doi.org/10.1137/s009753970342465xopenalex-snapshot
Computing Elementary Symmetric Polynomials with a Subpolynomial Numberof Multiplications
inferred← citeshttps://doi.org/10.1137/s0097539794264809openalex-snapshot
Boolean Circuits, Tensor Ranks, and Communication Complexity
inferred← citeshttps://doi.org/10.1145/167088.167226openalex-snapshot
Depth reduction for noncommutative arithmetic circuits
inferred← citeshttps://doi.org/10.1145/167088.167234openalex-snapshot
Simulating threshold circuits by majority circuits
inferred← citeshttps://doi.org/10.1145/1855118.1855133openalex-snapshot
The story of set disjointness
inferred← citeshttps://doi.org/10.1145/1855118.1886592openalex-snapshot
SIGACT News Complexity Theory Column 67
inferred← citeshttps://doi.org/10.1145/195058.195108openalex-snapshot
A weight-size trade-off for circuits with MOD m gates
inferred← citeshttps://doi.org/10.1145/2034575.2034590openalex-snapshot
SIGACT news complexity theory column 71
inferred← citeshttps://doi.org/10.1145/2213977.2214025openalex-snapshot
Interactive information complexity
inferred← citeshttps://doi.org/10.1145/2488608.2488612openalex-snapshot
Natural proofs versus derandomization
inferred← citeshttps://doi.org/10.1145/2488608.2488628openalex-snapshot
From information to exact communication
inferred← citeshttps://doi.org/10.1145/2559948openalex-snapshot
Degree lower bounds of tower-type for approximating formulas with parity quantifiers
inferred← citeshttps://doi.org/10.1145/2591796.2591811openalex-snapshot
Faster all-pairs shortest paths via circuit complexity
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.1145/2789149.2789161openalex-snapshot
Information Complexity and the Quest for Interactive Compression
inferred← citeshttps://doi.org/10.1145/3061640.3061648openalex-snapshot
Selected challenges in computational lower bounds
inferred← citeshttps://doi.org/10.1145/3188745.3188910openalex-snapshot
Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
inferred← citeshttps://doi.org/10.1145/3402926openalex-snapshot
Deterministic APSP, Orthogonal Vectors, and More
inferred← citeshttps://doi.org/10.1145/3406325.3451132openalex-snapshot
Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma
inferred← citeshttps://doi.org/10.1145/3564246.3585147openalex-snapshot
Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms
inferred← citeshttps://doi.org/10.1145/3564246.3585216openalex-snapshot
Depth-𝑑 Threshold Circuits vs. Depth-(𝑑+1) AND-OR Trees
inferred← citeshttps://doi.org/10.1145/3717823.3718272openalex-snapshot
Leakage-Resilient Extractors against Number-on-Forehead Protocols
inferred← citeshttps://doi.org/10.1561/0400000040openalex-snapshot
Lower Bounds in Communication Complexity
inferred← citeshttps://doi.org/10.1561/9781601982599openalex-snapshot
Lower Bounds in Communication Complexity
inferred← citeshttps://doi.org/10.22331/q-2020-05-11-264openalex-snapshot
How many qubits are needed for quantum computational supremacy?
inferred← citeshttps://doi.org/10.4036/iis.2014.1openalex-snapshot
Proving Circuit Lower Bounds in High Uniform Classes
inferred← citeshttps://doi.org/10.4230/lipics.fsttcs.2021.14openalex-snapshot
Functional Lower Bounds for Restricted Arithmetic Circuits of Depth Four
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2021.29openalex-snapshot
Counting Short Vector Pairs by Inner Product and Relations to the Permanent
inferred← citeshttps://doi.org/10.4230/lipics.itcs.2022.48openalex-snapshot
Larger Corner-Free Sets from Combinatorial Degenerations
inferred← citeshttps://doi.org/10.48550/arxiv.1111.1261openalex-snapshot
A Casual Tour Around a Circuit Complexity Bound
inferred← citeshttps://doi.org/10.48550/arxiv.1212.1891openalex-snapshot
Natural Proofs Versus Derandomization
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.1504.06830openalex-snapshot
Information Complexity and the Quest for Interactive Compression (A Survey)
inferred← citeshttps://doi.org/10.48550/arxiv.1710.01969openalex-snapshot
Simultaneous Multiparty Communication Complexity of Composed Functions
inferred← citeshttps://doi.org/10.48550/arxiv.1802.09121openalex-snapshot
Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials
inferred← citeshttps://doi.org/10.48550/arxiv.2111.08262openalex-snapshot
Larger Corner-Free Sets from Combinatorial Degenerations
inferred← citeshttps://doi.org/10.70675/6f7a7842z6c00z4827zbd19zb54ee1de39c5openalex-snapshot
Asymptotic properties of hypergraphs and channels
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.