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

Related Items

Path Checking for MTL and TPTL over Data Words ⋮ Trace inclusion for one-counter nets revisited ⋮ Monomials, multilinearity and identity testing in simple read-restricted circuits ⋮ Iterated multiplication in \(VTC^0\) ⋮ Evaluating Matrix Circuits ⋮ The conjugacy problem in free solvable groups and wreath products of abelian groups is in \({\mathsf {TC}^0}\) ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ Parallel complexity for nilpotent groups ⋮ Skew circuits of small width ⋮ Uniform derandomization from pathetic lower bounds ⋮ Dual VP classes ⋮ 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 ⋮ Parallel Identity Testing for Skew Circuits with Big Powers and Applications ⋮ Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space ⋮ Bounded Treewidth and Space-Efficient Linear Algebra ⋮ Expander construction in \(\mathrm{VNC}^1\) ⋮ Extensions of MSO and the monadic counting hierarchy ⋮ A transfer method from bounded existential Diophantine equations to Tarski algebra formulas ⋮ On the coincidence of complexity classes BPC and \(\text{TC}^0 \) ⋮ On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1 ⋮ SNARGs and PPAD hardness from the decisional Diffie-Hellman assumption ⋮ The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ Complexity of regular functions ⋮ The orbit problem is in the GapL hierarchy ⋮ Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing ⋮ Knapsack and the power word problem in solvable Baumslag–Solitar groups ⋮ A Tutorial on Query Answering and Reasoning over Probabilistic Knowledge Bases ⋮ The Orbit Problem Is in the GapL Hierarchy ⋮ New substitution bases for complexity classes ⋮ Unnamed Item ⋮ Communication and information complexity ⋮ On the complexity of regular-grammars with integer attributes ⋮ Knapsack in graph groups ⋮ Elementary analytic functions in \(\mathsf{VT}\mathsf{C}^0\) ⋮ A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups ⋮ A characterization of definability of second-order generalized quantifiers with applications to non-definability ⋮ Mathematical logic: proof theory, constructive mathematics. Abstracts from the workshop held November 8--14, 2020 (hybrid meeting) ⋮ Interval graph representation with given interval and intersection lengths ⋮ Fifty years of the spectrum problem: survey and new results ⋮ Tree compression using string grammars ⋮ Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth ⋮ Space Hardness of Solving Structured Linear Systems. ⋮ Evaluation of circuits over nilpotent and polycyclic groups ⋮ Root finding with threshold circuits ⋮ Better complexity bounds for cost register automata ⋮ Unnamed Item ⋮ TC^0 circuits for algorithmic problems in nilpotent groups ⋮ Green's theorem and isolation in planar graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Understanding cutting planes for QBFs ⋮ Parallel identity testing for skew circuits with big powers and applications ⋮ Conjugacy in Baumslag's group, generic case complexity, and division in power circuits ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ On the Complexity of Value Iteration ⋮ The conjugacy problem in free solvable groups and wreath products of abelian groups is in \(\mathsf{TC}^0\) ⋮ Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity ⋮ Polynomial time relatively computable triangular arrays for almost sure convergence ⋮ Quantum Hardness of Learning Shallow Classical Circuits ⋮ Unnamed Item ⋮ Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\) ⋮ Better complexity bounds for cost register automata ⋮ Dynamic complexity of expansion ⋮ A \#SAT algorithm for small constant-depth circuits with PTF gates

Cites Work