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)- Progress on polynomial identity testing. II
- Equivalence of polynomial identity testing and polynomial factorization
- Short Proofs for the Determinant Identities
- Read-once polynomial identity testing
- Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
- Blackbox identity testing for sum of special ROABPs and its border class
- Geometric complexity theory. V: Efficient algorithms for Noether normalization
- Exact learning from an honest teacher that answers membership queries
- scientific article; zbMATH DE number 7250153 (Why is no real title available?)
- A generalized sylvester-gallai type theorem for quadratic polynomials
- Barriers for rank methods in arithmetic complexity
- Fast exact algorithms using Hadamard product of polynomials
- Improved bounds for reduction to depth 4 and depth 3
- Arithmetic circuits: a chasm at depth 3
- Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
- Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits
- Non-commutative computations: lower bounds and polynomial identity testing
- Characterizing arithmetic read-once formulae
- Circuits in bounded arithmetic. I
- Improved hitting set for orbit of ROABPs
- Almost all subgeneric third-order Chow decompositions are identifiable
- Progress on polynomial identity testing
- Jacobian hits circuits: hitting sets, lower bounds for depth-\(D\) occur-\(k\) formulas and depth-3 transcendence degree-\(k\) circuits
- 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
- Subspace arrangements, graph rigidity and derandomization through submodular optimization
- Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties)
- Subtraction-free complexity, cluster transformations, and spanning trees
- Deterministic polynomial identity tests for multilinear bounded-read formulae
- scientific article; zbMATH DE number 7758310 (Why is no real title available?)
- Linear-size constant-query IOPs for delegating computation
- On proving parameterized size lower bounds for multilinear algebraic models
- Towards blackbox identity testing of log-variate circuits
- Constructive non-commutative rank computation is in deterministic polynomial time
- On some computations on sparse polynomials
- Algorithms based on \(*\)-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing
- Algebraic independence in positive characteristic: a \(p\)-adic calculus
- A case of depth-3 identity testing, sparse factorization and duality
- Arithmetic and Algebraic Circuits
- scientific article; zbMATH DE number 7204375 (Why is no real title available?)
- scientific article; zbMATH DE number 7250152 (Why is no real title available?)
- Lower bounds for matrix factorization
- Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees
- Operator scaling: theory and applications
- \textsf{VNP} = \textsf{VP} in the multilinear world
- A Selection of Lower Bounds for Arithmetic Circuits
- Ulrich complexity
- scientific article; zbMATH DE number 7009617 (Why is no real title available?)
- scientific article; zbMATH DE number 7471587 (Why is no real title available?)
- Improved Explicit Hitting-Sets for ROABPs
- Lower bounds for matrix factorization
- 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
- Recent progress on arithmetic circuit lower bounds
- The partition rank of a tensor and \(k\)-right corners in \(\mathbb{F}_q^n\)
- scientific article; zbMATH DE number 7204372 (Why is no real title available?)
- Most secant varieties of tangential varieties to Veronese varieties are nondefective
- Lower bounds for tropical circuits and dynamic programs
- Polynomial interpolation and identity testing from high powers over finite fields
- A \(\tau \)-conjecture for Newton polygons
- Practical homomorphic message authenticators for arithmetic circuits
- \(\mathrm P \overset {?} {=} \mathrm{NP}\)
- On measures of space over real and complex numbers
- Algebraic complexity classes
- Faster sparse multivariate polynomial interpolation of straight-line programs
- On the complexity of computing a random Boolean function over the reals
- scientific article; zbMATH DE number 7561765 (Why is no real title available?)
- Random arithmetic formulas can be reconstructed efficiently
- Quadratic lower bounds for algebraic branching programs and formulas
- A lower bound on determinantal complexity
- Connections between graphs and matrix spaces
- An exponential lower bound for homogeneous depth four arithmetic formulas
- A review note on arbitrary precision arithmetic
- On the closures of monotone algebraic classes and variants of the determinant
- scientific article; zbMATH DE number 7250151 (Why is no real title available?)
- Emptiness problems for integer circuits
- On hard instances of non-commutative permanent
- Types of depth and formula size
- Partial strong structural controllability
- Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
- How to recover a secret with \(O(n)\) additions
- scientific article; zbMATH DE number 1148334 (Why is no real title available?)
- A quadratic size-hierarchy theorem for small-depth multilinear formulas
- 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
- Schur polynomials do not have small formulas if the determinant does not
- ReLU neural networks of polynomial size for exact maximum flow computation
- Linear independence, alternants, and applications
- Communication and information complexity
- A quadratic lower bound for homogeneous algebraic branching programs
- On \(\epsilon\)-sensitive monotone computations
- Tropical complexity, Sidon sets, and dynamic programming
- Notes on Boolean read-\(k\) and multilinear circuits
- Learning algebraic decompositions using Prony structures
- Lower bounds for depth-4 formulas computing iterated matrix multiplication
- A note on parameterized polynomial identity testing using hitting set generators
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)
