Arithmetic circuits: a survey of recent results and open questions
From MaRDI portal
Publication:3069052
Recommendations
Cited in
(only showing first 100 items - show all)- Emptiness problems for integer circuits
- Geometric complexity theory. V: Efficient algorithms for Noether normalization
- scientific article; zbMATH DE number 7009617 (Why is no real title available?)
- Subtraction-free complexity, cluster transformations, and spanning trees
- Succinct functional commitment for a large class of arithmetic circuits
- scientific article; zbMATH DE number 7471587 (Why is no real title available?)
- On hard instances of non-commutative permanent
- Equivalence of polynomial identity testing and polynomial factorization
- Complexity in ideals of polynomials: questions on algebraic complexity of circuits and proofs
- On proving parameterized size lower bounds for multilinear algebraic models
- Small-depth multilinear formula lower bounds for iterated matrix multiplication with applications
- On \(\epsilon\)-sensitive monotone computations
- Lower bounds for depth-4 formulas computing iterated matrix multiplication
- Progress on polynomial identity testing
- A quadratic size-hierarchy theorem for small-depth multilinear formulas
- Schur polynomials do not have small formulas if the determinant does not
- Recent progress on arithmetic circuit lower bounds
- Improved hitting set for orbit of ROABPs
- Almost all subgeneric third-order Chow decompositions are identifiable
- Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
- Weighted sum-of-squares lower bounds for univariate polynomials imply \(\mathsf{VP} \neq \mathsf{VNP}\)
- Polynomial interpolation and identity testing from high powers over finite fields
- Faster sparse multivariate polynomial interpolation of straight-line programs
- Quadratic lower bounds for algebraic branching programs and formulas
- Arithmetic circuits: a chasm at depth 3
- Tropical complexity, Sidon sets, and dynamic programming
- Depth-4 identity testing and Noether's normalization lemma
- scientific article; zbMATH DE number 7561765 (Why is no real title available?)
- A quadratic lower bound for homogeneous algebraic branching programs
- Shadows of Newton polytopes
- scientific article; zbMATH DE number 1148334 (Why is no real title available?)
- On the complexity of computing a random Boolean function over the reals
- scientific article; zbMATH DE number 7250153 (Why is no real title available?)
- scientific article; zbMATH DE number 7204375 (Why is no real title available?)
- scientific article; zbMATH DE number 7250152 (Why is no real title available?)
- scientific article; zbMATH DE number 7559443 (Why is no real title available?)
- Fast exact algorithms using Hadamard product of polynomials
- \(\mathrm P \overset {?} {=} \mathrm{NP}\)
- scientific article; zbMATH DE number 7250150 (Why is no real title available?)
- scientific article; zbMATH DE number 7561742 (Why is no real title available?)
- Lower bounds for matrix factorization
- A super-quadratic lower bound for depth four arithmetic circuits
- Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
- Lower bounds for matrix factorization
- Lower bounds for tropical circuits and dynamic programs
- 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
- Short Proofs for the Determinant Identities
- A Selection of Lower Bounds for Arithmetic Circuits
- Characterizing arithmetic read-once formulae
- Most secant varieties of tangential varieties to Veronese varieties are nondefective
- 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
- On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree
- On the closures of monotone algebraic classes and variants of the determinant
- Constructive non-commutative rank computation is in deterministic polynomial time
- Arithmetic and Algebraic Circuits
- Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits
- The partition rank of a tensor and \(k\)-right corners in \(\mathbb{F}_q^n\)
- Practical homomorphic message authenticators for arithmetic circuits
- A \(\tau \)-conjecture for Newton polygons
- Circuits in bounded arithmetic. I
- scientific article; zbMATH DE number 7204372 (Why is no real title available?)
- Types of depth and formula size
- Connections between graphs and matrix spaces
- Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits
- Towards Optimal Depth Reductions for Syntactically Multilinear Circuits
- scientific article; zbMATH DE number 7250151 (Why is no real title available?)
- On measures of space over real and complex numbers
- Algorithms based on \(*\)-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing
- A lower bound on determinantal complexity
- Regular expression length via arithmetic formula complexity
- Improved Explicit Hitting-Sets for ROABPs
- Operator scaling: theory and applications
- On the closures of monotone algebraic classes and variants of the determinant
- Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications.
- Lower bounds for the circuit size of partially homogeneous polynomials
- Arithmetic circuits, structured matrices and (not so) deep learning
- Algebraic independence and blackbox identity testing
- 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
- A review note on arbitrary precision arithmetic
- Partial strong structural controllability
- Hardness of graph-structured algebraic and symbolic problems
- Exact learning from an honest teacher that answers membership queries
- Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring
- On hard instances of non-commutative permanent
- How to recover a secret with \(O(n)\) additions
- scientific article; zbMATH DE number 7758310 (Why is no real title available?)
- Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees
- Towards blackbox identity testing of log-variate circuits
- On some computations on sparse polynomials
- Blackbox identity testing for sum of special ROABPs and its border class
- \textsf{VNP} = \textsf{VP} in the multilinear world
- Jacobian hits circuits: hitting sets, lower bounds for depth-\(D\) occur-\(k\) formulas and depth-3 transcendence degree-\(k\) circuits
- A note on parameterized polynomial identity testing using hitting set generators
- Interactions of computational complexity theory and mathematics
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)
