On the public citation graph
The Power of the Middle Bit of a #P Function
0 signed · 87 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/bf00289117openalex-snapshot
The complexity of combinatorial problems with succinct input representation
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/bf01201812openalex-snapshot
On the power of generalized Mod-classes
inferredcites →https://doi.org/10.1007/bf01202284openalex-snapshot
On the power of deterministic reductions to C=P
inferredcites →https://doi.org/10.1007/bf01371729openalex-snapshot
A relationship between difference hierarchies and relativized polynomial hierarchies
inferredcites →https://doi.org/10.1007/bfb0028987openalex-snapshot
On the power of parity polynomial time
inferredcites →https://doi.org/10.1007/bfb0029603openalex-snapshot
On the power of uniform families of constant depth threshold circuits
inferredcites →https://doi.org/10.1007/bfb0036487openalex-snapshot
Two remarks on the power of counting
inferredcites →https://doi.org/10.1016/0020-0190(82)90139-9openalex-snapshot
Some observations on the probabilistic algorithms and NP-hard problems
inferredcites →https://doi.org/10.1016/0022-0000(83)90027-2openalex-snapshot
A low and a high hierarchy within NP
inferredcites →https://doi.org/10.1016/0022-0000(92)90022-bopenalex-snapshot
Turing machines with few accepting computations and low sets for PP
inferredcites →https://doi.org/10.1016/0304-3975(75)90016-xopenalex-snapshot
A comparison of polynomial time reducibilities
inferredcites →https://doi.org/10.1016/0304-3975(79)90044-6openalex-snapshot
The Complexity of Computing the Permanent
inferredcites →https://doi.org/10.1016/0304-3975(86)90135-0openalex-snapshot
NP is as easy as detecting unique solutions
inferredcites →https://doi.org/10.1016/0304-3975(86)90165-9openalex-snapshot
On the construction of parallel computers from various bases of boolean functions
inferredcites →https://doi.org/10.1016/0304-3975(90)90081-ropenalex-snapshot
Relations among mod-classes
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(92)90369-qopenalex-snapshot
Polynomial-time 1-Turing reductions from #PH to #P
inferredcites →https://doi.org/10.1016/0890-5401(89)90063-1openalex-snapshot
Enumerative counting is hard
inferredcites →https://doi.org/10.1016/s0019-9958(82)80019-3openalex-snapshot
Robustness of probabilistic computational complexity classes under definitional perturbations
inferredcites →https://doi.org/10.1051/ita/1987210404191openalex-snapshot
The difference and truth-table hierarchies for NP
inferredcites →https://doi.org/10.1109/fscs.1990.89583openalex-snapshot
ON ACC and threshold circuits
inferredcites →https://doi.org/10.1109/sct.1988.5281openalex-snapshot
An oracle characterization of the counting hierarchy
inferredcites →https://doi.org/10.1109/sct.1989.41826openalex-snapshot
Turning machines with few accepting computations and low sets for PP
inferredcites →https://doi.org/10.1109/sct.1991.160239openalex-snapshot
PP is closed under truth-table reductions
inferredcites →https://doi.org/10.1109/sct.1991.160264openalex-snapshot
Relating equivalence and reducibility to sparse sets
inferredcites →https://doi.org/10.1109/sfcs.1989.63527openalex-snapshot
On the computational power of PP and (+)P
inferredcites →https://doi.org/10.1109/sfcs.1989.63538openalex-snapshot
A note on the power of threshold circuits
inferredcites →https://doi.org/10.1137/0206049openalex-snapshot
Computational Complexity of Probabilistic Turing Machines
inferredcites →https://doi.org/10.1137/0220053openalex-snapshot
PP is as Hard as the Polynomial-Time Hierarchy
inferredcites →https://doi.org/10.1145/103418.103426openalex-snapshot
PP is closed under intersection
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/28395.28404openalex-snapshot
Algebraic methods in the theory of lower bounds for Boolean circuit complexity
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.1002/malq.200710016openalex-snapshot
On the complexity of the pancake problem
inferred← citeshttps://doi.org/10.1006/inco.1996.0080openalex-snapshot
Gap-Definability as a Closure Property
inferred← citeshttps://doi.org/10.1007/11533719_36openalex-snapshot
On the Complexity of Computing the Logarithm and Square Root Functions on a Complex Domain
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_48openalex-snapshot
Gap-definability as a closure property
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_1openalex-snapshot
Time, Hardware, and Uniformity
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-642-24508-4openalex-snapshot
Boolean Function Complexity: Advances and Frontiers
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/bf01201812openalex-snapshot
On the power of generalized Mod-classes
inferred← citeshttps://doi.org/10.1007/bfb0055799openalex-snapshot
Average-case intractability vs. worst-case intractability
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/s00153-017-0560-9openalex-snapshot
Uniform proofs of ACC representations
inferred← citeshttps://doi.org/10.1007/s00153-022-00828-4openalex-snapshot
Implicit recursion-theoretic characterizations of counting classes
inferred← citeshttps://doi.org/10.1007/s002240000004openalex-snapshot
On the Power of Generalized MOD-Classes
inferred← citeshttps://doi.org/10.1007/s002240000126openalex-snapshot
Exponential Sums and Circuits with a Single Threshold Gate and Mod-Gates
inferred← citeshttps://doi.org/10.1007/s00453-013-9823-yopenalex-snapshot
Lower Bounds Against Weakly-Uniform Threshold Circuits
inferred← citeshttps://doi.org/10.1016/j.entcs.2006.08.009openalex-snapshot
On the Complexity of the Pancake Problem
inferred← citeshttps://doi.org/10.1016/j.ic.2020.104627openalex-snapshot
A structured view on weighted counting with relations to counting, quantum computation and applications
inferred← citeshttps://doi.org/10.1016/j.jco.2006.05.007openalex-snapshot
On the complexity of computing the logarithm and square root functions on a complex domain
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.tcs.2005.10.013openalex-snapshot
On learning embedded midbit functions
inferred← citeshttps://doi.org/10.1016/s0304-3975(98)00061-9openalex-snapshot
Relating polynomial time to constant depth
inferred← citeshttps://doi.org/10.1051/ita/1996300100011openalex-snapshot
Relationships among $PL$, $\#L$, and the determinant
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.2011.36openalex-snapshot
Non-uniform ACC Circuit Lower Bounds
inferred← citeshttps://doi.org/10.1109/sct.1993.336531openalex-snapshot
On the power of generalized MOD-classes
inferred← citeshttps://doi.org/10.1109/sct.1994.315797openalex-snapshot
Relationships among PL, #L, and the determinant
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/sct.1995.514868openalex-snapshot
On the power of number-theoretic operations with respect to counting
inferred← citeshttps://doi.org/10.1137/s0097539792233907openalex-snapshot
A Uniform Circuit Lower Bound for the Permanent
inferred← citeshttps://doi.org/10.1145/2034575.2034590openalex-snapshot
SIGACT news complexity theory column 71
inferred← citeshttps://doi.org/10.1515/9783110889178.115openalex-snapshot
The complexity of counting problems
inferred← citeshttps://doi.org/10.4086/cjtcs.1999.007openalex-snapshot
The Permanent Requires Large Uniform Threshold Circuits.
inferred← citeshttps://doi.org/10.48550/arxiv.1111.1261openalex-snapshot
A Casual Tour Around a Circuit Complexity Bound
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.