On the public citation graph
The complexity of combinatorial problems with succinct input representation
0 signed · 296 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-08342-1_37openalex-snapshot
On the difference between one and many
inferredcites →https://doi.org/10.1007/3-540-10856-4_70openalex-snapshot
The complexity of manipulating hierarchically defined sets of rectangles
inferredcites →https://doi.org/10.1007/3-540-13883-8_72openalex-snapshot
A new characterization of BPP
inferredcites →https://doi.org/10.1007/3-540-16761-7_71openalex-snapshot
Hierarchical planarity testing algorithms
inferredcites →https://doi.org/10.1007/3-540-16761-7_93openalex-snapshot
More complicated questions about maxima and minima, and some closures of NP
inferredcites →https://doi.org/10.1007/bfb0009651openalex-snapshot
Two remarks on the power of counting
inferredcites →https://doi.org/10.1007/bfb0030338openalex-snapshot
The complexity of problems concerning graphs with regularities
inferredcites →https://doi.org/10.1007/bfb0036487openalex-snapshot
Two remarks on the power of counting
inferredcites →https://doi.org/10.1007/bfb0064872openalex-snapshot
Weak monadic second order theory of succesor is not elementary-recursive
inferredcites →https://doi.org/10.1016/0020-0190(83)90044-3openalex-snapshot
BPP and the polynomial hierarchy
inferredcites →https://doi.org/10.1016/0304-3975(76)90061-xopenalex-snapshot
The polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/0304-3975(76)90062-1openalex-snapshot
Complete sets and the polynomial-time hierarchy
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(80)90027-4openalex-snapshot
On counting problems and the polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/0304-3975(86)90141-6openalex-snapshot
Some observations on the connection between counting and recursion
inferredcites →https://doi.org/10.1016/0304-3975(87)90049-1openalex-snapshot
More complicated questions about maxima and minima, and some closures of NP
inferredcites →https://doi.org/10.1016/s0019-9958(83)80004-7openalex-snapshot
Succinct representations of graphs
inferredcites →https://doi.org/10.1016/s0019-9958(86)80044-4openalex-snapshot
A decisive characterization of BPP
inferredcites →https://doi.org/10.1017/cbo9781107325630.008openalex-snapshot
Computational Complexity
inferredcites →https://doi.org/10.1109/sfcs.1982.28openalex-snapshot
On the complexity of unique solutions
inferredcites →https://doi.org/10.1109/sfcs.1982.92openalex-snapshot
The complexity of compacting hierarchically specified layouts of integrated circuits
inferredcites →https://doi.org/10.1109/sfcs.1983.21openalex-snapshot
Generalized Kolmogorov complexity and the structure of feasible computations
inferredcites →https://doi.org/10.1109/sfcs.1985.49openalex-snapshot
Separating the polynomial-time hierarchy by oracles
inferredcites →https://doi.org/10.1137/0206049openalex-snapshot
Computational Complexity of Probabilistic Turing Machines
inferredcites →https://doi.org/10.1145/322033.322037openalex-snapshot
Log Space Recognition and Translation of Parenthesis Languages
inferredcites →https://doi.org/10.1145/62.322435openalex-snapshot
On the complexity of unique solutions
inferredcites →https://doi.org/10.1145/800061.808740openalex-snapshot
The complexity of approximate counting
inferredcites →https://doi.org/10.1145/800070.802199openalex-snapshot
The complexity of facets (and some facets of complexity)
inferredcites →https://doi.org/10.1145/800125.804029openalex-snapshot
Word problems requiring exponential time(Preliminary Report)
inferredcites →https://doi.org/10.1145/990518.990519openalex-snapshot
The circuit value problem is log space complete for P
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.200510010openalex-snapshot
The ultra-weak Ash conjecture and some particular cases
inferred← citeshttps://doi.org/10.1006/inco.1995.1109openalex-snapshot
Complexity Classes of Optimization Functions
inferred← citeshttps://doi.org/10.1006/inco.1996.0080openalex-snapshot
Gap-Definability as a Closure Property
inferred← citeshttps://doi.org/10.1006/inco.1997.2696openalex-snapshot
Succinct Representation, Leaf Languages, and Projection Reductions
inferred← citeshttps://doi.org/10.1006/inco.2001.3084openalex-snapshot
Nonerasing, Counting, and Majority over the Linear Time Hierarchy
inferred← citeshttps://doi.org/10.1006/jcss.1995.1036openalex-snapshot
The Power of the Middle Bit of a #P Function
inferred← citeshttps://doi.org/10.1006/jcss.1996.0059openalex-snapshot
On Closure Properties of #P in the Context of PF∘#P
inferred← citeshttps://doi.org/10.1006/jcss.1997.1516openalex-snapshot
Universally Serializable Computation
inferred← citeshttps://doi.org/10.1006/jcss.1999.1675openalex-snapshot
On TC0, AC0, and Arithmetic Circuits
inferred← citeshttps://doi.org/10.1006/jcss.2000.1729openalex-snapshot
Graph Ramsey Theory and the Polynomial Hierarchy
inferred← citeshttps://doi.org/10.1007/11537311_5openalex-snapshot
Bounds on the Power of Constant-Depth Quantum Circuits
inferred← citeshttps://doi.org/10.1007/11537311_8openalex-snapshot
Decidable Membership Problems for Finite Recurrent Systems over Sets of Naturals
inferred← citeshttps://doi.org/10.1007/3-540-18088-5_46openalex-snapshot
The logarithmic alternation hierarchy collapses: $$A\Sigma _2^\mathcal{L} = A\Pi _2^\mathcal{L}$$
inferred← citeshttps://doi.org/10.1007/3-540-28520-2_6openalex-snapshot
Randomized Algorithms and Complexity Classes
inferred← citeshttps://doi.org/10.1007/3-540-28520-2_8openalex-snapshot
Other Public-Key Cryptosystems and Protocols
inferred← citeshttps://doi.org/10.1007/3-540-36494-3_47openalex-snapshot
Competing Provers Yield Improved Karp-Lipton Collapse Results
inferred← citeshttps://doi.org/10.1007/3-540-44450-5_13openalex-snapshot
Arithmetic Circuits and Polynomial Replacement Systems
inferred← citeshttps://doi.org/10.1007/3-540-44612-5_28openalex-snapshot
Subtractive Reductions and Complete Problems for Counting Complexity Classes
inferred← citeshttps://doi.org/10.1007/3-540-45655-4_59openalex-snapshot
On Reachability in Graphs with Bounded Independence Number
inferred← citeshttps://doi.org/10.1007/3-540-45841-7_25openalex-snapshot
On Quantum Computation with Some Restricted Amplitudes
inferred← citeshttps://doi.org/10.1007/3-540-46583-9_5openalex-snapshot
A Generalized Quantifier Concept in Computational Complexity Theory
inferred← citeshttps://doi.org/10.1007/3-540-48321-7_9openalex-snapshot
Restrictive acceptance suffices for equivalence problems
inferred← citeshttps://doi.org/10.1007/3-540-51083-4_77openalex-snapshot
Succinct representations of counting problems
inferred← citeshttps://doi.org/10.1007/3-540-52282-4_31openalex-snapshot
Counting classes: Thresholds, parity, mods, and fewness
inferred← citeshttps://doi.org/10.1007/3-540-52292-1_20openalex-snapshot
The complexity of graph problems for succinctly represented graphs
inferred← citeshttps://doi.org/10.1007/3-540-52846-6_101openalex-snapshot
On matroids and hierarchical graphs
inferred← citeshttps://doi.org/10.1007/3-540-54458-5_76openalex-snapshot
On the complexity of graph reconstruction
inferred← citeshttps://doi.org/10.1007/3-540-54967-6_73openalex-snapshot
Is BP.⊕ $$\mathcal{P}$$ a probabilistic class?
inferred← citeshttps://doi.org/10.1007/3-540-55210-3_200openalex-snapshot
Graph isomorphism is low for PP
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-56939-1_63openalex-snapshot
The complexity of approximating PSPACE-complete problems for hierarchical specifications
inferred← citeshttps://doi.org/10.1007/3-540-57785-8_162openalex-snapshot
On different reducibility notions for function classes
inferred← citeshttps://doi.org/10.1007/3-540-57785-8_174openalex-snapshot
The variable membership problem: Succinctness versus complexity
inferred← citeshttps://doi.org/10.1007/3-540-60084-1_75openalex-snapshot
The complexity of searching succinctly represented graphs
inferred← citeshttps://doi.org/10.1007/3-540-61332-3_145openalex-snapshot
A note on uniform circuit lower bounds for the counting hierarchy (extended abstract)
inferred← citeshttps://doi.org/10.1007/978-0-387-35608-2_27openalex-snapshot
Quantum NP and a Quantum Hierarchy
inferred← citeshttps://doi.org/10.1007/978-1-4613-3557-3_15openalex-snapshot
On the Complexity of Min-Max Optimization Problems and their Approximation
inferred← citeshttps://doi.org/10.1007/978-1-4615-3422-8_30openalex-snapshot
The Complexity of Algorithmic Problems on Succinct Instances
inferred← citeshttps://doi.org/10.1007/978-3-030-00338-8_3openalex-snapshot
A Tutorial on Query Answering and Reasoning over Probabilistic Knowledge Bases
inferred← citeshttps://doi.org/10.1007/978-3-030-80049-9_2openalex-snapshot
On Measure Quantifiers in First-Order Arithmetic
inferred← citeshttps://doi.org/10.1007/978-3-030-86772-0_18openalex-snapshot
Explainable AI Using MAP-Independence
inferred← citeshttps://doi.org/10.1007/978-3-031-36978-0_19openalex-snapshot
Structural Complexity of Rational Interactive Proofs
inferred← citeshttps://doi.org/10.1007/978-3-032-31348-5_22openalex-snapshot
Counting Random Oracles for the Polynomial-Time Hierarchy and Quantum Complexity Classes
inferred← citeshttps://doi.org/10.1007/978-3-319-40970-2_3openalex-snapshot
Solution-Graphs of Boolean Formulas and Isomorphism
inferred← citeshttps://doi.org/10.1007/978-3-319-44832-9_4openalex-snapshot
Resistance to Corruption of General Strategic Argumentation
inferred← citeshttps://doi.org/10.1007/978-3-319-61581-3_40openalex-snapshot
The Complexity of Inferences and Explanations in Probabilistic Logic Programming
inferred← citeshttps://doi.org/10.1007/978-3-319-61581-3_9openalex-snapshot
The Descriptive Complexity of Bayesian Network Specifications
inferred← citeshttps://doi.org/10.1007/978-3-319-71008-2_13openalex-snapshot
Optimization of the Parameters of Smoothed Particle Hydrodynamics Method, Using Evolutionary Algorithms
inferred← citeshttps://doi.org/10.1007/978-3-540-24597-1_32openalex-snapshot
Quantum and Classical Complexity Classes: Separations, Collapses, and Closure Properties
inferred← citeshttps://doi.org/10.1007/978-3-540-24749-4_29openalex-snapshot
A Logspace Approximation Scheme for the Shortest Path Problem for Graphs with Bounded Independence Number
inferred← citeshttps://doi.org/10.1007/978-3-540-27836-8_76openalex-snapshot
Word Problems on Compressed Words
inferred← citeshttps://doi.org/10.1007/978-3-540-30538-5_40openalex-snapshot
Complexity of Linear Connectivity Problems in Directed Hypergraphs
inferred← citeshttps://doi.org/10.1007/978-3-540-30570-5_16openalex-snapshot
Privacy in Database Publishing
inferred← citeshttps://doi.org/10.1007/978-3-540-70918-3_12openalex-snapshot
On Defining Integers in the Counting Hierarchy and Proving Arithmetic Circuit Lower Bounds
inferred← citeshttps://doi.org/10.1007/978-3-540-74240-1_29openalex-snapshot
On the Complexity of Kings
inferred← citeshttps://doi.org/10.1007/978-3-540-74240-1_34openalex-snapshot
The Computational Complexity of Monotonicity in Probabilistic Networks
inferred← citeshttps://doi.org/10.1007/978-3-642-22006-7_61openalex-snapshot
Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth
inferred← citeshttps://doi.org/10.1007/978-3-642-22152-1_15openalex-snapshot
On Stopping Evidence Gathering for Diagnostic Bayesian Networks
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/978-3-642-32589-2_51openalex-snapshot
Computational Complexity of Smooth Differential Equations
inferred← citeshttps://doi.org/10.1007/978-3-642-54423-1_6openalex-snapshot
False-Name Manipulation in Weighted Voting Games Is Hard for Probabilistic Polynomial Time
inferred← citeshttps://doi.org/10.1007/978-3-662-03927-4_7openalex-snapshot
Polynomial Time and Beyond
inferred← citeshttps://doi.org/10.1007/978-3-662-44465-8_41openalex-snapshot
On the Complexity of Symbolic Verification and Decision Problems in Bit-Vector Logic
inferred← citeshttps://doi.org/10.1007/978-981-95-4839-2_2openalex-snapshot
Closure Properties and Characterizations of TotP
inferred← citeshttps://doi.org/10.1007/bf01200064openalex-snapshot
Three ? P 2 -complete problems in computational learning theory
inferred← citeshttps://doi.org/10.1007/bf01201812openalex-snapshot
On the power of generalized Mod-classes
inferred← citeshttps://doi.org/10.1007/bf01202284openalex-snapshot
On the power of deterministic reductions to C=P
inferred← citeshttps://doi.org/10.1007/bf01371729openalex-snapshot
A relationship between difference hierarchies and relativized polynomial hierarchies
inferred← citeshttps://doi.org/10.1007/bf01578841openalex-snapshot
Generalized theorems on relationships among reducibility notions to certain complexity classes
inferred← citeshttps://doi.org/10.1007/bf01578845openalex-snapshot
On the complexity of graph reconstruction
inferred← citeshttps://doi.org/10.1007/bf02582920openalex-snapshot
SeparatingPH fromPP by relativization
inferred← citeshttps://doi.org/10.1007/bf03167537openalex-snapshot
Efficient verification of Tunnell’s criterion
inferred← citeshttps://doi.org/10.1007/bfb0020802openalex-snapshot
Randomized polynomials, threshold circuits, and the polynomial hierarchy
inferred← citeshttps://doi.org/10.1007/bfb0023451openalex-snapshot
THE OPERATORS MIN AND MAX ON THE POLYNOMIAL HIERARCHY
inferred← citeshttps://doi.org/10.1007/bfb0029632openalex-snapshot
Vector language: Simple description of hard instances
inferred← citeshttps://doi.org/10.1007/bfb0029956openalex-snapshot
The complexity of policy evaluation for finite-horizon partially-observable Markov decision processes
inferred← citeshttps://doi.org/10.1007/bfb0035795openalex-snapshot
A combinatorial technique for separating counting complexity classes
inferred← citeshttps://doi.org/10.1007/bfb0039598openalex-snapshot
The correlation between the complexities of the non-hierarchical and hierarchical versions of graph problems
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/s00037-009-0260-xopenalex-snapshot
On Defining Integers And Proving Arithmetic Circuit Lower Bounds
inferred← citeshttps://doi.org/10.1007/s00037-011-0002-8openalex-snapshot
Interpolation in Valiant’s Theory
inferred← citeshttps://doi.org/10.1007/s00037-013-0079-3openalex-snapshot
Monomials in Arithmetic Circuits: Complete Problems in the Counting Hierarchy
inferred← citeshttps://doi.org/10.1007/s00037-016-0124-0openalex-snapshot
The Minimum Oracle Circuit Size Problem
inferred← citeshttps://doi.org/10.1007/s00037-020-00197-5openalex-snapshot
The Robustness of LWPP and WPP, with an Application to Graph Reconstruction
inferred← citeshttps://doi.org/10.1007/s00224-007-2034-7openalex-snapshot
Polynomial-Space Decidable Membership Problems for Recurrent Systems over Sets of Natural Numbers
inferred← citeshttps://doi.org/10.1007/s00224-008-9127-9openalex-snapshot
On the Autoreducibility of Functions
inferred← citeshttps://doi.org/10.1007/s00224-022-10106-8openalex-snapshot
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms
inferred← citeshttps://doi.org/10.1007/s002240000080openalex-snapshot
The Chain Method to Separate Counting Classes
inferred← citeshttps://doi.org/10.1007/s002240000109openalex-snapshot
On the Computational Complexity of Some Classical Equivalence Relations on Boolean Functions
inferred← citeshttps://doi.org/10.1007/s00453-013-9823-yopenalex-snapshot
Lower Bounds Against Weakly-Uniform Threshold Circuits
inferred← citeshttps://doi.org/10.1007/s10472-023-09874-xopenalex-snapshot
Controlling weighted voting games by deleting or adding players with or without changing the quota
inferred← citeshttps://doi.org/10.1007/s10849-015-9218-3openalex-snapshot
Dependence Logic with a Majority Quantifier
inferred← citeshttps://doi.org/10.1007/s11229-025-05406-8openalex-snapshot
Counting in Goodman and Quine’s constructive nominalism
inferred← citeshttps://doi.org/10.1007/s13218-024-00843-yopenalex-snapshot
Towards a Logical Foundation of Randomized Computation: Doctoral Thesis Abstract
inferred← citeshttps://doi.org/10.1007/s42113-019-00032-3openalex-snapshot
Computational Resource Demands of a Predictive Bayesian Brain
inferred← citeshttps://doi.org/10.1016/0004-3702(96)00014-8openalex-snapshot
The complexity of searching implicit graphs
inferred← citeshttps://doi.org/10.1016/0020-0190(91)90035-gopenalex-snapshot
An oracle separating ΘP from PPPH
inferred← citeshttps://doi.org/10.1016/0020-0190(91)90140-dopenalex-snapshot
Probabilistic polynomial time is closed under parity reductions
inferred← citeshttps://doi.org/10.1016/0020-0190(91)90232-7openalex-snapshot
On matroids and hierarchial graphs
inferred← citeshttps://doi.org/10.1016/0020-0190(92)90002-dopenalex-snapshot
On the power of enumerative counting
inferred← citeshttps://doi.org/10.1016/0020-0190(92)90021-mopenalex-snapshot
A note on the permanent value problem
inferred← citeshttps://doi.org/10.1016/0020-0190(92)90086-bopenalex-snapshot
On the closure of certain function classes under integer division by polynomially-bounded functions
inferred← citeshttps://doi.org/10.1016/0020-0190(94)00068-9openalex-snapshot
A note on SpanP functions
inferred← citeshttps://doi.org/10.1016/0020-0190(94)90123-6openalex-snapshot
Upward separation for FewP and related classes
inferred← citeshttps://doi.org/10.1016/0022-0000(88)90030-xopenalex-snapshot
Parallel computation with threshold functions
inferred← citeshttps://doi.org/10.1016/0022-0000(91)90040-copenalex-snapshot
Relativized counting classes: Relations among thresholds, parity, and mods
inferred← citeshttps://doi.org/10.1016/0022-0000(92)90004-3openalex-snapshot
The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
inferred← citeshttps://doi.org/10.1016/0022-0000(92)90022-bopenalex-snapshot
Turing machines with few accepting computations and low sets for PP
inferred← citeshttps://doi.org/10.1016/0022-0000(93)90006-iopenalex-snapshot
A complexity theory for feasible closure properties
inferred← citeshttps://doi.org/10.1016/0304-3975(86)90141-6openalex-snapshot
Some observations on the connection between counting and recursion
inferred← citeshttps://doi.org/10.1016/0304-3975(92)90073-oopenalex-snapshot
Generalizations of Opt P to the polynomial hierarchy
inferred← citeshttps://doi.org/10.1016/0304-3975(92)90084-sopenalex-snapshot
Counting classes: thresholds, parity, mods, and fewness
inferred← citeshttps://doi.org/10.1016/0304-3975(92)90125-yopenalex-snapshot
A uniform approach to define complexity classes
inferred← citeshttps://doi.org/10.1016/0304-3975(92)90333-bopenalex-snapshot
Restricted relativizations of probabilistic polynomial time
inferred← citeshttps://doi.org/10.1016/0304-3975(92)90369-qopenalex-snapshot
Polynomial-time 1-Turing reductions from #PH to #P
inferred← citeshttps://doi.org/10.1016/0304-3975(93)90020-topenalex-snapshot
On sparse hard sets for counting classes
inferred← citeshttps://doi.org/10.1016/0304-3975(93)90214-eopenalex-snapshot
Probabilistic polynomials, AC0 functions and the polynomial-time hierarchy
inferred← citeshttps://doi.org/10.1016/0890-5401(89)90012-6openalex-snapshot
The logarithmic alternation hierarchy collapses: AΣ2L = AΠ2L
inferred← citeshttps://doi.org/10.1016/j.apal.2023.103341openalex-snapshot
Towards logical foundations for probabilistic computation
inferred← citeshttps://doi.org/10.1016/j.artint.2014.10.001openalex-snapshot
Most frugal explanations in Bayesian networks
inferred← citeshttps://doi.org/10.1016/j.artint.2018.06.001openalex-snapshot
The complexity of Bayesian networks specified by propositional and relational languages
inferred← citeshttps://doi.org/10.1016/j.artint.2019.07.001openalex-snapshot
On the complexity of inconsistency measurement
inferred← citeshttps://doi.org/10.1016/j.artint.2020.103344openalex-snapshot
Handling and measuring inconsistency in non-monotonic logics
inferred← citeshttps://doi.org/10.1016/j.artint.2021.103474openalex-snapshot
Open-world probabilistic databases: Semantics, algorithms, complexity
inferred← citeshttps://doi.org/10.1016/j.artint.2023.103884openalex-snapshot
On measuring inconsistency in definite and indefinite databases with denial constraints
inferred← citeshttps://doi.org/10.1016/j.artint.2024.104197openalex-snapshot
On measuring inconsistency in graph databases with regular path constraints
inferred← citeshttps://doi.org/10.1016/j.cosrev.2008.02.001openalex-snapshot
The consequences of eliminating NP solutions
inferred← citeshttps://doi.org/10.1016/j.dam.2007.04.023openalex-snapshot
Semidefinite programming and arithmetic circuit evaluation
inferred← citeshttps://doi.org/10.1016/j.ic.2004.10.009openalex-snapshot
Quantum and classical complexity classes: Separations, collapses, and closure properties
inferred← citeshttps://doi.org/10.1016/j.ic.2005.01.002openalex-snapshot
Competing provers yield improved Karp–Lipton collapse results
inferred← citeshttps://doi.org/10.1016/j.ic.2010.09.002openalex-snapshot
Extensions of MSO and the monadic counting hierarchy
inferred← citeshttps://doi.org/10.1016/j.ic.2012.10.013openalex-snapshot
Permanent does not have succinct polynomial size arithmetic circuits of constant depth
inferred← citeshttps://doi.org/10.1016/j.ic.2014.09.006openalex-snapshot
On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant
inferred← citeshttps://doi.org/10.1016/j.ijar.2011.08.003openalex-snapshot
Most probable explanations in Bayesian networks: Complexity and tractability
inferred← citeshttps://doi.org/10.1016/j.ijar.2012.04.005openalex-snapshot
Same-decision probability: A confidence measure for threshold-based decisions
inferred← citeshttps://doi.org/10.1016/j.ijar.2017.03.014openalex-snapshot
The effect of combination functions on the complexity of relational Bayesian networks
inferred← citeshttps://doi.org/10.1016/j.ijar.2019.04.003openalex-snapshot
The finite model theory of Bayesian network specifications: Descriptive complexity and zero/one laws
inferred← citeshttps://doi.org/10.1016/j.ijar.2019.12.003openalex-snapshot
Complexity results for probabilistic answer set programming
inferred← citeshttps://doi.org/10.1016/j.ijar.2020.07.004openalex-snapshot
The joy of Probabilistic Answer Set Programming: Semantics, complexity, expressivity, inference
inferred← citeshttps://doi.org/10.1016/j.ijar.2022.11.012openalex-snapshot
Motivating explanations in Bayesian networks using MAP-independence
inferred← citeshttps://doi.org/10.1016/j.ipl.2012.08.001openalex-snapshot
Towards a tight hardness–randomness connection between permanent and arithmetic circuit identity testing
inferred← citeshttps://doi.org/10.1016/j.jco.2012.10.001openalex-snapshot
On the complexity of the multivariate resultant
inferred← citeshttps://doi.org/10.1016/j.jcss.2005.11.003openalex-snapshot
A parametric analysis of the state-explosion problem in model checking
inferred← citeshttps://doi.org/10.1016/j.jcss.2017.06.008openalex-snapshot
Characterising the complexity of tissue P systems with fission rules
inferred← citeshttps://doi.org/10.1016/j.tcs.2004.03.004openalex-snapshot
Lower bounds and the hardness of counting properties
inferred← citeshttps://doi.org/10.1016/j.tcs.2009.02.038openalex-snapshot
Linear connectivity problems in directed hypergraphs
inferred← citeshttps://doi.org/10.1016/j.tcs.2018.06.012openalex-snapshot
Subroutines in P systems and closure properties of their complexity classes
inferred← citeshttps://doi.org/10.1016/j.tcs.2023.113928openalex-snapshot
On counting propositional logic and Wagner's hierarchy
inferred← citeshttps://doi.org/10.1016/j.tsc.2005.03.012openalex-snapshot
Subtractive reductions and complete problems for counting complexity classes
inferred← citeshttps://doi.org/10.1016/s0004-3702(02)00271-0openalex-snapshot
Complexity results for structure-based causality
inferred← citeshttps://doi.org/10.1016/s0020-0190(97)00134-8openalex-snapshot
Languages represented by Boolean formulas
inferred← citeshttps://doi.org/10.1016/s0022-0000(05)80024-8openalex-snapshot
Gap-definable counting classes
inferred← citeshttps://doi.org/10.1016/s0022-0000(05)80082-0openalex-snapshot
Simple characterizations of P(#P) and complete problems
inferred← citeshttps://doi.org/10.1016/s0168-0072(98)00057-8openalex-snapshot
Succinctness as a source of complexity in logical formalisms
inferred← citeshttps://doi.org/10.1016/s0304-3975(97)00005-4openalex-snapshot
Unambiguous computations and locally definable acceptance types
inferred← citeshttps://doi.org/10.1051/ita/1996300100011openalex-snapshot
Relationships among $PL$, $\#L$, and the determinant
inferred← citeshttps://doi.org/10.1051/ita/1996300200911openalex-snapshot
Bounded queries to arbitrary sets
inferred← citeshttps://doi.org/10.1051/ita:1999100openalex-snapshot
Immunity and Simplicity for Exact Counting and Other Counting Classes
inferred← citeshttps://doi.org/10.1090/dimacs/035/05openalex-snapshot
Complexity of hierarchically and 1-dimensional periodically specified problems. I: Hardness results
inferred← citeshttps://doi.org/10.1093/logcom/ext073openalex-snapshot
Bijective faithful translations among default logics
inferred← citeshttps://doi.org/10.1098/rspa.1999.0485openalex-snapshot
Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy
inferred← citeshttps://doi.org/10.1103/physrevlett.120.200502openalex-snapshot
Impossibility of Classically Simulating One-Clean-Qubit Model with Multiplicative Error
inferred← citeshttps://doi.org/10.1109/18.971739openalex-snapshot
Links between complexity theory and constrained block coding
inferred← citeshttps://doi.org/10.1109/ccc.1997.612298openalex-snapshot
The general notion of a dot-operator
inferred← citeshttps://doi.org/10.1109/ccc.1997.612309openalex-snapshot
On TC/sup 0/, AC/sup 0/, and arithmetic circuits
inferred← citeshttps://doi.org/10.1109/ccc.1998.694598openalex-snapshot
How to encode a logical structure by an OBDD
inferred← citeshttps://doi.org/10.1109/ccc.1998.694621openalex-snapshot
Complexity issues in Markov decision processes
inferred← citeshttps://doi.org/10.1109/ccc.1999.766271openalex-snapshot
Gaps in bounded query hierarchies
inferred← citeshttps://doi.org/10.1109/ccc.2001.933890openalex-snapshot
Links between complexity theory and constrained block coding
inferred← citeshttps://doi.org/10.1109/ccc.2003.1214410openalex-snapshot
Hardness vs. randomness within alternating time
inferred← citeshttps://doi.org/10.1109/ccc.2006.30openalex-snapshot
On the Complexity of Numerical Analysis
inferred← citeshttps://doi.org/10.1109/focs52979.2021.00103openalex-snapshot
MAJORITY-3SAT (and Related Problems) in Polynomial Time
inferred← citeshttps://doi.org/10.1109/fscs.1990.89600openalex-snapshot
The complexity of finding medians
inferred← citeshttps://doi.org/10.1109/lics.2015.67openalex-snapshot
On the Complexity of Linear Arithmetic with Divisibility
inferred← citeshttps://doi.org/10.1109/sct.1989.41826openalex-snapshot
Turning machines with few accepting computations and low sets for PP
inferred← citeshttps://doi.org/10.1109/sct.1991.160238openalex-snapshot
Counting classes are at least as hard as the polynomial-time hierarchy
inferred← citeshttps://doi.org/10.1109/sct.1991.160240openalex-snapshot
A complexity theory for feasible closure properties
inferred← citeshttps://doi.org/10.1109/sct.1991.160254openalex-snapshot
On one query, self-reducible sets
inferred← citeshttps://doi.org/10.1109/sct.1992.215398openalex-snapshot
On closeness of NP-hard sets to other complexity classes
inferred← citeshttps://doi.org/10.1109/sct.1993.336531openalex-snapshot
On the power of generalized MOD-classes
inferred← citeshttps://doi.org/10.1109/sct.1993.336532openalex-snapshot
On closure properties of Hash P in the context of PF (omicron) Hash P
inferred← citeshttps://doi.org/10.1109/sct.1994.315797openalex-snapshot
Relationships among PL, #L, and the determinant
inferred← citeshttps://doi.org/10.1109/sct.1995.514862openalex-snapshot
Optimizing TRIEs for ordered pattern matching is Π/sub 2//sup P/-complete
inferred← citeshttps://doi.org/10.1109/sct.1995.514863openalex-snapshot
On the structure of low sets [complexity classes]
inferred← citeshttps://doi.org/10.1112/s146115700000022xopenalex-snapshot
Restrictive Acceptance Suffices for Equivalence Problems
inferred← citeshttps://doi.org/10.1137/0220053openalex-snapshot
PP is as Hard as the Polynomial-Time Hierarchy
inferred← citeshttps://doi.org/10.1137/0221023openalex-snapshot
Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
showing the first 200 of 265 · page through all 265
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.