Limitations of sums of bounded read formulas and ABPs
From MaRDI portal
Publication:2117084
DOI10.1007/978-3-030-79416-3_9OpenAlexW3175728444MaRDI QIDQ2117084FDOQ2117084
Authors: Purnata Ghosal, B. V. Raghavendra Rao 
Publication date: 21 March 2022
Full work available at URL: https://arxiv.org/abs/2010.01385
Cites Work
- The complexity of computing the permanent
- The complexity of partial derivatives
- Computing Algebraic Formulas Using a Constant Number of Registers
- Characterizing Valiant's algebraic complexity classes
- Probability and Computing
- Some Exact Complexity Results for Straight-Line Computations over Semirings
- Completeness and reduction in algebraic complexity theory
- Title not available (Why is that?)
- An almost cubic lower bound for depth three arithmetic circuits
- Separating multilinear branching programs and formulas
- Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields.
- Separation of multilinear circuit and formula size
- Arithmetic circuits: a survey of recent results and open questions
- Multi-linear formulas for permanent and determinant are of super-polynomial size
- Depth-3 arithmetic circuits over fields of characteristic zero
- Characterizing arithmetic read-once formulae
- The Parallel Evaluation of General Arithmetic Expressions
- Balancing syntactically multilinear arithmetic circuits
- Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
- Tight bounds on maximal and maximum matchings
- Complete derandomization of identity testing and reconstruction of read-once formulas
- Deterministic black-box identity testing \(\pi\)-ordered algebraic branching programs
- Sums of read-once formulas: how many summands are necessary?
- Separation between read-once oblivious algebraic branching programs (ROABPs) and multilinear depth three circuits
- Some lower bound results for set-multilinear arithmetic computations
- Lower bounds for special cases of syntactic multilinear ABPs
- A quadratic lower bound for homogeneous algebraic branching programs
- Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits
- A quadratic lower bound for algebraic branching programs
- Lower bounds for sum and sum of products of read-once formulas
- Separating monotone VP and VNP
- Lower bounds for special cases of syntactic multilinear ABPs
Cited In (1)
Uses Software
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)
