Fast Parallel Computation of Polynomials Using Few Processors
From MaRDI portal
Publication:3036703
DOI10.1137/0212043zbMATH Open0524.68028OpenAlexW2081256023MaRDI QIDQ3036703FDOQ3036703
Authors:
Publication date: 1983
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/9c88dcd783fd0364fc4972c77a6bfc31f7ff16fc
Cited In (75)
- An introduction to parallel dynamic programming
- A super-quadratic lower bound for depth four arithmetic circuits
- Title not available (Why is that?)
- Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications.
- The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
- Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring
- Lower bounds for the sum of small-size algebraic branching programs
- The computational power of depth five arithmetic circuits
- On explicit branching programs for the rectangular determinant and permanent polynomials
- The limits of depth reduction for arithmetic formulas: it's all about the top fan-in
- Computing (and Life) Is All about Tradeoffs
- Cyclotomic identity testing and applications
- Schur polynomials do not have small formulas if the determinant does not
- Weighted sum-of-squares lower bounds for univariate polynomials imply \(\mathsf{VP} \neq \mathsf{VNP}\)
- Shadows of Newton polytopes
- Multi-\(k\)-ic depth three circuit lower bound
- \(\mathrm P \overset {?} {=} \mathrm{NP}\)
- Title not available (Why is that?)
- Fast exact algorithms using Hadamard product of polynomials
- Resource trade-offs in syntactically multilinear arithmetic circuits
- Short Proofs for the Determinant Identities
- A Selection of Lower Bounds for Arithmetic Circuits
- Feasible arithmetic computations: Valiant's hypothesis
- Lower bounds for tropical circuits and dynamic programs
- Lower bounds for sums of powers of low degree univariates
- On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree
- Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
- On the power of homogeneous depth 4 arithmetic circuits
- The arithmetic complexity of tensor contraction
- On computing the determinant in small parallel time using a small number of processors
- The iterated mod problem
- Arithmetic circuits: the chasm at depth four gets wider
- Subexponential size hitting sets for bounded depth multilinear formulas
- Parallel complexity of logical query programs
- Linear matroid intersection is in quasi-NC
- A complexity theory of efficient parallel algorithms
- Fast and efficient parallel solution of dense linear systems
- On efficient parallel computations for some dynamic programming problems
- Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity
- Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees
- On the efficiency of effective Nullstellensätze
- Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae
- Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
- Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
- Title not available (Why is that?)
- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- Size-depth trade-offs for monotone arithmetic circuits
- Jacobian hits circuits: hitting sets, lower bounds for depth-\(D\) occur-\(k\) formulas and depth-3 transcendence degree-\(k\) circuits
- A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a la maniere de Valiant
- Polynomial decomposition algorithms
- Lower bounds on arithmetic circuits via partial derivatives
- Lower bounds on monotone arithmetic circuits with restricted depths
- Homomorphism polynomials complete for VP
- Balancing bounded treewidth circuits
- A generalization of Spira's theorem and circuits with small segregators or separators
- A generalization of Spira's theorem and circuits with small segregators or separators
- Improved bounds for reduction to depth 4 and depth 3
- Boolean circuits versus arithmetic circuits
- Characterizing Valiant's algebraic complexity classes
- An exponential lower bound for homogeneous depth four arithmetic formulas
- Algebraic complexity classes
- Geometric complexity theory: an introduction for geometers
- Dual VP classes
- Geometric complexity theory. V: Efficient algorithms for Noether normalization
- Two dynamic programming algorithms for which interpreted pebbling helps
- Complexity and Algorithms for Well-Structured k-SAT Instances
- Title not available (Why is that?)
- Irreducibility of multivariate polynomials
- Small-depth multilinear formula lower bounds for iterated matrix multiplication with applications
- Succinct algebraic branching programs characterizing non-uniform complexity classes
- Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
- Functional decomposition of polynomials: the tame case
- Arithmetic circuits: a chasm at depth 3
- Cook's versus Valiant's hypothesis
- A quasi-polynomial-time algorithm for sampling words from a context-free language
This page was built for publication: Fast Parallel Computation of Polynomials Using Few Processors
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3036703)
