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)- 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
- Subspace arrangements, graph rigidity and derandomization through submodular optimization
- Non-commutative computations: lower bounds and polynomial identity testing
- Deterministic polynomial identity tests for multilinear bounded-read formulae
- Progress on polynomial identity testing. II
- Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
- Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties)
- Barriers for rank methods in arithmetic complexity
- Algebraic independence in positive characteristic: a \(p\)-adic calculus
- Communication and information complexity
- scientific article; zbMATH DE number 7561740 (Why is no real title available?)
- Improved bounds for reduction to depth 4 and depth 3
- Linear-size constant-query IOPs for delegating computation
- Lower bounds for the sum of small-size algebraic branching programs
- Random arithmetic formulas can be reconstructed efficiently
- Ulrich complexity
- A generalized sylvester-gallai type theorem for quadratic polynomials
- Notes on Boolean read-\(k\) and multilinear circuits
- An exponential lower bound for homogeneous depth four arithmetic formulas
- A case of depth-3 identity testing, sparse factorization and duality
- Learning algebraic decompositions using Prony structures
- Read-once polynomial identity testing
- Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree
- ReLU neural networks of polynomial size for exact maximum flow computation
- The limits of depth reduction for arithmetic formulas: it's all about the top fan-in
- 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
- scientific article; zbMATH DE number 7561757 (Why is no real title available?)
- Algebraic complexity classes
- Emptiness problems for integer circuits
- Linear independence, alternants, and applications
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)
