Succinct Algebraic Branching Programs Characterizing Non-uniform Complexity Classes
From MaRDI portal
Publication:3088284
DOI10.1007/978-3-642-22953-4_18zbMath1342.68137OpenAlexW2145140337MaRDI QIDQ3088284
Publication date: 19 August 2011
Published in: Fundamentals of Computation Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22953-4_18
Data structures (68P05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Processing succinct matrices and vectors ⋮ Interactive proofs and a Shamir-like result for real number computations
Cites Work
- VPSPACE and a transfer theorem over the reals
- Arithmetization: A new method in structural complexity theory
- Feasible arithmetic computations: Valiant's hypothesis
- On uniform circuit complexity
- Succinct representation, leaf languages, and projection reductions
- Completeness and reduction in algebraic complexity theory
- Functions computable in polynomial space
- Characterizing Valiant's algebraic complexity classes
- Fast Parallel Computation of Polynomials Using Few Processors
- Small-Space Analogues of Valiant’s Classes
- Succinct representations of graphs
- Counting Classes and the Fine Structure between NC 1 and L
- PSPACE SURVIVES CONSTANT-WIDTH BOTTLENECKS
- Computing Algebraic Formulas Using a Constant Number of Registers
- Circuit Definitions of Nondeterministic Complexity Classes
- On Relating Time and Space to Size and Depth
- Computational Complexity
- A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a la maniere de Valiant
