Lower bounds for set-multilinear branching programs
From MaRDI portal
Cites work
- A super-polynomial lower bound for regular arithmetic formulas
- An almost cubic lower bound for depth three arithmetic circuits
- An exponential lower bound for homogeneous depth four arithmetic formulas
- Arithmetic circuits: a survey of recent results and open questions
- Balancing syntactically multilinear arithmetic circuits
- Blackbox identity testing for sum of special ROABPs and its border class
- Cook's versus Valiant's hypothesis
- Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
- Deterministic polynomial identity testing in non-commutative models
- Hitting sets for multilinear read-once algebraic branching programs, in any order
- Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
- Identity testing and lower bounds for read-\(k\) oblivious algebraic branching programs
- Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs
- Improved Explicit Hitting-Sets for ROABPs
- Improved hitting set for orbit of ROABPs
- Improved low-depth set-multilinear circuit lower bounds
- Improved lower bound, and proof barrier, for constant depth algebraic circuits
- Limitations of sums of bounded read formulas and ABPs
- Lower bounds and separations for constant depth multilinear circuits
- Lower bounds for special cases of syntactic multilinear ABPs
- Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
- Lower bounds for the sum of small-size algebraic branching programs
- Lower bounds on arithmetic circuits via partial derivatives
- Near-optimal set-multilinear formula lower bounds
- On the partial derivative method applied to lopsided set-multilinear polynomials
- On the power of homogeneous depth 4 arithmetic circuits
- Pseudorandom Bits for Oblivious Branching Programs
- Quadratic lower bounds for algebraic branching programs and formulas
- Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs
- Separating multilinear branching programs and formulas
- Separation between read-once oblivious algebraic branching programs (ROABPs) and multilinear depth-three circuits
- Separation of multilinear circuit and formula size
- Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication
- Some lower bound results for set-multilinear arithmetic computations
- Superpolynomial lower bounds against low-depth algebraic circuits
- Tensor-rank and lower bounds for arithmetic formulas
This page was built for publication: Lower bounds for set-multilinear branching programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6866476)
