scientific article; zbMATH DE number 7250150

DOI10.4230/LIPIcs.CCC.2018.10zbMath1442.68062arXiv1801.09275MaRDI QIDQ5121898

Zeyu Guo, Amit Sinhababu, Nitin Saxena

Publication date: 22 September 2020

Full work available at URL: https://arxiv.org/abs/1801.09275

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

Jacobianfinite fieldalgebraic dependencesatisfiabilityapproximate polynomialPSPACEEXPSPACEhitting-setArthur-Merlinborder VPGCT chasm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computational invariant theory. With two appendices by Vladimir L. Popov and an addendum by Nobert A. Campo and Vladimir L. Popov
• Extractors and rank extractors for polynomial sources
• On the order of approximation in approximative triadic decompositions of tensors
• Apolarity and canonical forms for homogeneous polynomials
• The complexity of factors of multivariate polynomials
• The complexity of the word problems for commutative semigroups and polynomial ideals
• On the affine Bezout inequality
• Algebraic independence and blackbox identity testing
• Hilbert's Nullstellensatz is in the polynomial hierarchy
• Complexity of ring morphism problems
• Geometric complexity theory V: Efficient algorithms for Noether normalization
• Arithmetic Circuits: A survey of recent results and open questions
• Powers of tensors and fast matrix multiplication
• Progress on Polynomial Identity Testing - II
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Fast Parallel Matrix Inversion Algorithms
• Algebraic Independence over Positive Characteristic: New Criterion and Applications to Locally Low Algebraic Rank Circuits
• Sharp Effective Nullstellensatz
• Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory
• Bootstrapping variables in algebraic circuits
• Computational Complexity
• Jacobian hits circuits
• Algebraic independence in positive characteristic: A $p$-adic calculus