On the public citation graph
Lower bounds on monotone complexity of the logical permanent
0 signed · 84 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/bf00263988openalex-snapshot
A new lower bound on the monotone network complexity of Boolean sums
inferredcites →https://doi.org/10.1007/bfb0017292openalex-snapshot
Boolean functions whose monotone complexity is of size n2/log n
inferredcites →https://doi.org/10.1016/0304-3975(79)90008-2openalex-snapshot
Switching functions whose monotone complexity is nearly quadratic
inferredcites →https://doi.org/10.1016/0304-3975(89)90084-4openalex-snapshot
Boolean functions whose monotone complexity is of size n2log n
inferredcites →https://doi.org/10.1137/0202019openalex-snapshot
An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
inferredcites →https://doi.org/10.1137/0204027openalex-snapshot
The Power of Negative Thinking in Multiplying Boolean Matrices
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1006/jcss.1995.1033openalex-snapshot
Monotone Separation of Logarithmic Space from Logarithmic Depth
inferred← citeshttps://doi.org/10.1007/3-540-19487-8_16openalex-snapshot
A fast parallel algorithm for computing all maximal cliques in a graph and the related problems
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/978-1-4612-2566-9_12openalex-snapshot
Bounded Arithmetic and Lower Bounds in Boolean Complexity
inferred← citeshttps://doi.org/10.1007/978-1-4612-2566-9_8openalex-snapshot
On Proving Lower Bounds for Circuit Size
inferred← citeshttps://doi.org/10.1007/978-1-4614-7258-2_26openalex-snapshot
On Small Size Approximation Models
inferred← citeshttps://doi.org/10.1007/978-3-031-23101-8_20openalex-snapshot
Lower Bounds for Monotone q-Multilinear Boolean Circuits
inferred← citeshttps://doi.org/10.1007/978-3-319-08783-2_51openalex-snapshot
Depth Lower Bounds against Circuits with Sparse Orientation
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-319-34171-2_18openalex-snapshot
Some Complete and Intermediate Polynomials in Algebraic Complexity Theory
inferred← citeshttps://doi.org/10.1007/978-3-540-49382-2_29openalex-snapshot
Remarks on Graph Complexity
inferred← citeshttps://doi.org/10.1007/978-3-540-70575-8_4openalex-snapshot
Optimal Cryptographic Hardness of Learning Monotone Functions
inferred← citeshttps://doi.org/10.1007/978-3-642-03456-5_2openalex-snapshot
On Negations in Boolean Networks
inferred← citeshttps://doi.org/10.1007/bf01137685openalex-snapshot
Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
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/bf01978380openalex-snapshot
A method for obtaining efficient lower bounds for monotone complexity
inferred← citeshttps://doi.org/10.1007/bfb0017163openalex-snapshot
Separating the eraser turing machine classes Le, NLe, co-NLe and Pe
inferred← citeshttps://doi.org/10.1007/bfb0029596openalex-snapshot
Restricted branching programs and their computational power
inferred← citeshttps://doi.org/10.1007/s00037-024-00257-0openalex-snapshot
Localizability of the approximation method
inferred← citeshttps://doi.org/10.1007/s00224-014-9574-4openalex-snapshot
Lower Bounds for Tropical Circuits and Dynamic Programs
inferred← citeshttps://doi.org/10.1007/s00224-016-9740-yopenalex-snapshot
Some Complete and Intermediate Polynomials in Algebraic Complexity Theory
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/0012-365x(92)90640-2openalex-snapshot
Matching theory—a sampler: from Dénes König to the present
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/0022-0000(91)90024-yopenalex-snapshot
Expressing combinatorial optimization problems by Linear Programs
inferred← citeshttps://doi.org/10.1016/0196-6774(86)90011-8openalex-snapshot
The NP-completeness column: An ongoing guide
inferred← citeshttps://doi.org/10.1016/0196-6774(86)90020-9openalex-snapshot
The NP-completeness column: An ongoing guide
inferred← citeshttps://doi.org/10.1016/0196-8858(91)90010-gopenalex-snapshot
Coxeter groups and nonuniform complexity
inferred← citeshttps://doi.org/10.1016/b978-0-444-51624-4.50011-3openalex-snapshot
Computational Complexity
inferred← citeshttps://doi.org/10.1016/b978-0-444-88071-0.50019-9openalex-snapshot
The Complexity of Finite Functions
inferred← citeshttps://doi.org/10.1016/j.artint.2004.04.002openalex-snapshot
On the computational complexity of qualitative coalitional games
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.ejc.2007.11.004openalex-snapshot
On digraph coloring problems and treewidth duality
inferred← citeshttps://doi.org/10.1016/j.jcss.2022.05.003openalex-snapshot
Lower bounds for Boolean circuits of bounded negation width
inferred← citeshttps://doi.org/10.1070/rm1986v041n04abeh003385openalex-snapshot
Lower estimates of the dimension of schemes of bounded depth in the basis $ \{\&,\vee,\oplus\}$
inferred← citeshttps://doi.org/10.1070/rm2003v058n05abeh000667openalex-snapshot
Monotone Boolean functions
inferred← citeshttps://doi.org/10.1070/rm2009v064n05abeh004640openalex-snapshot
Some unsolved problems in discrete mathematics and mathematical cybernetics
inferred← citeshttps://doi.org/10.1070/rm2012v067n01abeh004777openalex-snapshot
Computational complexity of Boolean functions
inferred← citeshttps://doi.org/10.1070/sm2012v203n10abeh004270openalex-snapshot
A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials
inferred← citeshttps://doi.org/10.1109/ccc.1997.612325openalex-snapshot
Finite limits and monotone computations: the lower bounds criterion
inferred← citeshttps://doi.org/10.1109/fscs.1990.89582openalex-snapshot
On the power of small-depth threshold circuits
inferred← citeshttps://doi.org/10.1109/lics.2005.31openalex-snapshot
On Digraph Coloring Problems and Treewidth Duality
inferred← citeshttps://doi.org/10.1109/sct.1991.160272openalex-snapshot
Monotone separation of logspace from NC/sup 1/
inferred← citeshttps://doi.org/10.1109/sct.1993.336535openalex-snapshot
On proving lower bounds for circuit size
inferred← citeshttps://doi.org/10.1109/sfcs.1994.365685openalex-snapshot
A lower bound for the monotone depth of connectivity
inferred← citeshttps://doi.org/10.1109/sfcs.1997.646112openalex-snapshot
Separation of the monotone NC hierarchy
inferred← citeshttps://doi.org/10.1137/18m1196339openalex-snapshot
Approximation Limitations of Pure Dynamic Programming
inferred← citeshttps://doi.org/10.1137/s0097539794266766openalex-snapshot
The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
inferred← citeshttps://doi.org/10.1142/s021819670900524xopenalex-snapshot
OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT
inferred← citeshttps://doi.org/10.1145/113413.113415openalex-snapshot
On Datalog vs. polynomial time (extended abstract)
inferred← citeshttps://doi.org/10.1145/167088.167245openalex-snapshot
Monotone monadic SNP and constraint satisfaction
inferred← citeshttps://doi.org/10.1145/2213977.2214024openalex-snapshot
Tight bounds for monotone switching networks via fourier analysis
inferred← citeshttps://doi.org/10.1145/3188745.3188912openalex-snapshot
On the complexity of hazard-free circuits
inferred← citeshttps://doi.org/10.1145/3320123openalex-snapshot
On the Complexity of Hazard-free Circuits
inferred← citeshttps://doi.org/10.1145/3337787openalex-snapshot
Representations of Monotone Boolean Functions by Linear Programs
inferred← citeshttps://doi.org/10.1145/3618260.3649733openalex-snapshot
Quadratic Lower Bounds on the Approximate Stabilizer Rank: A Probabilistic Approach
inferred← citeshttps://doi.org/10.20948/mvk-2022-61openalex-snapshot
Reciprocal inputs in arithmetic and tropical circuits
inferred← citeshttps://doi.org/10.32920/23459144openalex-snapshot
Expressibility Of Constraint Satisfaction Problems In Extensions Of First-Order Logic
inferred← citeshttps://doi.org/10.32920/23459144.v1openalex-snapshot
Expressibility Of Constraint Satisfaction Problems In Extensions Of First-Order Logic
inferred← citeshttps://doi.org/10.4213/rm9322openalex-snapshot
Некоторые нерешенные задачи дискретной математики и математической кибернетики
inferred← citeshttps://doi.org/10.4213/sm7904openalex-snapshot
Об одном методе получения нижних оценок сложности монотонных арифметических схем, вычисляющих действительные многочлены
inferred← citeshttps://doi.org/10.4230/lipics.itcs.2023.74openalex-snapshot
Karchmer-Wigderson Games for Hazard-Free Computation
inferred← citeshttps://doi.org/10.48550/arxiv.1305.3218openalex-snapshot
Computing Cliques is Intractable
inferred← citeshttps://doi.org/10.48550/arxiv.1307.4308openalex-snapshot
An Alternative Proof of the Exponential Monotone Complexity of the Clique Function
inferred← citeshttps://doi.org/10.48550/arxiv.2012.10976openalex-snapshot
Notes on Hazard-Free Circuits
inferred← citeshttps://doi.org/10.5446/15981openalex-snapshot
P, NP and mathematics - a computational complexity perspective
inferred← citeshttps://doi.org/10.5772/37084openalex-snapshot
Provably Secure Cryptographic Constructions
inferred← citeshttps://doi.org/10.70675/b87162c6zd596z4893z84b7z6c743245a72dopenalex-snapshot
Sur les systèmes de formes normales pour représenter efficacement des fonctions multivaluées
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.