Fast Parallel Computation of Polynomials Using Few Processors
From MaRDI portal
Publication:3036703
DOI10.1137/0212043zbMath0524.68028OpenAlexW2081256023MaRDI QIDQ3036703
No author found.
Publication date: 1983
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/9c88dcd783fd0364fc4972c77a6bfc31f7ff16fc
Related Items (72)
Irreducibility of multivariate polynomials ⋮ Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring ⋮ A Generalization of Spira’s Theorem and Circuits with Small Segregators or Separators ⋮ On the efficiency of effective Nullstellensätze ⋮ Fast exact algorithms using Hadamard product of polynomials ⋮ The arithmetic complexity of tensor contraction ⋮ Lower Bounds for Sums of Powers of Low Degree Univariates ⋮ Subexponential size hitting sets for bounded depth multilinear formulas ⋮ The Limits of Depth Reduction for Arithmetic Formulas: It's All About the Top Fan-In ⋮ Some complete and intermediate polynomials in algebraic complexity theory ⋮ Boolean circuits versus arithmetic circuits ⋮ Parallel complexity of logical query programs ⋮ A quasi-polynomial-time algorithm for sampling words from a context-free language ⋮ A generalization of Spira's theorem and circuits with small segregators or separators ⋮ On efficient parallel computations for some dynamic programming problems ⋮ Feasible arithmetic computations: Valiant's hypothesis ⋮ The iterated mod problem ⋮ Lower bounds on arithmetic circuits via partial derivatives ⋮ Resource trade-offs in syntactically multilinear arithmetic circuits ⋮ Dual VP classes ⋮ Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications. ⋮ Balancing bounded treewidth circuits ⋮ The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials ⋮ Unnamed Item ⋮ Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors ⋮ Complexity and Algorithms for Well-Structured k-SAT Instances ⋮ Shadows of Newton polytopes ⋮ Schur polynomials do not have small formulas if the determinant does not ⋮ Multi-\(k\)-ic depth three circuit lower bound ⋮ An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas ⋮ On the Power of Homogeneous Depth 4 Arithmetic Circuits ⋮ Arithmetic circuits: the chasm at depth four gets wider ⋮ A complexity theory of efficient parallel algorithms ⋮ Unnamed Item ⋮ Polynomial decomposition algorithms ⋮ The Computational Power of Depth Five Arithmetic Circuits ⋮ Cook's versus Valiant's hypothesis ⋮ Lower bounds for tropical circuits and dynamic programs ⋮ Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems ⋮ Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications ⋮ Characterizing Valiant's algebraic complexity classes ⋮ Lower Bounds for Syntactically Multilinear Algebraic Branching Programs ⋮ Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae ⋮ Unnamed Item ⋮ Two dynamic programming algorithms for which interpreted pebbling helps ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Linear matroid intersection is in quasi-NC ⋮ Improved bounds for reduction to depth 4 and depth 3 ⋮ On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree ⋮ Arithmetic Circuits: A Chasm at Depth 3 ⋮ Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits ⋮ Succinct Algebraic Branching Programs Characterizing Non-uniform Complexity Classes ⋮ Functional decomposition of polynomials: the tame case ⋮ Algebraic Complexity Classes ⋮ A Selection of Lower Bounds for Arithmetic Circuits ⋮ Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Geometric complexity theory V: Efficient algorithms for Noether normalization ⋮ $$P\mathop{ =}\limits^{?}NP$$ ⋮ Non-commutative arithmetic circuits: depth reduction and size lower bounds ⋮ Fast and efficient parallel solution of dense linear systems ⋮ Unnamed Item ⋮ Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees ⋮ Computing (and Life) Is All about Tradeoffs ⋮ A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a la maniere de Valiant ⋮ Short Proofs for the Determinant Identities ⋮ On computing the determinant in small parallel time using a small number of processors ⋮ Geometric complexity theory: an introduction for geometers ⋮ Size-depth trade-offs for monotone arithmetic circuits ⋮ Lower bounds on monotone arithmetic circuits with restricted depths ⋮ Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
This page was built for publication: Fast Parallel Computation of Polynomials Using Few Processors
