scientific article; zbMATH DE number 3799016

Cited in

(57)

The complexity of combinatorial problems with succinct input representation
Some observations on the connection between counting and recursion
On sets polynomially enumerable by iteration
Turing machines with few accepting computations and low sets for PP
Polynomial-time 1-Turing reductions from $\#$PH to $\#$P
On sparse hard sets for counting classes
Threshold circuits of small majority-depth
Gap-definable counting classes
Universally serializable computation
A second step towards complexity-theoretic analogs of Rice's Theorem
Model checking for fragments of the interval temporal logic HS at the low levels of the polynomial time hierarchy
Enumerative counting is hard
Tally NP sets and easy census functions.
Alternating and empty alternating auxiliary stack automata.
Structural control in weighted voting games
On the probabilistic closure of the loose unambiguous hierarchy
A complexity theory for feasible closure properties
A novel characterization of the complexity class $\Theta_k^{\mathrm{P}}$ based on counting and comparison
Quantum and classical complexity classes: Separations, collapses, and closure properties
A common algebraic description for probabilistic and quantum computations
A note on parallel queries and the symmetric-difference hierarchy.
A dichotomy for real weighted Holant problems
The complexity of computational problems about Nash equilibria in symmetric win-lose games
Barnette's conjecture through the lens of the Mod_k P complexity classes
Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
A note on separating the relativized polynomial time hierarchy by immune sets
On Toda’s Theorem in Structural Communication Complexity
Separating \oplus L from L, NL, co-NL, and AL = P for oblivious Turing machines of linear access
The consequences of eliminating NP solutions
Counting homomorphisms to trees modulo a prime
Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2
The operators min and max on the polynomial hierarchy
The complexity class θp2: Recent results and applications in AI and modal logic
On the power of parity polynomial time
The complexity landscape of outcome determination in judgment aggregation
Stathis Zachos at 70!
The strong exponential hierarchy collapses
The complexity of symmetric Boolean parity Holant problems (extended abstract)
Stability, vertex stability, and unfrozenness for special graph classes
Constructive separations and their consequences
On the power of counting the total number of computation paths of NPTMs
Weighted automata and logics meet computational complexity
On the acceptance power of regular languages
On quasilinear-time complexity theory
Modulo classes and logarithmic advice
A hierarchy of constant communication complexity
On the fine-grained complexity of parity problems
Probabilistic polynomials, AC$^ 0$ functions and the polynomial-time hierarchy
Gaps, ambiguity, and establishing complexity-class containments via iterative constant-setting
Lower bounds and the hardness of counting properties
Logical characterizations of weighted complexity classes
Descriptive complexity and weighted Turing machines
Kolmogorov characterizations of complexity classes
The complexity of Kemeny elections
Meta-kernelization with structural parameters
$P^{NP[O(\log n)]}$ and sparse turing-complete sets for NP
Polynomial size $\Omega$-branching programs and their computational power

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4743737)