On the public citation graph
Non-uniform ACC Circuit Lower Bounds
0 signed · 166 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.1054openalex-snapshot
Exponential Size Lower Bounds for Some Depth 3 Circuits
inferredcites →https://doi.org/10.1006/jcss.1995.1029openalex-snapshot
Superlinear Lower Bounds for Bounded-Width Branching Programs
inferredcites →https://doi.org/10.1006/jcss.1995.1036openalex-snapshot
The Power of the Middle Bit of a #P Function
inferredcites →https://doi.org/10.1006/jcss.1999.1675openalex-snapshot
On TC0, AC0, and Arithmetic Circuits
inferredcites →https://doi.org/10.1006/jcss.2001.1767openalex-snapshot
Time–Space Tradeoffs for SAT on Nonuniform Machines
inferredcites →https://doi.org/10.1007/3-540-48686-0_21openalex-snapshot
Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy
inferredcites →https://doi.org/10.1007/3-540-59042-0_63openalex-snapshot
Lower bounds for depth-three circuits with equals and mod-gates
inferredcites →https://doi.org/10.1007/978-3-642-11269-0_6openalex-snapshot
The Complexity of Satisfiability of Small Depth Circuits
inferredcites →https://doi.org/10.1007/bf01263425openalex-snapshot
Circuits constructed with MOD q gates cannot compute ?AND? in sublinear size
inferredcites →https://doi.org/10.1007/bf01275486openalex-snapshot
BPP has subexponential time simulations unlessEXPTIME has publishable proofs
inferredcites →https://doi.org/10.1007/bf01744431openalex-snapshot
Parity, circuits, and the polynomial-time hierarchy
inferredcites →https://doi.org/10.1007/bf02579196openalex-snapshot
The monotone circuit complexity of boolean functions
inferredcites →https://doi.org/10.1007/s00037-004-0182-6openalex-snapshot
Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds
inferredcites →https://doi.org/10.1007/s00037-010-0287-zopenalex-snapshot
A New Characterization of ACC0 and Probabilistic CC0
inferredcites →https://doi.org/10.1007/s00224-005-1258-7openalex-snapshot
Constant Width Planar Computation Characterizes ACC0
inferredcites →https://doi.org/10.1016/0020-0190(88)90152-4openalex-snapshot
Short propositional formulas represent nondeterministic computations
inferredcites →https://doi.org/10.1016/0020-0190(96)00029-4openalex-snapshot
A note on a theorem of Barrington, Straubing and Thérien
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(83)90015-4openalex-snapshot
A Turing machine time hierarchy
inferredcites →https://doi.org/10.1016/0304-3975(91)90177-4openalex-snapshot
An O(T log T) reduction from RAM computations to satisfiability
inferredcites →https://doi.org/10.1016/0890-5401(90)90007-5openalex-snapshot
Non-uniform automata over groups
inferredcites →https://doi.org/10.1016/j.jalgor.2004.04.012openalex-snapshot
An algorithm for the satisfiability problem of formulas in conjunctive normal form
inferredcites →https://doi.org/10.1016/s0019-9958(82)90382-5openalex-snapshot
Circuit-size lower bounds and non-reducibility to sparse sets
inferredcites →https://doi.org/10.1016/s0019-9958(86)80009-2openalex-snapshot
A note on succinct representations of graphs
inferredcites →https://doi.org/10.1016/s0020-0190(98)00093-3openalex-snapshot
A lower bound for depth-3 circuits with MOD m gates
inferredcites →https://doi.org/10.1016/s0022-0000(02)00024-7openalex-snapshot
In search of an easy witness: exponential time vs. probabilistic polynomial time
inferredcites →https://doi.org/10.1109/ccc.2006.6openalex-snapshot
A Duality between Clause Width and Clause Density for SAT
inferredcites →https://doi.org/10.1109/focs.2006.46openalex-snapshot
Lower bounds for circuits with MOD_m gates
inferredcites →https://doi.org/10.1109/focs.2009.17openalex-snapshot
Linear Systems over Composite Moduli
inferredcites →https://doi.org/10.1109/focs.2010.25openalex-snapshot
Fighting Perebor: New and Improved Algorithms for Formula and QBF Satisfiability
inferredcites →https://doi.org/10.1109/fscs.1990.89583openalex-snapshot
ON ACC and threshold circuits
inferredcites →https://doi.org/10.1109/sfcs.1985.49openalex-snapshot
Separating the polynomial-time hierarchy by oracles
inferredcites →https://doi.org/10.1137/0204037openalex-snapshot
Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
inferredcites →https://doi.org/10.1137/s0097539700389652openalex-snapshot
Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
inferredcites →https://doi.org/10.1137/s0097539792233907openalex-snapshot
A Uniform Circuit Lower Bound for the Permanent
inferredcites →https://doi.org/10.1137/s0097539798340850openalex-snapshot
Lower Bounds for (MOD p - MOD m ) Circuits
inferredcites →https://doi.org/10.1145/1101821.1101822openalex-snapshot
Time-space lower bounds for satisfiability
inferredcites →https://doi.org/10.1145/12130.12131openalex-snapshot
Bounded-width polynomial-size branching programs recognize exactly those languages in NC 1
inferredcites →https://doi.org/10.1145/12130.12132openalex-snapshot
Almost optimal lower bounds for small depth circuits
inferredcites →https://doi.org/10.1145/1806689.1806723openalex-snapshot
Improving exhaustive search implies superpolynomial lower bounds
inferredcites →https://doi.org/10.1145/195058.195103openalex-snapshot
On the computational power of depth 2 circuits with threshold and modulo gates
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/322047.322060openalex-snapshot
Satisfiability Is Quasilinear Complete in NQL
inferredcites →https://doi.org/10.1145/322047.322061openalex-snapshot
Separating Nondeterministic Time Complexity Classes
inferredcites →https://doi.org/10.1145/48014.63138openalex-snapshot
Finite monoids and the fine structure of NC 1
inferredcites →https://doi.org/10.3233/978-1-58603-929-5-403openalex-snapshot
Worst-Case Upper Bounds
inferredcites →https://doi.org/10.4086/cjtcs.1999.007openalex-snapshot
The Permanent Requires Large Uniform Threshold Circuits.
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-48516-0_6openalex-snapshot
On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection
inferred← citeshttps://doi.org/10.1007/978-3-319-09284-3_4openalex-snapshot
Solving Sparse Instances of Max SAT via Width Reduction and Greedy Restriction
inferred← citeshttps://doi.org/10.1007/978-3-319-98355-4_8openalex-snapshot
Probabilism versus Alternation for Automata
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-21581-0_1openalex-snapshot
Connecting SAT Algorithms and Complexity Lower Bounds
inferred← citeshttps://doi.org/10.1007/978-3-642-22006-7_48openalex-snapshot
Robust Simulations and Significant Separations
inferred← citeshttps://doi.org/10.1007/978-3-642-22685-4_21openalex-snapshot
Diagonalization Strikes Back: Some Recent Lower Bounds in Complexity Theory
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-3-642-29344-3_32openalex-snapshot
NE Is Not NP Turing Reducible to Nonexponentially Dense NP Sets
inferred← citeshttps://doi.org/10.1007/978-3-642-30891-8_11openalex-snapshot
Parameterized Complexity and Subexponential-Time Computability
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_65openalex-snapshot
On the Limits of Sparsification
inferred← citeshttps://doi.org/10.1007/978-3-642-32009-5_5openalex-snapshot
Substitution-Permutation Networks, Pseudorandom Functions, and Natural Proofs
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-32241-9_36openalex-snapshot
On TC0 Lower Bounds for the Permanent
inferred← citeshttps://doi.org/10.1007/978-3-642-38536-0_15openalex-snapshot
Towards NEXP versus BPP?
inferred← citeshttps://doi.org/10.1007/978-3-662-43948-7_14openalex-snapshot
Short PCPs with Projection Queries
inferred← citeshttps://doi.org/10.1007/978-3-662-44465-8_15openalex-snapshot
An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas
inferred← citeshttps://doi.org/10.1007/978-3-662-48054-0_19openalex-snapshot
Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases
inferred← citeshttps://doi.org/10.1007/s00037-012-0051-7openalex-snapshot
Pseudorandom generators for CC0[p] and the Fourier spectrum of low-degree polynomials over finite fields
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-0067-7openalex-snapshot
A satisfiability algorithm and average-case hardness for formulas over the full binary basis
inferred← citeshttps://doi.org/10.1007/s00037-013-0069-5openalex-snapshot
Amplifying circuit lower bounds against polynomial time, with applications
inferred← citeshttps://doi.org/10.1007/s00037-014-0087-yopenalex-snapshot
On Uniformity and Circuit Lower Bounds
inferred← citeshttps://doi.org/10.1007/s00037-015-0100-0openalex-snapshot
Mining Circuit Lower Bound Proofs for Meta-Algorithms
inferred← citeshttps://doi.org/10.1007/s00037-015-0103-xopenalex-snapshot
Unifying Known Lower Bounds via Geometric Complexity Theory
inferred← citeshttps://doi.org/10.1007/s00224-014-9600-6openalex-snapshot
Solving Sparse Instances of Max SAT via Width Reduction and Greedy Restriction
inferred← citeshttps://doi.org/10.1007/s00453-013-9823-yopenalex-snapshot
Lower Bounds Against Weakly-Uniform Threshold Circuits
inferred← citeshttps://doi.org/10.1007/s00453-015-0020-zopenalex-snapshot
An Improved Deterministic #SAT Algorithm for Small de Morgan Formulas
inferred← citeshttps://doi.org/10.1007/s00453-016-0228-6openalex-snapshot
Strong ETH and Resolution via Games and the Multiplicity of Strategies
inferred← citeshttps://doi.org/10.1007/s00453-021-00915-7openalex-snapshot
A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates
inferred← citeshttps://doi.org/10.1016/j.ic.2012.10.013openalex-snapshot
Permanent does not have succinct polynomial size arithmetic circuits of constant depth
inferred← citeshttps://doi.org/10.1016/j.ic.2017.07.002openalex-snapshot
Robust simulations and significant separations
inferred← citeshttps://doi.org/10.1017/cbo9780511979309openalex-snapshot
Quantum Computing since Democritus
inferred← citeshttps://doi.org/10.1090/jams/864openalex-snapshot
Geometric complexity theory V: Efficient algorithms for Noether normalization
inferred← citeshttps://doi.org/10.1109/ccc.2011.25openalex-snapshot
Linear Systems over Finite Abelian Groups
inferred← citeshttps://doi.org/10.1109/ccc.2012.29openalex-snapshot
A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis
inferred← citeshttps://doi.org/10.1109/ccc.2012.37openalex-snapshot
Pseudorandom Generators for Read-Once ACC^0
inferred← citeshttps://doi.org/10.1109/ccc.2012.40openalex-snapshot
Approximating AC^0 by Small Height Decision Trees and a Deterministic Algorithm for #AC^0SAT
inferred← citeshttps://doi.org/10.1109/ccc.2012.44openalex-snapshot
Amplifying Circuit Lower Bounds against Polynomial Time with Applications
inferred← citeshttps://doi.org/10.1109/ccc.2013.18openalex-snapshot
Constructing Hard Functions Using Learning Algorithms
inferred← citeshttps://doi.org/10.1109/ccc.2013.40openalex-snapshot
On Medium-Uniformity and Circuit Lower Bounds
inferred← citeshttps://doi.org/10.1109/ccc.2014.34openalex-snapshot
Mining Circuit Lower Bound Proofs for Meta-algorithms
inferred← citeshttps://doi.org/10.1109/ccc.2014.39openalex-snapshot
Fourier Concentration from Shrinkage
inferred← citeshttps://doi.org/10.1109/focs.2010.72openalex-snapshot
Pseudorandom Generators for CC0[p] and the Fourier Spectrum of Low-Degree Polynomials over Finite Fields
inferred← citeshttps://doi.org/10.1109/focs.2012.15openalex-snapshot
Geometric Complexity Theory V: Equivalence between Blackbox Derandomization of Polynomial Identity Testing and Derandomization of Noether's Normalization Lemma
inferred← citeshttps://doi.org/10.1109/focs.2012.80openalex-snapshot
Faster Algorithms for Rectangular Matrix Multiplication
inferred← citeshttps://doi.org/10.1109/focs.2013.58openalex-snapshot
A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits
inferred← citeshttps://doi.org/10.1109/focs52979.2021.00019openalex-snapshot
Fooling Constant-Depth Threshold Circuits (Extended Abstract)
inferred← citeshttps://doi.org/10.1137/1.9781611973099.77openalex-snapshot
A Satisfiability Algorithm for AC 0
inferred← citeshttps://doi.org/10.1137/1.9781611973730.18openalex-snapshot
Beating Exhaustive Search for Quantified Boolean Formulas and Connections to Circuit Complexity
inferred← citeshttps://doi.org/10.1137/1.9781611975031.18openalex-snapshot
Beating Brute Force for (Quantified) Satisfiability of Circuits of Bounded Treewidth
inferred← citeshttps://doi.org/10.1137/1.9781611975031.67openalex-snapshot
Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor
inferred← citeshttps://doi.org/10.1142/s0219061325500023openalex-snapshot
Learning algorithms versus automatability of Frege systems
inferred← citeshttps://doi.org/10.1145/2034575.2034590openalex-snapshot
SIGACT news complexity theory column 71
inferred← citeshttps://doi.org/10.1145/2090236.2090273openalex-snapshot
On beating the hybrid argument
inferred← citeshttps://doi.org/10.1145/2090236.2090275openalex-snapshot
Marginal hitting sets imply super-polynomial lower bounds for permanent
inferred← citeshttps://doi.org/10.1145/2422436.2422456openalex-snapshot
Space-bounded communication complexity
inferred← citeshttps://doi.org/10.1145/2488608.2488612openalex-snapshot
Natural proofs versus derandomization
inferred← citeshttps://doi.org/10.1145/2488608.2488669openalex-snapshot
Strong ETH holds for regular resolution
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/2792978openalex-snapshot
Substitution-Permutation Networks, Pseudorandom Functions, and Natural Proofs
inferred← citeshttps://doi.org/10.1145/2840728.2840768openalex-snapshot
Satisfiability on Mixed Instances
inferred← citeshttps://doi.org/10.1145/3188745.3188822openalex-snapshot
Quantified derandomization of linear threshold circuits
inferred← citeshttps://doi.org/10.1145/3313276.3316333openalex-snapshot
Bootstrapping results for threshold circuits “just beyond” known lower bounds
inferred← citeshttps://doi.org/10.1145/3798129.3800802openalex-snapshot
Superquadratic Lower Bounds for Depth-2 Linear Threshold Circuits
inferred← citeshttps://doi.org/10.1145/3801091openalex-snapshot
Towards P≠NP from Extended Frege lower bounds
inferred← citeshttps://doi.org/10.1515/9780823295708-025openalex-snapshot
CHAPTER NOTES AND REFERENCES
inferred← citeshttps://doi.org/10.1515/9783110203738.455openalex-snapshot
Chapter 8 Notes and References
inferred← citeshttps://doi.org/10.1587/transinf.2014edp7127openalex-snapshot
A Satisfiability Algorithm for Some Class of Dense Depth Two Threshold Circuits
inferred← citeshttps://doi.org/10.17760/d20486921openalex-snapshot
On approximating by polynomials and several related models
inferred← citeshttps://doi.org/10.4036/iis.2014.1openalex-snapshot
Proving Circuit Lower Bounds in High Uniform Classes
inferred← citeshttps://doi.org/10.4036/iis.2014.27openalex-snapshot
Lower Bounds for Threshold Circuits of Bounded Energy
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.4230/lipics.ccc.2016.19openalex-snapshot
New Non-Uniform Lower Bounds for Uniform Classes
inferred← citeshttps://doi.org/10.4230/lipics.ccc.2016.33openalex-snapshot
Functional Lower Bounds for Arithmetic Circuits and Connections to Boolean Circuit Complexity
inferred← citeshttps://doi.org/10.4230/lipics.isaac.2017.39openalex-snapshot
Dominance Product and High-Dimensional Closest Pair under L_infty
inferred← citeshttps://doi.org/10.4230/lipics.itcs.2017.30openalex-snapshot
What Circuit Classes Can Be Learned with Non-Trivial Savings?
inferred← citeshttps://doi.org/10.4230/lipics.itcs.2022.34openalex-snapshot
Algorithms and Lower Bounds for Comparator Circuits from Shrinkage
inferred← citeshttps://doi.org/10.4230/lipics.stacs.2012.519openalex-snapshot
Stronger Lower Bounds and Randomness-Hardness Trade-Offs Using Associated Algebraic Complexity Classes
inferred← citeshttps://doi.org/10.4230/lipics.stacs.2022.55openalex-snapshot
Superlinear Lower Bounds Based on ETH
inferred← citeshttps://doi.org/10.48550/arxiv.1012.2034openalex-snapshot
Robust Simulations and Significant Separations
inferred← citeshttps://doi.org/10.48550/arxiv.1012.2394openalex-snapshot
NE is not NP Turing Reducible to Nonexpoentially Dense NP Sets
inferred← citeshttps://doi.org/10.48550/arxiv.1107.3127openalex-snapshot
A Satisfiability Algorithm for AC$^0$
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.1212.4548openalex-snapshot
A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits
inferred← citeshttps://doi.org/10.48550/arxiv.1306.4029openalex-snapshot
Satisfiability Algorithms for Restricted Circuit Classes
inferred← citeshttps://doi.org/10.48550/arxiv.1309.0249openalex-snapshot
Algorithms versus Circuit Lower Bounds
inferred← citeshttps://doi.org/10.48550/arxiv.1312.6680openalex-snapshot
Faster all-pairs shortest paths via circuit complexity
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.1404.4852openalex-snapshot
Polynomials Modulo Composite Numbers: Ax-Katz type theorems for the structure of their solution sets
inferred← citeshttps://doi.org/10.48550/arxiv.1611.01706openalex-snapshot
Self-reducible with easy decision version counting problems admit additive error approximation. Connections to counting complexity, exponential time complexity, and circuit lower bounds
inferred← citeshttps://doi.org/10.48550/arxiv.2109.13917openalex-snapshot
Separating Circuits : Switching Lemmas and Random Restrictions
inferred← citeshttps://doi.org/10.5040/9780755625963.0007openalex-snapshot
Chapter Notes and References
inferred← citeshttps://doi.org/10.5120/ijca2019919465openalex-snapshot
P vs NP Solution – Advances in Computational Complexity, Status and Future Scope
inferred← citeshttps://doi.org/10.5555/2722129.2722147openalex-snapshot
Beating exhaustive search for quantified boolean formulas and connections to circuit complexity
inferred← citeshttps://doi.org/10.70675/20c06f35z8a0dz4872z83e0z5bc2fafd8555openalex-snapshot
On the complexity of regular languages
inferred← citeshttps://doi.org/10.7282/t32b8wngopenalex-snapshot
Some applications of randomness in computational complexity
inferred← citeshttps://doi.org/10.7282/t35d8qvqopenalex-snapshot
On circuit complexity classes and iterated matrix multiplication
inferred← citeshttps://doi.org/10.7916/d8zp45ktopenalex-snapshot
Unconditional Lower Bounds in Complexity Theory
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.