Dual VP classes

DOI10.1007/S00037-016-0146-7MaRDI QIDQ2410687zbMATH OpenOpenAlexFDO

Authors Eric Allender, Anna Gál, Ian Mertz

Publication date 18 October 2017

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-016-0146-7

zbMATH Keywords

arithmetic circuitscircuit complexitythreshold circuitssemiunbounded circuits

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Dual VP classes
• Characterizing Valiant’s Algebraic Complexity Classes
• Characterizing Valiant's algebraic complexity classes
• A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a la maniere de Valiant
• Circuits arithmétiques et calculs tensoriels

Cites work

• scientific article; zbMATH DE number 1375589 (Why is no real title available?)
• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• scientific article; zbMATH DE number 1161568 (Why is no real title available?)
• A Uniform Circuit Lower Bound for the Permanent
• A new characterization of \(\text{ACC}^{0}\) and probabilistic \(\text{CC}^{0}\)
• Amplifying lower bounds by means of self-reducibility
• Boolean complexity classes vs. their arithmetic analogs
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Characterizing Valiant's algebraic complexity classes
• Circuits and expressions with nonassociative gates
• Circuits constructed with MOD\(_ q\) gates cannot compute ``and in sublinear size
• Computing with a full memory: catalytic space
• Cook's versus Valiant's hypothesis
• Division in logspace-uniform NC
• Dual VP classes
• Explicit constructions of linear-sized superconcentrators
• Fast Parallel Computation of Polynomials Using Few Processors
• Interpolation in Valiant's theory
• Isolation, matching, and counting uniform and nonuniform upper bounds
• Making Nondeterminism Unambiguous
• Matrix Representation of Finite Fields
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• Nondeterministic NC^1 computation
• Nonuniform ACC circuit lower bounds
• On ACC
• On Threshold Circuits and Polynomial Computation
• On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
• On the least prime in an arithmetic progression and estimates for the zeros of Dirichlet L-functions
• PP is as Hard as the Polynomial-Time Hierarchy
• Properties that characterize LOGCFL
• Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems
• The complexity of iterated multiplication
• The support problem and its elliptic analogue
• Two Applications of Inductive Counting for Complementation Problems
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Visibly counter languages and the structure of \(\mathrm {NC}^{1}\)

Cited in

(2)

• On SBV dual
• Dual VP classes

This page was built for publication: Dual VP classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2410687)