Limitations of sums of bounded read formulas and ABPs

DOI10.1007/978-3-030-79416-3_9OpenAlexW3175728444MaRDI QIDQ2117084

Purnata Ghosal, B. V. Raghavendra Rao

Publication date: 21 March 2022

Full work available at URL: https://arxiv.org/abs/2010.01385

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Uses Software

• GitHub
• lowerbounds-survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• The complexity of partial derivatives
• Completeness and reduction in algebraic complexity theory
• Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields.
• Sums of read-once formulas: how many summands are necessary?
• Tight bounds on maximal and maximum matchings
• Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits
• Balancing syntactically multilinear arithmetic circuits
• A quadratic lower bound for homogeneous algebraic branching programs
• Characterizing Valiant's algebraic complexity classes
• Characterizing Arithmetic Read-Once Formulae
• Deterministic Black-Box Identity Testing $pi$-Ordered Algebraic Branching Programs
• Arithmetic Circuits: A survey of recent results and open questions
• Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• Computing Algebraic Formulas Using a Constant Number of Registers
• The Parallel Evaluation of General Arithmetic Expressions
• Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits
• Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas
• 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
• Separating multilinear branching programs and formulas
• Probability and Computing
• Multi-linear formulas for permanent and determinant are of super-polynomial size
• Lower bounds for special cases of syntactic multilinear ABPs
• Lower bounds for special cases of syntactic multilinear ABPs
• Depth-3 arithmetic circuits over fields of characteristic zero

This page was built for publication: Limitations of sums of bounded read formulas and ABPs