On the public citation graph

Descriptive Complexity of #P Functions

0 signed · 68 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.
Claim with ORCID
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.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1006/inco.1994.1100openalex-snapshot
Logical Definability of NP Optimization Problems
inferredcites →https://doi.org/10.1007/bfb0026095openalex-snapshot
On counting and approximation
inferredcites →https://doi.org/10.1016/0020-0190(90)90214-iopenalex-snapshot
A guided tour of chernoff bounds
inferredcites →https://doi.org/10.1016/0022-0000(90)90022-dopenalex-snapshot
On uniformity within NC1
inferredcites →https://doi.org/10.1016/0196-6774(89)90038-2openalex-snapshot
Monte-Carlo approximation algorithms for enumeration problems
inferredcites →https://doi.org/10.1016/0304-3975(76)90061-xopenalex-snapshot
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(86)90135-0openalex-snapshot
NP is as easy as detecting unique solutions
inferredcites →https://doi.org/10.1016/0890-5401(89)90063-1openalex-snapshot
Enumerative counting is hard
inferredcites →https://doi.org/10.1016/s0019-9958(86)80029-8openalex-snapshot
Relational queries computable in polynomial time
inferredcites →https://doi.org/10.1109/psct.1987.10319271openalex-snapshot
Expressibility as a Complexity Measure: Results and Directions
inferredcites →https://doi.org/10.1109/sct.1991.160280openalex-snapshot
Approximation properties of NP minimization classes
inferredcites →https://doi.org/10.1109/sct.1993.336543openalex-snapshot
Polynomial-time optimization, parallel approximation, and fixpoint logic
inferredcites →https://doi.org/10.1109/sfcs.1983.35openalex-snapshot
Monte-Carlo algorithms for enumeration and reliability problems
inferredcites →https://doi.org/10.1109/sfcs.1988.21957openalex-snapshot
Polytopes, permanents and graphs with large factors
inferredcites →https://doi.org/10.1109/sfcs.1989.63527openalex-snapshot
On the computational power of PP and (+)P
inferredcites →https://doi.org/10.1137/0214060openalex-snapshot
On Approximation Algorithms for # P
inferredcites →https://doi.org/10.1137/0216051openalex-snapshot
Languages that Capture Complexity Classes
inferredcites →https://doi.org/10.1145/102782.102783openalex-snapshot
A random polynomial-time algorithm for approximating the volume of convex bodies
inferredcites →https://doi.org/10.1145/62212.62233openalex-snapshot
Optimization, approximation, and complexity classes
inferredcites →https://doi.org/10.1145/800070.802186openalex-snapshot
The complexity of relational query languages (Extended Abstract)

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.1996.0069openalex-snapshot
Logical Definability of Counting Functions
inferred← citeshttps://doi.org/10.1007/11821069_64openalex-snapshot
The Complexity of Counting Functions with Easy Decision Version
inferred← citeshttps://doi.org/10.1007/3-540-44436-x_12openalex-snapshot
On the Relative Complexity of Approximate Counting Problems
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-44622-2_27openalex-snapshot
On the Complexity of Combinatorial and Metafinite Generating Functions of Graph Properties in the Computational Model of Blum, Shub and Smale
inferred← citeshttps://doi.org/10.1007/3-540-46521-9_8openalex-snapshot
Semantical Counting Circuits
inferred← citeshttps://doi.org/10.1007/3-540-60246-1_120openalex-snapshot
Comparing counting classes for logspace, one-way logspace, and first-order
inferred← citeshttps://doi.org/10.1007/978-3-030-59267-7_22openalex-snapshot
Characterizations and Approximability of Hard Counting Classes Below $$\#\mathsf {P}$$
inferred← citeshttps://doi.org/10.1007/978-3-319-57586-5_6openalex-snapshot
Completeness Results for Counting Problems with Easy Decision
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-642-02017-9_14openalex-snapshot
On the Connection between Interval Size Functions and Path Counting
inferred← citeshttps://doi.org/10.1007/978-3-662-52921-8_15openalex-snapshot
A Model-Theoretic Characterization of Constant-Depth Arithmetic Circuits
inferred← citeshttps://doi.org/10.1007/bfb0029983openalex-snapshot
Counting problems over the reals
inferred← citeshttps://doi.org/10.1007/s00037-016-0137-8openalex-snapshot
On the connection between interval size functions and path counting
inferred← citeshttps://doi.org/10.1007/s00224-003-1023-8openalex-snapshot
Semantical Counting Circuits
inferred← citeshttps://doi.org/10.1007/s00453-003-1073-yopenalex-snapshot
The Relative Complexity of Approximate Counting Problems
inferred← citeshttps://doi.org/10.1016/0304-3975(95)00237-5openalex-snapshot
Recursion theoretic characterizations of complexity classes of counting functions
inferred← citeshttps://doi.org/10.1016/j.apal.2019.04.006openalex-snapshot
A model-theoretic characterization of constant-depth arithmetic circuits
inferred← citeshttps://doi.org/10.1016/j.ic.2020.104627openalex-snapshot
A structured view on weighted counting with relations to counting, quantum computation and applications
inferred← citeshttps://doi.org/10.1016/j.ic.2024.105213openalex-snapshot
Weighted automata and logics meet computational complexity
inferred← citeshttps://doi.org/10.1016/j.ic.2026.105446openalex-snapshot
Descriptive complexity and weighted Turing machines
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.jcss.2020.04.002openalex-snapshot
Descriptive complexity of #P functions: A new perspective
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/s0166-218x(00)00221-3openalex-snapshot
On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
inferred← citeshttps://doi.org/10.1016/s0304-3975(98)00190-xopenalex-snapshot
Counting problems over the reals
inferred← citeshttps://doi.org/10.1109/ccc.1996.507664openalex-snapshot
Nondeterministic NC/sup 1/ computation
inferred← citeshttps://doi.org/10.1109/lics.2017.8005150openalex-snapshot
Descriptive Complexity for counting complexity classes
inferred← citeshttps://doi.org/10.1109/sct.1994.315798openalex-snapshot
Logical definability of counting functions
inferred← citeshttps://doi.org/10.1137/s0097539793304601openalex-snapshot
The Complexity of Planar Counting Problems
inferred← citeshttps://doi.org/10.1145/3037381openalex-snapshot
A Complexity Trichotomy for Approximately Counting List H -Colorings
inferred← citeshttps://doi.org/10.1145/3209108.3209179openalex-snapshot
Model-Theoretic Characterization of Boolean and Arithmetic Circuit Classes of Small Depth
inferred← citeshttps://doi.org/10.1145/3294052.3319704openalex-snapshot
Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation
inferred← citeshttps://doi.org/10.1145/3375395.3389130openalex-snapshot
Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration
inferred← citeshttps://doi.org/10.1145/3422648.3422661openalex-snapshot
Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation
inferred← citeshttps://doi.org/10.1145/3477045openalex-snapshot
#NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes
inferred← citeshttps://doi.org/10.1145/3561064.3561072openalex-snapshot
Guest column: A panorama of counting problems the decision version of which is in P
inferred← citeshttps://doi.org/10.1145/3771721openalex-snapshot
Counting of Teams in First-Order Team Logics
inferred← citeshttps://doi.org/10.23638/lmcs-16(1:9)2020openalex-snapshot
Descriptive Complexity for Counting Complexity Classes
inferred← citeshttps://doi.org/10.24963/ijcai.2018/727openalex-snapshot
The Finite Model Theory of Bayesian Networks: Descriptive Complexity
inferred← citeshttps://doi.org/10.4230/lipics.csl.2011.189openalex-snapshot
Enumeration Complexity of Logical Query Problems with Second-order Variables
inferred← citeshttps://doi.org/10.4230/lipics.csl.2013.149openalex-snapshot
Descriptive complexity of approximate counting CSPs
inferred← citeshttps://doi.org/10.4230/lipics.fsttcs.2009.2329openalex-snapshot
Functionally Private Approximations of Negligibly-Biased Estimators
inferred← citeshttps://doi.org/10.4230/lipics.mfcs.2019.19openalex-snapshot
Counting of Teams in First-Order Team Logics
inferred← citeshttps://doi.org/10.48550/arxiv.1611.01706openalex-snapshot
Self-reducible with easy decision version counting problems admit additive error approximation. Connections to counting complexity, exponential time complexity, and circuit lower bounds
inferred← citeshttps://doi.org/10.48550/arxiv.1801.01901openalex-snapshot
On randomized counting versus randomised decision
inferred← citeshttps://doi.org/10.48550/arxiv.2003.02524openalex-snapshot
Characterizations and approximability of hard counting classes below #P
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.