Arithmetic Circuits: A survey of recent results and open questions
From MaRDI portal
Publication:3069052
DOI10.1561/0400000039zbMath1205.68175OpenAlexW2026944800MaRDI 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
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)
Related Items (only showing first 100 items - show all)
Fast exact algorithms using Hadamard product of polynomials ⋮ Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank 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 ⋮ Partial strong structural controllability ⋮ The Limits of Depth Reduction for Arithmetic Formulas: It's All About the Top Fan-In ⋮ Constructive Non-Commutative Rank Computation Is in Deterministic Polynomial Time. ⋮ Some complete and intermediate polynomials in algebraic complexity theory ⋮ Faster sparse multivariate polynomial interpolation of straight-line programs ⋮ Exact learning from an honest teacher that answers membership queries ⋮ Types of depth and formula size ⋮ Quadratic lower bounds for algebraic branching programs and formulas ⋮ Lower bounds for the circuit size of partially homogeneous polynomials ⋮ Unnamed Item ⋮ The partition rank of a tensor and \(k\)-right corners in \(\mathbb{F}_q^n\) ⋮ Linear-size constant-query IOPs for delegating computation ⋮ Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications. ⋮ Ulrich complexity ⋮ Emptiness problems for integer circuits ⋮ Learning algebraic decompositions using Prony structures ⋮ Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication ⋮ Most secant varieties of tangential varieties to Veronese varieties are nondefective ⋮ 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 ⋮ \textsf{VNP} = \textsf{VP} in the multilinear world ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Deterministic polynomial identity tests for multilinear bounded-read formulae ⋮ On \(\epsilon\)-sensitive monotone computations ⋮ A case of depth-3 identity testing, sparse factorization and duality ⋮ An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas ⋮ Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits ⋮ Polynomial interpolation and identity testing from high powers over finite fields ⋮ Sylvester-Gallai type theorems for quadratic polynomials ⋮ Unnamed Item ⋮ Barriers for Rank Methods in Arithmetic Complexity ⋮ Subspace Arrangements, Graph Rigidity and Derandomization Through Submodular Optimization ⋮ Algorithms Based on *-Algebras, and Their Applications to Isomorphism of Polynomials with One Secret, Group Isomorphism, and Polynomial Identity Testing ⋮ Random arithmetic formulas can be reconstructed efficiently ⋮ A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas ⋮ Lower bounds for tropical circuits and dynamic programs ⋮ Read-once polynomial identity testing ⋮ Algebraic Independence and Blackbox Identity Testing ⋮ Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications ⋮ Practical homomorphic message authenticators for arithmetic circuits ⋮ On measures of space over real and complex numbers ⋮ A note on parameterized polynomial identity testing using hitting set generators ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the complexity of noncommutative polynomial factorization ⋮ Average-case linear matrix factorization and reconstruction of low width algebraic branching programs ⋮ Building above read-once polynomials: identity testing and hardness of representation ⋮ Improved bounds for reduction to depth 4 and depth 3 ⋮ Lower bounds for matrix factorization ⋮ Blackbox identity testing for sum of special ROABPs and its border class ⋮ Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree ⋮ Arithmetic Circuits: A Chasm at Depth 3 ⋮ Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties) ⋮ 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 ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On hard instances of non-commutative permanent ⋮ Algebraic Complexity Classes ⋮ A Selection of Lower Bounds for Arithmetic Circuits ⋮ Operator scaling: theory and applications ⋮ Towards Optimal Depth Reductions for Syntactically Multilinear Circuits ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Geometric complexity theory V: Efficient algorithms for Noether normalization ⋮ $$P\mathop{ =}\limits^{?}NP$$ ⋮ A generalized sylvester-gallai type theorem for quadratic polynomials ⋮ Characterizing Arithmetic Read-Once Formulae ⋮ Tropical Complexity, Sidon Sets, and Dynamic Programming ⋮ On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A quadratic lower bound for homogeneous algebraic branching programs ⋮ Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees ⋮ Emptiness Problems for Integer Circuits ⋮ Lower bounds for matrix factorization ⋮ A lower bound on determinantal complexity ⋮ Improved hitting set for orbit of ROABPs ⋮ Almost all subgeneric third-order Chow decompositions are identifiable ⋮ Short Proofs for the Determinant Identities ⋮ Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits ⋮ A \(\tau \)-conjecture for Newton polygons ⋮ Equivalence of polynomial identity testing and polynomial factorization ⋮ 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
This page was built for publication: Arithmetic Circuits: A survey of recent results and open questions
