Fast Parallel Computation of Polynomials Using Few Processors
From MaRDI portal
Cited in
(87)- Lower bounds on monotone arithmetic circuits with restricted depths
- Irreducibility of multivariate polynomials
- Parallel complexity of logical query programs
- On efficient parallel computations for some dynamic programming problems
- Feasible arithmetic computations: Valiant's hypothesis
- The iterated mod problem
- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- A quasi-polynomial-time algorithm for sampling words from a context-free language
- Lower bounds on arithmetic circuits via partial derivatives
- Balancing bounded treewidth circuits
- Multi-k-ic depth three circuit lower bound
- Fast and efficient parallel solution of dense linear systems
- Cook's versus Valiant's hypothesis
- Linear matroid intersection is in quasi-NC
- Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
- Two dynamic programming algorithms for which interpreted pebbling helps
- Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees
- Geometric complexity theory: an introduction for geometers
- On the efficiency of effective Nullstellensätze
- Dual VP classes
- Characterizing Valiant's algebraic complexity classes
- Improved bounds for reduction to depth 4 and depth 3
- Boolean circuits versus arithmetic circuits
- Homomorphism polynomials complete for VP
- 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
- Algebraic complexity classes
- A Selection of Lower Bounds for Arithmetic Circuits
- Geometric complexity theory. V: Efficient algorithms for Noether normalization
- \(\mathrm P \overset {?} {=} \mathrm{NP}\)
- Computing (and Life) Is All about Tradeoffs
- A generalization of Spira's theorem and circuits with small segregators or separators
- The arithmetic complexity of tensor contraction
- The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
- An exponential lower bound for homogeneous depth four arithmetic formulas
- On the power of homogeneous depth 4 arithmetic circuits
- Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
- Subexponential size hitting sets for bounded depth multilinear formulas
- Succinct algebraic branching programs characterizing non-uniform complexity classes
- Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications.
- Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity
- A generalization of Spira's theorem and circuits with small segregators or separators
- Lower bounds for sums of powers of low degree univariates
- The limits of depth reduction for arithmetic formulas: it's all about the top fan-in
- Complexity and Algorithms for Well-Structured k-SAT Instances
- Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
- Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae
- Resource trade-offs in syntactically multilinear arithmetic circuits
- Arithmetic circuits: the chasm at depth four gets wider
- On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree
- scientific article; zbMATH DE number 7009617 (Why is no real title available?)
- The computational power of depth five arithmetic circuits
- Small-depth multilinear formula lower bounds for iterated matrix multiplication with applications
- Lower bounds for tropical circuits and dynamic programs
- On explicit branching programs for the rectangular determinant and permanent polynomials
- Quasipolynomial hitting sets for circuits with restricted parse trees
- Lower bounds for multilinear order-restricted ABPs
- scientific article; zbMATH DE number 7561742 (Why is no real title available?)
- A super-quadratic lower bound for depth four arithmetic circuits
- Short Proofs for the Determinant Identities
- A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a la maniere de Valiant
- Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring
- Polynomial decomposition algorithms
- Shadows of Newton polytopes
- Schur polynomials do not have small formulas if the determinant does not
- Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
- Weighted sum-of-squares lower bounds for univariate polynomials imply \(\mathsf{VP} \neq \mathsf{VNP}\)
- An introduction to parallel dynamic programming
- Lower bounds for the sum of small-size algebraic branching programs
- Cyclotomic identity testing and applications
- Branching programs with extended memory: new insights
- Homogeneous algebraic complexity theory and algebraic formulas
- Improved lower bound, and proof barrier, for constant depth algebraic circuits
- Lower bounds for the sum of small-size algebraic branching programs
- Hitting sets for orbits of circuit classes and polynomial families
- A simple inclusion-exclusion based algorithm for (k, n)-MLC and related problems
- A largish sum-of-squares implies circuit hardness and derandomization
- A subquadratic upper bound on Hurwitz's problem and related noncommutative polynomials
- Secret sharing, slice formulas, and monotone real circuits
- Monotone bounded-depth complexity of homomorphism polynomials
- On the existence of algebraic natural proofs
- Efficient polynomial identity testing over nonassociative algebras
- Functional decomposition of polynomials: the tame case
- On computing the determinant in small parallel time using a small number of processors
- Size-depth trade-offs for monotone arithmetic circuits
- Fast exact algorithms using Hadamard product of polynomials
- A complexity theory of efficient parallel algorithms
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)
