Uniform constant-depth threshold circuits for division and iterated multiplication.

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

Related Items

Unnamed Item, Parallel identity testing for skew circuits with big powers and applications, Fifty years of the spectrum problem: survey and new results, Decomposition of threshold functions into bounded fan-in threshold functions, Log-space algorithms for paths and matchings in \(k\)-trees, Corrigendum to: ``Uniform constant-depth threshold circuits for division and iterated multiplication, Interval graph representation with given interval and intersection lengths, Extensions of MSO and the monadic counting hierarchy, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, The orbit problem is in the GapL hierarchy, On the complexity of regular-grammars with integer attributes, Root finding with threshold circuits, Green's theorem and isolation in planar graphs, Conjugacy in Baumslag's group, generic case complexity, and division in power circuits, A transfer method from bounded existential Diophantine equations to Tarski algebra formulas, Knapsack in graph groups, Tree compression using string grammars, Evaluation of circuits over nilpotent and polycyclic groups, Understanding cutting planes for QBFs, Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing, Better complexity bounds for cost register automata, Skew circuits of small width, The conjugacy problem in free solvable groups and wreath products of abelian groups is in \(\mathsf{TC}^0\), Polynomial time relatively computable triangular arrays for almost sure convergence, Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\), The conjugacy problem in free solvable groups and wreath products of abelian groups is in \({\mathsf {TC}^0}\), Dual VP classes, Complexity of regular functions, A characterization of definability of second-order generalized quantifiers with applications to non-definability, Trace inclusion for one-counter nets revisited, Monomials, multilinearity and identity testing in simple read-restricted circuits, Uniform derandomization from pathetic lower bounds, Parallel Identity Testing for Skew Circuits with Big Powers and Applications, Bounded Treewidth and Space-Efficient Linear Algebra, A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups, Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth, Evaluating Matrix Circuits, Path Checking for MTL and TPTL over Data Words, The Orbit Problem Is in the GapL Hierarchy

Cites Work