Pages that link to "Item:Q685721"

The following pages link to Arithmetization: A new method in structural complexity theory (Q685721):

Displaying 17 items.

• The complexity of weighted counting for acyclic conjunctive queries (Q395018) (← links)
• Shorter arithmetization of nondeterministic computations (Q496013) (← links)
• Interactive proof systems and alternating time-space complexity (Q685437) (← links)
• Non-deterministic exponential time has two-prover interactive protocols (Q685724) (← links)
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs (Q1321029) (← links)
• Probabilistically checkable proofs and their consequences for approximation algorithms (Q1344618) (← links)
• Recursion theoretic characterizations of complexity classes of counting functions (Q1365942) (← links)
• Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity (Q1604200) (← links)
• Competing provers yield improved Karp-Lipton collapse results (Q1775885) (← links)
• Randomized proofs in arithmetic (Q1807460) (← links)
• Cook's versus Valiant's hypothesis (Q1978701) (← links)
• A structured view on weighted counting with relations to counting, quantum computation and applications (Q2216125) (← links)
• EPiC: efficient privacy-preserving counting for MapReduce (Q2218469) (← links)
• Characterizing Valiant's algebraic complexity classes (Q2479314) (← links)
• A note on the circuit complexity of PP (Q2576885) (← links)
• Succinct Algebraic Branching Programs Characterizing Non-uniform Complexity Classes (Q3088284) (← links)
• A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a la maniere de Valiant (Q5502811) (← links)