Pages that link to "Item:Q3359758"

The following pages link to PP is as Hard as the Polynomial-Time Hierarchy (Q3359758):

Displaying 50 items.

• Dependence logic with a majority quantifier (Q302214) (← links)
• Is Valiant-Vazirani's isolation probability improvable? (Q354652) (← links)
• A dichotomy in the complexity of counting database repairs (Q389240) (← links)
• Pseudorandom generators, typically-correct derandomization, and circuit lower bounds (Q430845) (← links)
• Most probable explanations in Bayesian networks: complexity and tractability (Q433524) (← links)
• On a theorem of Razborov (Q445247) (← links)
• A complex analogue of Toda's theorem (Q454132) (← links)
• Lower bounds against weakly-uniform threshold circuits (Q486977) (← links)
• Meet your expectations with guarantees: beyond worst-case synthesis in quantitative games (Q528191) (← links)
• Leaf languages and string compression (Q550251) (← links)
• The size of SPP (Q596117) (← links)
• Average-case intractability vs. worst-case intractability (Q598182) (← links)
• Extensions of MSO and the monadic counting hierarchy (Q617710) (← links)
• Lower bounds for the determinantal complexity of explicit low degree polynomials (Q639850) (← links)
• On the acceptance power of regular languages (Q672323) (← links)
• On quasilinear-time complexity theory (Q672330) (← links)
• Modulo classes and logarithmic advice (Q672652) (← links)
• Counting induced subgraphs: an algebraic approach to \(\#\)W[1]-hardness (Q832520) (← links)
• The complexity of the \(K\)th largest subset problem and related problems (Q894449) (← links)
• The complexity of power indexes with graph restricted coalitions (Q898757) (← links)
• Universal relations and {\#}P-completeness (Q954984) (← links)
• The parameterized complexity of probability amplification (Q975525) (← links)
• Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions (Q987376) (← links)
• Structural properties of oracle classes (Q990941) (← links)
• The complexity of power-index comparison (Q1001906) (← links)
• A remark on collective quantification (Q1006495) (← links)
• From a zoo to a zoology: Towards a general theory of graph polynomials (Q1015377) (← links)
• Parameterized circuit complexity and the \(W\) hierarchy (Q1127315) (← links)
• A note on the permanent value problem (Q1198001) (← links)
• Graph isomorphism is low for PP (Q1210331) (← links)
• Non-commutative arithmetic circuits: depth reduction and size lower bounds (Q1274913) (← links)
• Relating polynomial time to constant depth (Q1274992) (← links)
• A lower bound for monotone arithmetic circuits computing \(0-1\) permanent (Q1276316) (← links)
• On bounded-probability operators and C\(_ =\)P (Q1313771) (← links)
• Gap-definable counting classes (Q1318473) (← links)
• PSPACE is provable by two provers in one round (Q1318475) (← links)
• A note on SpanP functions (Q1328756) (← links)
• On closure properties of GapP (Q1337146) (← links)
• Perceptrons, PP, and the polynomial hierarchy (Q1346615) (← links)
• On ACC (Q1346616) (← links)
• Recursion theoretic characterizations of complexity classes of counting functions (Q1365942) (← links)
• Universally serializable computation (Q1384538) (← links)
• The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes. (Q1401394) (← links)
• Some connections between bounded query classes and non-uniform complexity. (Q1426008) (← links)
• Time-space tradeoffs for satisfiability (Q1567402) (← links)
• Circuits over PP and PL (Q1567408) (← links)
• The counting complexity of group-definable languages (Q1575546) (← links)
• Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity (Q1604200) (← links)
• Randomness vs time: Derandomization under a uniform assumption (Q1604214) (← links)
• The fewest clues problem (Q1623268) (← links)