Publication:4036702
From MaRDI portal
zbMath0769.68050MaRDI QIDQ4036702
Publication date: 18 May 1993
Boolean model; arithmetic circuits; Boolean circuits; circuit size; low-level complexity; arithmetic model; Samuelson-Berkowitz method for computing the determinant
68Q25: Analysis of algorithms and problem complexity
Related Items
Relationships among $PL$, $\#L$, and the determinant, The orbit problem is in the GapL hierarchy, Faster combinatorial algorithms for determinant and Pfaffian, On the guessing number of shift graphs, Non-commutative arithmetic circuits: depth reduction and size lower bounds, The complexity of the characteristic and the minimal polynomial., On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits, On the reducibility of sets inside NP to sets with low information content, The combinatorial approach yields an NC algorithm for computing Pfaffians, Matrix rigidity, On the complexity of matrix rank and rigidity, Characterizing Valiant's algebraic complexity classes, The Orbit Problem Is in the GapL Hierarchy