Arithmetic circuits: a survey of recent results and open questions

DOI10.1561/0400000039zbMATH Open1205.68175OpenAlexW2026944800MaRDI QIDQ3069052FDOQ3069052

Authors: Amir Shpilka, Amir Yehudayoff 

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

Recommendations

• Recent progress on arithmetic circuit lower bounds
• Progress on polynomial identity testing
• Arithmetic circuits: a chasm at depth 3
• Non-commutative computations: lower bounds and polynomial identity testing
• Depth-3 arithmetic circuits over fields of characteristic zero

zbMATH Keywords

lower boundspolynomial identity testingarithmetic circuit complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

Cited In (only showing first 100 items - show all)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• \(\mathrm P \overset {?} {=} \mathrm{NP}\)
• Fast exact algorithms using Hadamard product of polynomials
• Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
• Lower bounds for matrix factorization
• Lower bounds for matrix factorization
• Short Proofs for the Determinant Identities
• A Selection of Lower Bounds for Arithmetic Circuits
• Lower bounds for tropical circuits and dynamic programs
• Characterizing arithmetic read-once formulae
• Most secant varieties of tangential varieties to Veronese varieties are nondefective
• Constructive non-commutative rank computation is in deterministic polynomial time
• Arithmetic and Algebraic Circuits
• Title not available (Why is that?)
• The partition rank of a tensor and \(k\)-right corners in \(\mathbb{F}_q^n\)
• A \(\tau \)-conjecture for Newton polygons
• Practical homomorphic message authenticators for arithmetic circuits
• Connections between graphs and matrix spaces
• Circuits in bounded arithmetic. I
• Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits
• Improved Explicit Hitting-Sets for ROABPs
• On measures of space over real and complex numbers
• A lower bound on determinantal complexity
• Operator scaling: theory and applications
• Some complete and intermediate polynomials in algebraic complexity theory
• A review note on arbitrary precision arithmetic
• Factors of low individual degree polynomials
• Lower bounds for depth-three arithmetic circuits with small bottom fanin
• Subexponential size hitting sets for bounded depth multilinear formulas
• Building above read-once polynomials: identity testing and hardness of representation
• Exact learning from an honest teacher that answers membership queries
• Title not available (Why is that?)
• On the complexity of noncommutative polynomial factorization
• Towards blackbox identity testing of log-variate circuits
• On some computations on sparse polynomials
• Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees
• Blackbox identity testing for sum of special ROABPs and its border class
• Jacobian hits circuits: hitting sets, lower bounds for depth-\(D\) occur-\(k\) formulas and depth-3 transcendence degree-\(k\) circuits
• \textsf{VNP} = \textsf{VP} in the multilinear world
• Non-commutative computations: lower bounds and polynomial identity testing
• Subspace arrangements, graph rigidity and derandomization through submodular optimization
• Progress on polynomial identity testing. II
• Barriers for rank methods in arithmetic complexity
• Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties)
• Deterministic polynomial identity tests for multilinear bounded-read formulae
• Algebraic independence in positive characteristic: a \(p\)-adic calculus
• Improved bounds for reduction to depth 4 and depth 3
• Linear-size constant-query IOPs for delegating computation
• Random arithmetic formulas can be reconstructed efficiently
• A generalized sylvester-gallai type theorem for quadratic polynomials
• Ulrich complexity
• An exponential lower bound for homogeneous depth four arithmetic formulas
• A case of depth-3 identity testing, sparse factorization and duality
• Read-once polynomial identity testing
• 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
• Algorithms Based on *-Algebras, and Their Applications to Isomorphism of Polynomials with One Secret, Group Isomorphism, and Polynomial Identity Testing
• Algebraic complexity classes
• Geometric complexity theory. V: Efficient algorithms for Noether normalization
• Subtraction-free complexity, cluster transformations, and spanning trees
• Title not available (Why is that?)
• Title not available (Why is that?)
• Equivalence of polynomial identity testing and polynomial factorization
• On proving parameterized size lower bounds for multilinear algebraic models
• Progress on polynomial identity testing
• Recent progress on arithmetic circuit lower bounds
• Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
• Polynomial interpolation and identity testing from high powers over finite fields
• Faster sparse multivariate polynomial interpolation of straight-line programs
• Sylvester-Gallai type theorems for quadratic polynomials
• Arithmetic circuits: a chasm at depth 3
• Title not available (Why is that?)
• On the complexity of computing a random Boolean function over the reals
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A super-quadratic lower bound for depth four arithmetic circuits
• Semialgebraic proofs, IPS lower bounds, and the \(\tau\)-conjecture: can a natural number be negative?
• A robust version of Hegedűs's lemma, with applications
• On the closures of monotone algebraic classes and variants of the determinant
• On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree
• Limitations of sums of bounded read formulas and ABPs
• Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
• Variants of the determinant polynomial and the \textsf{VP}-completeness
• Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits
• Types of depth and formula size
• Towards Optimal Depth Reductions for Syntactically Multilinear Circuits
• Title not available (Why is that?)
• Regular expression length via arithmetic formula complexity
• On the closures of monotone algebraic classes and variants of the determinant
• Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications.
• Arithmetic circuits, structured matrices and (not so) deep learning
• Lower bounds for the circuit size of partially homogeneous polynomials
• Algebraic independence and blackbox identity testing
• Partial strong structural controllability
• Hardness of graph-structured algebraic and symbolic problems
• Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring

This page was built for publication: Arithmetic circuits: a survey of recent results and open questions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3069052)