scientific article; zbMATH DE number 3799016

Cited in

(52)

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

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)