scientific article; zbMATH DE number 7009617
From MaRDI portal
Publication:4612482
DOI10.4086/TOC.2018.V014A018zbMATH Open1412.68081OpenAlexW2904278047MaRDI QIDQ4612482FDOQ4612482
Authors: 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 of this publication is not available (Why is that?)
Recommendations
- Succinct hitting sets and barriers to proving algebraic circuits lower bounds
- Proof complexity lower bounds from algebraic circuit complexity
- scientific article; zbMATH DE number 7471587
- Near-optimal bootstrapping of hitting sets for algebraic circuits
- On the limit of some algorithmic approach to circuit lower bounds
- On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy
- Feasibly constructive proofs of succinct weak circuit lower bounds
- On proving circuit lower bounds against the polynomial-time hierarchy: positive and negative results
- scientific article; zbMATH DE number 806749
- Circuit-size lower bounds and non-reducibility to sparse sets
Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- On the Computational Complexity of Algorithms
- Almost-natural proofs
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- The complexity of partial derivatives
- A probabilistic remark on algebraic program testing
- Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Title not available (Why is that?)
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Simple Constructions of Almost k-wise Independent Random Variables
- A Pseudorandom Generator from any One-way Function
- Title not available (Why is that?)
- Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Hitting sets for multilinear read-once algebraic branching programs, in any order
- Dimension Expanders via Rank Condensers
- On identity testing of tensors, low-rank recovery and compressed sensing
- Title not available (Why is that?)
- On computing the determinant in small parallel time using a small number of processors
- Parity, circuits, and the polynomial-time hierarchy
- The monotone circuit complexity of Boolean functions
- Pseudorandom bits for constant depth circuits
- Completeness and reduction in algebraic complexity theory
- Fast Parallel Computation of Polynomials Using Few Processors
- Arithmetic circuits: the chasm at depth four gets wider
- Lower bounds on arithmetic circuits via partial derivatives
- Arithmetic circuits: a chasm at depth 3
- Pseudorandom generators for polynomial threshold functions
- An exponential lower bound for homogeneous depth four arithmetic formulas
- Separation of multilinear circuit and formula size
- Subexponential size hitting sets for bounded depth multilinear formulas
- Arithmetic circuits: a survey of recent results and open questions
- Hardness-randomness tradeoffs for bounded depth arithmetic circuits
- Blackbox Polynomial Identity Testing for Depth 3 Circuits
- 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
- 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
- Number-theoretic constructions of efficient pseudo-random functions
- Algebrization: a new barrier in complexity theory
- Deterministic extractors for affine sources over large fields
- Algebraic methods for interactive proof systems
- Balancing syntactically multilinear arithmetic circuits
- An almost optimal rank bound for depth-3 identities
- Turing machines that take advice
- The gap between monotone and non-monotone circuit complexity is exponential
- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- Progress on polynomial identity testing
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Title not available (Why is that?)
- Blackbox identity testing for bounded top-fanin depth-3 circuits: the field doesn't matter
- Read-once polynomial identity testing
- From sylvester-gallai configurations to rank bounds
- Elusive functions and lower bounds for arithmetic circuits
- Nonuniform ACC circuit lower bounds
- Progress on polynomial identity testing. II
- On the power of homogeneous depth 4 arithmetic circuits
- Pseudorandom functions in \(\text{TC}^0\) and cryptographic limitations to proving lower bounds
- Algebraic independence and blackbox identity testing
- Jacobian hits circuits: hitting sets, lower bounds for depth-\(D\) occur-\(k\) formulas and depth-3 transcendence degree-\(k\) circuits
- Learning algorithms from natural proofs
- Unifying known lower bounds via geometric complexity theory
- Natural proofs versus derandomization
- Open Problems in Mathematics
- Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
- Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs
- Succinct hitting sets and barriers to proving algebraic circuits lower bounds
- Proof Complexity Lower Bounds from Algebraic Circuit Complexity
- Linear matroid intersection is in quasi-NC
- Bipartite perfect matching is in quasi-NC
- Improved bounds for reduction to depth 4 and depth 3
- On Algebraic Branching Programs of Small Width
- Boundaries of VP and VNP
- Generalized matrix completion and algebraic natural proofs
- Lower bounds for depth-4 formulas computing iterated matrix multiplication
- Explicit tensors
Cited In (8)
- Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
- A PSPACE construction of a hitting set for the closure of small algebraic circuits
- Feasibly constructive proofs of succinct weak circuit lower bounds
- Computing Hitting Set Kernels By AC^0-Circuits
- A generalized sylvester-gallai type theorem for quadratic polynomials
- Title not available (Why is that?)
- Hitting sets and reconstruction for dense orbits in VPe and ΣΠΣ circuits
- Sylvester-Gallai type theorems for quadratic polynomials
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4612482)
