Arithmetic Circuits: A survey of recent results and open questions
From MaRDI portal
Publication:3069052
DOI10.1561/0400000039zbMath1205.68175MaRDI QIDQ3069052
Publication date: 24 January 2011
Published in: Foundations and Trends® in Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1561/0400000039
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68N30: Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)
Related Items
Unnamed Item, Most secant varieties of tangential varieties to Veronese varieties are nondefective, Algorithms Based on *-Algebras, and Their Applications to Isomorphism of Polynomials with One Secret, Group Isomorphism, and Polynomial Identity Testing, Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications, On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree, Constructive Non-Commutative Rank Computation Is in Deterministic Polynomial Time., Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models, Unnamed Item, Lower bounds for matrix factorization, Unnamed Item, Sylvester-Gallai type theorems for quadratic polynomials, Barriers for Rank Methods in Arithmetic Complexity, A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas, Towards Optimal Depth Reductions for Syntactically Multilinear Circuits, A super-quadratic lower bound for depth four arithmetic circuits, A generalized sylvester-gallai type theorem for quadratic polynomials, Emptiness Problems for Integer Circuits, Short Proofs for the Determinant Identities, Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits, Lower bounds for depth-three arithmetic circuits with small bottom fanin, Subexponential size hitting sets for bounded depth multilinear formulas, Factors of low individual degree polynomials, Random arithmetic formulas can be reconstructed efficiently, Lower bounds for tropical circuits and dynamic programs, Read-once polynomial identity testing, Building above read-once polynomials: identity testing and hardness of representation, Fast exact algorithms using Hadamard product of polynomials, \textsf{VNP} = \textsf{VP} in the multilinear world, Deterministic polynomial identity tests for multilinear bounded-read formulae, Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits, Some complete and intermediate polynomials in algebraic complexity theory, Ulrich complexity, Sums of read-once formulas: how many summands are necessary?, Deterministic identity testing for sum of read-once oblivious arithmetic branching programs, Sparse multivariate polynomial interpolation on the basis of Schubert polynomials, Polynomial interpolation and identity testing from high powers over finite fields, Practical homomorphic message authenticators for arithmetic circuits, On the complexity of noncommutative polynomial factorization, A case of depth-3 identity testing, sparse factorization and duality, On measures of space over real and complex numbers, Lower bounds for matrix factorization, Blackbox identity testing for sum of special ROABPs and its border class, Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties), A lower bound on determinantal complexity, Improved hitting set for orbit of ROABPs, Almost all subgeneric third-order Chow decompositions are identifiable, Variants of the determinant polynomial and the \textsf{VP}-completeness, Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization, Limitations of sums of bounded read formulas and ABPs, Partial strong structural controllability, Quadratic lower bounds for algebraic branching programs and formulas, The partition rank of a tensor and \(k\)-right corners in \(\mathbb{F}_q^n\), Linear-size constant-query IOPs for delegating computation, Emptiness problems for integer circuits, Learning algebraic decompositions using Prony structures, On \(\epsilon\)-sensitive monotone computations, Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits, A note on parameterized polynomial identity testing using hitting set generators, Average-case linear matrix factorization and reconstruction of low width algebraic branching programs, Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree, On hard instances of non-commutative permanent, Operator scaling: theory and applications, A quadratic lower bound for homogeneous algebraic branching programs, Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees, A \(\tau \)-conjecture for Newton polygons, Equivalence of polynomial identity testing and polynomial factorization, Lower bounds for the circuit size of partially homogeneous polynomials, Improved bounds for reduction to depth 4 and depth 3, Faster sparse multivariate polynomial interpolation of straight-line programs, Exact learning from an honest teacher that answers membership queries, Arithmetic Circuits: A Chasm at Depth 3, Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits, On Hard Instances of Non-Commutative Permanent, Algebraic Complexity Classes, A Selection of Lower Bounds for Arithmetic Circuits, Geometric complexity theory V: Efficient algorithms for Noether normalization, $$P\mathop{ =}\limits^{?}NP$$, Characterizing Arithmetic Read-Once Formulae, Tropical Complexity, Sidon Sets, and Dynamic Programming, Types of depth and formula size, Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication, An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas, Algebraic Independence and Blackbox Identity Testing, Subspace Arrangements, Graph Rigidity and Derandomization Through Submodular Optimization, The Limits of Depth Reduction for Arithmetic Formulas: It's All About the Top Fan-In, Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications., Algebraic independence in positive characteristic: A $p$-adic calculus, Depth-4 Identity Testing and Noether’s Normalization Lemma, Subtraction-free complexity, cluster transformations, and spanning trees, Regular expression length via arithmetic formula complexity, Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring, Unnamed Item, Connections between graphs and matrix spaces, Shadows of Newton polytopes, ReLU neural networks of polynomial size for exact maximum flow computation, Schur polynomials do not have small formulas if the determinant does not, On the closures of monotone algebraic classes and variants of the determinant, Improved Explicit Hitting-Sets for ROABPs
