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
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
