On the public citation graph
On computing Boolean connectives of characteristic functions
0 signed · 58 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/3-540-09510-1_44openalex-snapshot
P-selective sets, tally languages, and the behavior of polynomial time reducibilities on NP
inferredcites →https://doi.org/10.1007/3-540-11493-9openalex-snapshot
Group-Theoretic Algorithms and Graph Isomorphism
inferredcites →https://doi.org/10.1007/3-540-16486-3_93openalex-snapshot
The boolean hierarchy: Hardware over NP
inferredcites →https://doi.org/10.1007/3-540-51498-8_4openalex-snapshot
Generalized Boolean hierarchies and Boolean hierarchies over RP
inferredcites →https://doi.org/10.1007/bf01744288openalex-snapshot
P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
inferredcites →https://doi.org/10.1007/bfb0039602openalex-snapshot
Probability one separation of the Boolean hierarchy
inferredcites →https://doi.org/10.1016/0022-0000(84)90068-0openalex-snapshot
The complexity of facets (and some facets of complexity)
inferredcites →https://doi.org/10.1016/0022-0000(88)90010-4openalex-snapshot
Graph isomorphism is in the low hierarchy
inferredcites →https://doi.org/10.1016/0022-0000(88)90039-6openalex-snapshot
The complexity of optimization problems
inferredcites →https://doi.org/10.1016/0022-0000(89)90024-xopenalex-snapshot
PNP[(log )] and sparse turing-complete sets for NP
inferredcites →https://doi.org/10.1016/0022-0000(89)90025-1openalex-snapshot
The strong exponential hierarchy collapses
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(91)90160-4openalex-snapshot
Bounded queries to SAT and the Boolean hierarchy
inferredcites →https://doi.org/10.1016/s0890-5401(03)00091-9openalex-snapshot
Some connections between bounded query classes and non-uniform complexity
inferredcites →https://doi.org/10.1051/ita/1987210404191openalex-snapshot
The difference and truth-table hierarchies for NP
inferredcites →https://doi.org/10.1108/ir.1999.04926fae.001openalex-snapshot
Lecture Notes in Computer Science 1205
inferredcites →https://doi.org/10.1109/psct.1987.10319254openalex-snapshot
Self-Reducible, P-Selective, Near-Testable, and P-Cheatable Sets: The Effect of Internal Structure on the Complexity of a Set
inferredcites →https://doi.org/10.1109/sct.1990.113965openalex-snapshot
The Boolean hierarchy and the polynomial hierarchy: a closer connection
inferredcites →https://doi.org/10.1109/sct.1991.160268openalex-snapshot
Connections between the complexity of unique satisfiability and the threshold behavior of randomized reductions
inferredcites →https://doi.org/10.1137/0217078openalex-snapshot
The Boolean Hierarchy I: Structural Properties
inferredcites →https://doi.org/10.1137/0217080openalex-snapshot
The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
inferredcites →https://doi.org/10.1137/0221045openalex-snapshot
On the Structure of Bounded Queries to Arbitrary NP Sets
inferredcites →https://doi.org/10.1137/s0097539790178069openalex-snapshot
The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1006/inco.2000.2884openalex-snapshot
Bounded Queries, Approximations, and the Boolean Hierarchy
inferred← citeshttps://doi.org/10.1006/jcss.1995.1028openalex-snapshot
On Unique Satisfiability and the Threshold Behavior of Randomized Reductions
inferred← citeshttps://doi.org/10.1007/978-0-387-98197-0_5openalex-snapshot
Complexity of Abstract Argumentation
inferred← citeshttps://doi.org/10.1007/978-3-540-77120-3_14openalex-snapshot
The 1-Versus-2 Queries Problem Revisited
inferred← citeshttps://doi.org/10.1007/978-3-540-87803-2_14openalex-snapshot
Computational Complexity of Semi-stable Semantics in Abstract Argumentation Frameworks
inferred← citeshttps://doi.org/10.1007/978-3-642-03073-4_13openalex-snapshot
Lower Bounds for Kernelizations and Other Preprocessing Procedures
inferred← citeshttps://doi.org/10.1007/bf01371729openalex-snapshot
A relationship between difference hierarchies and relativized polynomial hierarchies
inferred← citeshttps://doi.org/10.1007/bfb0029617openalex-snapshot
On checking versus evaluation of multiple queries
inferred← citeshttps://doi.org/10.1007/bfb0030862openalex-snapshot
Intersection suffices for Boolean hierarchy equivalence
inferred← citeshttps://doi.org/10.1007/s00224-008-9126-xopenalex-snapshot
The 1-Versus-2 Queries Problem Revisited
inferred← citeshttps://doi.org/10.1007/s00224-010-9270-yopenalex-snapshot
Lower Bounds for Kernelizations and Other Preprocessing Procedures
inferred← citeshttps://doi.org/10.1007/s00224-011-9381-0openalex-snapshot
Parameterized Random Complexity
inferred← citeshttps://doi.org/10.1007/s10458-013-9224-2openalex-snapshot
Computational complexity and approximability of social welfare optimization in multiagent resource allocation
inferred← citeshttps://doi.org/10.1007/s10472-015-9461-yopenalex-snapshot
Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games
inferred← citeshttps://doi.org/10.1016/j.artint.2009.09.001openalex-snapshot
The computational complexity of ideal semantics
inferred← citeshttps://doi.org/10.1016/j.artint.2013.06.004openalex-snapshot
Parametric properties of ideal semantics
inferred← citeshttps://doi.org/10.1016/j.artint.2015.07.006openalex-snapshot
Characteristics of multiple viewpoints in abstract argumentation
inferred← citeshttps://doi.org/10.1016/s0022-0000(03)00042-4openalex-snapshot
Completeness results for graph isomorphism
inferred← citeshttps://doi.org/10.1109/ccc.1998.694595openalex-snapshot
A note on the hardness of tree isomorphism
inferred← citeshttps://doi.org/10.1109/ccc.2008.32openalex-snapshot
Amplifying ZPP^SAT[1] and the Two Queries Problem
inferred← citeshttps://doi.org/10.1109/lics.1995.523245openalex-snapshot
Relativized logspace and generalized quantifiers over finite structures
inferred← citeshttps://doi.org/10.1109/sct.1991.160268openalex-snapshot
Connections between the complexity of unique satisfiability and the threshold behavior of randomized reductions
inferred← citeshttps://doi.org/10.1137/0221045openalex-snapshot
On the Structure of Bounded Queries to Arbitrary NP Sets
inferred← citeshttps://doi.org/10.1137/s0097539794261970openalex-snapshot
Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
inferred← citeshttps://doi.org/10.2307/2275546openalex-snapshot
Relativized logspace and generalized quantifiers over finite ordered structures
inferred← citeshttps://doi.org/10.3233/aac-210018openalex-snapshot
Revisiting initial sets in abstract argumentation
inferred← citeshttps://doi.org/10.5555/2343896.2343967openalex-snapshot
Complexity and approximability of social welfare optimization in multiagent resource allocation
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.