scientific article; zbMATH DE number 7009617

DOI10.4086/toc.2018.v014a018zbMath1412.68081OpenAlexW2904278047MaRDI QIDQ4612482

Amir Shpilka, Ben lee Volk, Michael A. Forbes

Publication date: 31 January 2019

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4086/toc.2018.v014a018

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

zbMATH Keywords

lower boundsderandomizationbarrierspolynomial identity testingalgebraic circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Related Items (2)

Sylvester-Gallai type theorems for quadratic polynomials ⋮ A generalized sylvester-gallai type theorem for quadratic polynomials

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Subexponential size hitting sets for bounded depth multilinear formulas
• Arithmetic circuits: the chasm at depth four gets wider
• Read-once polynomial identity testing
• Lower bounds and separations for constant depth multilinear circuits
• Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
• Almost-natural proofs
• Turing machines that take advice
• On computing the determinant in small parallel time using a small number of processors
• Pseudorandom bits for constant depth circuits
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• The monotone circuit complexity of Boolean functions
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• The complexity of partial derivatives
• A probabilistic remark on algebraic program testing
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• Lower bounds on arithmetic circuits via partial derivatives
• Pseudorandom functions in \(\text{TC}^0\) and cryptographic limitations to proving lower bounds
• Completeness and reduction in algebraic complexity theory
• Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
• The gap between monotone and non-monotone circuit complexity is exponential
• Algebraic independence and blackbox identity testing
• Balancing syntactically multilinear arithmetic circuits
• Unifying known lower bounds via geometric complexity theory
• Deterministic extractors for affine sources over large fields
• Improved bounds for reduction to depth 4 and depth 3
• Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
• Open Problems in Mathematics
• Natural Proofs versus Derandomization
• Arithmetic Circuits: A Chasm at Depth 3
• Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits
• Explicit Tensors
• Progress on Polynomial Identity Testing-II
• Pseudorandom Generators for Polynomial Threshold Functions
• Algebrization
• Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication
• An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
• On the Power of Homogeneous Depth 4 Arithmetic Circuits
• An Almost Optimal Rank Bound for Depth-3 Identities
• Fast Parallel Computation of Polynomials Using Few Processors
• Arithmetic Circuits: A survey of recent results and open questions
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Number-theoretic constructions of efficient pseudo-random functions
• Nonuniform ACC Circuit Lower Bounds
• Parity, circuits, and the polynomial-time hierarchy
• Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits
• Progress on Polynomial Identity Testing - II
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Simple Constructions of Almost k-wise Independent Random Variables
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• A Pseudorandom Generator from any One-way Function
• Algebraic methods for interactive proof systems
• Boundaries of VP and VNP
• On Algebraic Branching Programs of Small Width
• Blackbox Identity Testing for Bounded Top-Fanin Depth-3 Circuits: The Field Doesn't Matter
• Succinct hitting sets and barriers to proving algebraic circuits lower bounds
• Linear matroid intersection is in quasi-NC
• Blackbox Polynomial Identity Testing for Depth 3 Circuits
• Generalized matrix completion and algebraic natural proofs
• Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
• Hitting sets for multilinear read-once algebraic branching programs, in any order
• On the Computational Complexity of Algorithms
• Dimension Expanders via Rank Condensers
• Bipartite perfect matching is in quasi-NC
• Learning algorithms from natural proofs
• Proof Complexity Lower Bounds from Algebraic Circuit Complexity
• Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs
• From sylvester-gallai configurations to rank bounds
• On identity testing of tensors, low-rank recovery and compressed sensing
• Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
• Approaching the Chasm at Depth Four
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Multi-linear formulas for permanent and determinant are of super-polynomial size
• Natural proofs
• Derandomizing polynomial identity tests means proving circuit lower bounds

This page was built for publication: