On the public citation graph
Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
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.1007/bf02252909openalex-snapshot
Berechnungen in partiellen Algebren endlichen Typs
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1002/malq.19860321912openalex-snapshot
A Gödel Theorem on Network Complexity Lower Bounds
inferred← citeshttps://doi.org/10.1007/11821069_47openalex-snapshot
Reductions for Monotone Boolean Circuits
inferred← citeshttps://doi.org/10.1007/3-540-07407-4_10openalex-snapshot
The network-complexity of equivalence and other applications of the network complexity
inferred← citeshttps://doi.org/10.1007/3-540-07407-4_9openalex-snapshot
The complexity of negation-limited networks — A brief survey
inferred← citeshttps://doi.org/10.1007/3-540-08353-7_135openalex-snapshot
Graph-theoretic arguments in low-level complexity
inferred← citeshttps://doi.org/10.1007/3-540-45687-2_29openalex-snapshot
An Explicit Lower Bound of 5n − o(n) for Boolean Circuits
inferred← citeshttps://doi.org/10.1007/3-540-54458-5_68openalex-snapshot
Nonlinear lower bounds on the number of processors of circuits with sublinear separators
inferred← citeshttps://doi.org/10.1007/3-540-55210-3_191openalex-snapshot
A nonlinear lower bound on the practical combinational complexity
inferred← citeshttps://doi.org/10.1007/978-3-030-68195-1_9openalex-snapshot
On the Power of Nondeterministic Circuits and Co-Nondeterministic Circuits
inferred← citeshttps://doi.org/10.1007/978-3-319-21398-9_17openalex-snapshot
Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits
inferred← citeshttps://doi.org/10.1007/978-3-319-21398-9_23openalex-snapshot
Lower Bounds for the Size of Nondeterministic Circuits
inferred← citeshttps://doi.org/10.1007/978-3-642-02777-2_5openalex-snapshot
Finding Efficient Circuits Using SAT-Solvers
inferred← citeshttps://doi.org/10.1007/978-3-642-03456-5_2openalex-snapshot
On Negations in Boolean Networks
inferred← citeshttps://doi.org/10.1007/978-3-642-13962-8_27openalex-snapshot
Circuit Complexity and Multiplicative Complexity of Boolean Functions
inferred← citeshttps://doi.org/10.1007/978-3-642-22993-0_25openalex-snapshot
An Elementary Proof of a 3n − o(n) Lower Bound on the Circuit Complexity of Affine Dispersers
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-30870-3_44openalex-snapshot
A 5n − o(n) Lower Bound on the Circuit Size over U 2 of a Linear Boolean Function
inferred← citeshttps://doi.org/10.1007/bf00264601openalex-snapshot
Complexity hierarchies for Boolean functions
inferred← citeshttps://doi.org/10.1007/bf00289499openalex-snapshot
Nearly optimal hierarchies for network and formula size
inferred← citeshttps://doi.org/10.1007/bf01683282openalex-snapshot
On the combinational complexity of certain symmetric Boolean functions
inferred← citeshttps://doi.org/10.1007/bfb0024012openalex-snapshot
Planar circuits have short specifications
inferred← citeshttps://doi.org/10.1007/s00037-023-00246-9openalex-snapshot
Improving $$3N$$ Circuit Complexity Lower Bounds
inferred← citeshttps://doi.org/10.1007/s00224-014-9590-4openalex-snapshot
New Lower Bounds on Circuit Size of Multi-output Functions
inferred← citeshttps://doi.org/10.1007/s10598-013-9166-1openalex-snapshot
Lower bound on the complexity of finding polynomials of Boolean functions in the class of circuits with separated variables
inferred← citeshttps://doi.org/10.1007/s10703-017-0300-0openalex-snapshot
On compiling Boolean circuits optimized for secure multi-party computation
inferred← citeshttps://doi.org/10.1016/0020-0190(85)90035-3openalex-snapshot
Linear lower bounds on unbounded fan-in boolean circuits
inferred← citeshttps://doi.org/10.1016/0304-3975(76)90073-6openalex-snapshot
The combinational complexity of equivalence
inferred← citeshttps://doi.org/10.1016/0304-3975(80)90074-2openalex-snapshot
A 3n-lower bound on the network complexity of Boolean functions
inferred← citeshttps://doi.org/10.1016/0304-3975(83)90029-4openalex-snapshot
A Boolean function requiring 3n network size
inferred← citeshttps://doi.org/10.1016/0304-3975(83)90105-6openalex-snapshot
Size bounds for superconcentrators
inferred← citeshttps://doi.org/10.1016/0304-3975(85)90030-1openalex-snapshot
An Ω(n43) lower bound on the monotone network complexity of the nth degree convolution
inferred← citeshttps://doi.org/10.1016/0304-3975(91)90052-4openalex-snapshot
The complexity of the parity function in unbounded fan-in, unbounded depth circuits
inferred← citeshttps://doi.org/10.1016/0304-3975(94)00269-oopenalex-snapshot
A nonlinear lower bound on the practical combinational complexity
inferred← citeshttps://doi.org/10.1016/0890-5401(91)90041-yopenalex-snapshot
Nonlinear lower bounds on the number of processors of circuits with sublinear separators
inferred← citeshttps://doi.org/10.1016/j.dam.2024.09.023openalex-snapshot
Notes on Boolean read- k and multilinear circuits
inferred← citeshttps://doi.org/10.1016/j.jcss.2018.04.005openalex-snapshot
On the limits of gate elimination
inferred← citeshttps://doi.org/10.1016/j.tcs.2008.08.009openalex-snapshot
Reductions for monotone Boolean circuits
inferred← citeshttps://doi.org/10.1016/j.tcs.2016.05.005openalex-snapshot
Correlation bounds and #SAT algorithms for small linear-size circuits
inferred← citeshttps://doi.org/10.1016/j.tcs.2017.11.008openalex-snapshot
Gate elimination: Circuit size lower bounds and #SAT upper bounds
inferred← citeshttps://doi.org/10.1016/j.tcs.2020.03.005openalex-snapshot
Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth
inferred← citeshttps://doi.org/10.1016/s0019-9958(82)90382-5openalex-snapshot
Circuit-size lower bounds and non-reducibility to sparse sets
inferred← citeshttps://doi.org/10.1016/s0049-237x(09)70441-0openalex-snapshot
The Network Complexity and the Breadth of Boolean Functions
inferred← citeshttps://doi.org/10.1109/focs.2016.19openalex-snapshot
A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function
inferred← citeshttps://doi.org/10.1109/sfcs.1981.10openalex-snapshot
An O(N4/3) lower bound on the mono tone network complexity of N-TH degree convolution
inferred← citeshttps://doi.org/10.1145/3519935.3519976openalex-snapshot
3.1 n − o ( n ) circuit lower bounds for explicit functions
inferred← citeshttps://doi.org/10.1145/602220.602223openalex-snapshot
Cosmological lower bound on the circuit complexity of a small problem in logic
inferred← citeshttps://doi.org/10.1145/800116.803750openalex-snapshot
A 2.5 n-lower bound on the combinational complexity of Boolean functions
inferred← citeshttps://doi.org/10.20948/dms-2022-14openalex-snapshot
Improvement of circuit complexity lower bound for parity function in one infinite basis
inferred← citeshttps://doi.org/10.20948/mvk-2022-81openalex-snapshot
Circuit complexity lower bound for parity function in one infinite basis
inferred← citeshttps://doi.org/10.3103/s0027132215050083openalex-snapshot
Upper estimate of realization complexity of linear functions in a basis consisting of multi-input elements
inferred← citeshttps://doi.org/10.3103/s0278641913010032openalex-snapshot
The circuit complexity of checking polynomiality for functions over residue ring modulo a composite number is linear
inferred← citeshttps://doi.org/10.4230/lipics.mfcs.2016.45openalex-snapshot
Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework
inferred← citeshttps://doi.org/10.48550/arxiv.1207.5321openalex-snapshot
Cancellation-free circuits: An approach for proving superlinear lower bounds for linear Boolean operators
inferred← citeshttps://doi.org/10.48550/arxiv.1811.01347openalex-snapshot
Some Results on the Circuit Complexity of Bounded Width Circuits and Nondeterministic Circuits
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.