On the public citation graph
On the combinational complexity of certain symmetric Boolean functions
0 signed · 61 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/bf02246615openalex-snapshot
Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
inferredcites →https://doi.org/10.1016/0304-3975(75)90018-3openalex-snapshot
A class of boolean functions with linear combinational complexity
inferredcites →https://doi.org/10.1016/0304-3975(76)90073-6openalex-snapshot
The combinational complexity of equivalence
inferredcites →https://doi.org/10.1137/0206030openalex-snapshot
A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
inferredcites →https://doi.org/10.1145/321724.321731openalex-snapshot
Computational Work and Time on Finite Machines
inferredcites →https://doi.org/10.1145/321879.321882openalex-snapshot
Bounds to Complexities of Networks for Sorting and for Switching
inferredcites →https://doi.org/10.1145/800116.803750openalex-snapshot
A 2.5 n-lower bound on the combinational complexity of Boolean functions
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1007/11821069_16openalex-snapshot
Concrete Multiplicative Complexity of Symmetric Functions
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/978-3-319-90530-3_2openalex-snapshot
Lower Bounds for Unrestricted Boolean Circuits: Open Problems
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-20712-9_12openalex-snapshot
Gate Elimination for Linear Functions and New Feebly Secure Constructions
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-30642-6_9openalex-snapshot
Computing All MOD-Functions Simultaneously
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/978-3-662-48865-2_6openalex-snapshot
The Symmetric Property of Boolean Functions
inferred← citeshttps://doi.org/10.1007/bf01268142openalex-snapshot
PI k mass production and an optimal circuit for the Ne?iporuk slice
inferred← citeshttps://doi.org/10.1007/bfb0024011openalex-snapshot
On the planar monotone computation of threshold functions
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/s10958-012-1103-xopenalex-snapshot
Feebly secure cryptographic primitives
inferred← citeshttps://doi.org/10.1007/s10958-012-1104-9openalex-snapshot
Circuit complexity of linear functions: gate elimination and feeble security
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(87)90110-1openalex-snapshot
Models of lower-bounds proofs
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.ipl.2010.01.007openalex-snapshot
New upper bounds on the Boolean circuit complexity of symmetric functions
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.01.030openalex-snapshot
Tight bounds for the multiplicative complexity of symmetric functions
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/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.1016/s0304-3975(99)00182-6openalex-snapshot
On the multiplicative complexity of Boolean functions over the basis (∧,⊕,1)
inferred← citeshttps://doi.org/10.1109/12.106225openalex-snapshot
Depth-size tradeoffs for neural computation
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/isit54713.2023.10206832openalex-snapshot
On the Information Capacity of Nearest Neighbor Representations
inferred← citeshttps://doi.org/10.1109/isit57864.2024.10619486openalex-snapshot
Nearest Neighbor Representations of Neural Circuits
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.1109/tc.1986.1676729openalex-snapshot
Complexity Based on Partitioning of Boolean Circuits and their Relation to Multivalued Circuits
inferred← citeshttps://doi.org/10.1109/tit.1982.1056592openalex-snapshot
On the power of straight- line computations in finite fields
inferred← citeshttps://doi.org/10.1137/0220032openalex-snapshot
A $4n$ Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions
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/3519935.3520010openalex-snapshot
The exact complexity of pseudorandom functions and the black-box natural proof barrier for bootstrapping results in computational complexity
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.1515/dma-2021-0031openalex-snapshot
On the complexity of monotone circuits for threshold symmetric Boolean functions
inferred← citeshttps://doi.org/10.22331/q-2024-04-09-1312openalex-snapshot
Quantum advantage in temporally flat measurement-based quantum computation
inferred← citeshttps://doi.org/10.23919/date.2018.8342026openalex-snapshot
Improving circuit size upper bounds using SAT-solvers
inferred← citeshttps://doi.org/10.3103/s1066369x14050041openalex-snapshot
Upper bounds for the formula size of symmetric Boolean functions
inferred← citeshttps://doi.org/10.3724/sp.j.1001.2010.03671openalex-snapshot
Cryptographic Properties of Several Classes of Rotation Symmetric Boolean Functions
inferred← citeshttps://doi.org/10.4213/dm1547openalex-snapshot
О сложности монотонных схем для пороговых симметрических булевых функций
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.1208.3874openalex-snapshot
Upper bounds for the formula size of the majority function
inferred← citeshttps://doi.org/10.5555/3091125.3091195openalex-snapshot
Phase Transitions in Possible Dynamics of Cellular and Graph Automata Models of Sparsely Interconnected Multi-Agent Systems
inferred← citeshttps://doi.org/10.5772/37084openalex-snapshot
Provably Secure Cryptographic Constructions
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.