Limitations of sums of bounded read formulas and ABPs
From MaRDI portal
Publication:2117084
Cites work
- scientific article; zbMATH DE number 1775446 (Why is no real title available?)
- A quadratic lower bound for algebraic branching programs
- A quadratic lower bound for homogeneous algebraic branching programs
- An almost cubic lower bound for depth three arithmetic circuits
- Arithmetic circuits: a survey of recent results and open questions
- Balancing syntactically multilinear arithmetic circuits
- Characterizing Valiant's algebraic complexity classes
- Characterizing arithmetic read-once formulae
- Complete derandomization of identity testing and reconstruction of read-once formulas
- Completeness and reduction in algebraic complexity theory
- Computing Algebraic Formulas Using a Constant Number of Registers
- Depth-3 arithmetic circuits over fields of characteristic zero
- Deterministic black-box identity testing \(\pi\)-ordered algebraic branching programs
- Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields.
- Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
- Lower bounds for special cases of syntactic multilinear ABPs
- Lower bounds for special cases of syntactic multilinear ABPs
- Lower bounds for sum and sum of products of read-once formulas
- Multi-linear formulas for permanent and determinant are of super-polynomial size
- Probability and Computing
- Separating monotone VP and VNP
- 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
- Some Exact Complexity Results for Straight-Line Computations over Semirings
- Some lower bound results for set-multilinear arithmetic computations
- Sums of read-once formulas: how many summands are necessary?
- The Parallel Evaluation of General Arithmetic Expressions
- The complexity of computing the permanent
- The complexity of partial derivatives
- Tight bounds on maximal and maximum matchings
- Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits
This page was built for publication: Limitations of sums of bounded read formulas and ABPs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117084)
