On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models
From MaRDI portal
Publication:4988917
DOI10.3233/FI-2020-1980zbMath1497.68224OpenAlexW3117897418MaRDI QIDQ4988917
Purnata Ghosal, Rao B. V. Raghavendra
Publication date: 20 May 2021
Published in: Fundamenta Informaticae (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.3233/fi-2020-1980
Symbolic computation and algebraic computation (68W30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Networks and circuits as models of computation; circuit complexity (68Q06) Parameterized complexity, tractability and kernelization (68Q27)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On testing monomials in multivariate polynomials
- Faster algorithms for finding and counting subgraphs
- The complexity of computing the permanent
- The complexity of partial derivatives
- Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials
- Balancing syntactically multilinear arithmetic circuits
- On constant depth circuits parameterized by degree: identity testing and depth reduction
- Arithmetic Circuits: A Chasm at Depth 3
- Arithmetic Circuits: A survey of recent results and open questions
- The Limits of Depth Reduction for Arithmetic Formulas: It's All About the Top Fan-In
- Boundaries of VP and VNP
- Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits
- Parameterized Analogues of Probabilistic Computation
- Lower bounds for depth 4 formulas computing iterated matrix multiplication
- Counting Subgraphs via Homomorphisms
- Multi-linear formulas for permanent and determinant are of super-polynomial size
- Derandomizing polynomial identity tests means proving circuit lower bounds
This page was built for publication: On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models
