The power of the middle bit of a \(\#\)P function
From MaRDI portal
Publication:1894453
DOI10.1006/jcss.1995.1036zbMath0849.68036OpenAlexW1982847801MaRDI QIDQ1894453
Thomas Schwentick, Johannes Köbler, Frederic Green, Kenneth W. Regan, Jacobo Toran
Publication date: 4 November 1996
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/0697b0b67e8a03165d7fb002560003c25d23d52c
Related Items
The correlation between parity and quadratic polynomials mod \(3\) ⋮ On closure properties of GapP ⋮ On the complexity of computing the logarithm and square root functions on a complex domain ⋮ Uniform proofs of ACC representations ⋮ Average-case intractability vs. worst-case intractability ⋮ On the power of generalized Mod-classes ⋮ Unnamed Item ⋮ A structured view on weighted counting with relations to counting, quantum computation and applications ⋮ Relationships among $PL$, $\#L$, and the determinant ⋮ Lower bounds against weakly-uniform threshold circuits ⋮ On the Complexity of the Pancake Problem ⋮ On set intersection representations of graphs ⋮ Relating polynomial time to constant depth ⋮ Counting problems for parikh images ⋮ Implicit recursion-theoretic characterizations of counting classes ⋮ SELF-SPECIFYING MACHINES ⋮ On learning embedded midbit functions
