Fast Parallel Computation of Polynomials Using Few Processors
From MaRDI portal
Publication:3036703
Cited in
(75)- Multi-k-ic depth three circuit lower bound
- Fast exact algorithms using Hadamard product of polynomials
- \(\mathrm P \overset {?} {=} \mathrm{NP}\)
- Resource trade-offs in syntactically multilinear arithmetic circuits
- scientific article; zbMATH DE number 7561742 (Why is no real title available?)
- A super-quadratic lower bound for depth four arithmetic circuits
- An introduction to parallel dynamic programming
- scientific article; zbMATH DE number 7561696 (Why is no real title available?)
- Lower bounds for tropical circuits and dynamic programs
- Feasible arithmetic computations: Valiant's hypothesis
- Short Proofs for the Determinant Identities
- A Selection of Lower Bounds for Arithmetic Circuits
- Lower bounds for sums of powers of low degree univariates
- Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
- On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree
- 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
- Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications.
- Subexponential size hitting sets for bounded depth multilinear formulas
- Parallel complexity of logical query programs
- A complexity theory of efficient parallel algorithms
- Linear matroid intersection is in quasi-NC
- The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
- Fast and efficient parallel solution of dense linear systems
- Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring
- 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
- Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
- 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
- scientific article; zbMATH DE number 7561311 (Why is no real title available?)
- 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
- Lower bounds on monotone arithmetic circuits with restricted depths
- Lower bounds on arithmetic circuits via partial derivatives
- A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a la maniere de Valiant
- Homomorphism polynomials complete for VP
- Polynomial decomposition algorithms
- Balancing bounded treewidth circuits
- A generalization of Spira's theorem and circuits with small segregators or separators
- Improved bounds for reduction to depth 4 and depth 3
- A generalization of Spira's theorem and circuits with small segregators or separators
- Lower bounds for the sum of small-size algebraic branching programs
- The computational power of depth five arithmetic circuits
- Boolean circuits versus arithmetic circuits
- Characterizing Valiant's algebraic complexity classes
- An exponential lower bound for homogeneous depth four arithmetic formulas
- 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
- Algebraic complexity classes
- Geometric complexity theory: an introduction for geometers
- Computing (and Life) Is All about Tradeoffs
- 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
- scientific article; zbMATH DE number 7009617 (Why is no real title available?)
- Irreducibility of multivariate polynomials
- Cyclotomic identity testing and applications
- Succinct algebraic branching programs characterizing non-uniform complexity classes
- Small-depth multilinear formula lower bounds for iterated matrix multiplication with applications
- Functional decomposition of polynomials: the tame case
- Schur polynomials do not have small formulas if the determinant does not
- Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
- Weighted sum-of-squares lower bounds for univariate polynomials imply \(\mathsf{VP} \neq \mathsf{VNP}\)
- 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
- Shadows of Newton polytopes
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)
