scientific article; zbMATH DE number 7009617
From MaRDI portal
Publication:4612482
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
Cites work
- scientific article; zbMATH DE number 3651744 (Why is no real title available?)
- scientific article; zbMATH DE number 976329 (Why is no real title available?)
- scientific article; zbMATH DE number 3999837 (Why is no real title available?)
- scientific article; zbMATH DE number 6472651 (Why is no real title available?)
- A Pseudorandom Generator from any One-way Function
- A probabilistic remark on algebraic program testing
- Algebraic independence and blackbox identity testing
- Algebraic methods for interactive proof systems
- Algebrization: a new barrier in complexity theory
- Almost-natural proofs
- An almost optimal rank bound for depth-3 identities
- An exponential lower bound for homogeneous depth four arithmetic formulas
- Approaching the chasm at depth four
- Arithmetic circuits: a chasm at depth 3
- Arithmetic circuits: a survey of recent results and open questions
- Arithmetic circuits: the chasm at depth four gets wider
- Balancing syntactically multilinear arithmetic circuits
- Bipartite perfect matching is in quasi-NC
- Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
- Blackbox Polynomial Identity Testing for Depth 3 Circuits
- Blackbox identity testing for bounded top-fanin depth-3 circuits: the field doesn't matter
- Boundaries of VP and VNP
- Completeness and reduction in algebraic complexity theory
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Deterministic extractors for affine sources over large fields
- Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
- Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
- Dimension Expanders via Rank Condensers
- Elusive functions and lower bounds for arithmetic circuits
- Explicit tensors
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Fast Parallel Computation of Polynomials Using Few Processors
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- From sylvester-gallai configurations to rank bounds
- Generalized matrix completion and algebraic natural proofs
- Hardness-randomness tradeoffs for bounded depth arithmetic circuits
- Hitting sets for multilinear read-once algebraic branching programs, in any order
- Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
- Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs
- Improved bounds for reduction to depth 4 and depth 3
- 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
- Linear matroid intersection is in quasi-NC
- Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
- Lower bounds and separations for constant depth multilinear circuits
- Lower bounds for depth-4 formulas computing iterated matrix multiplication
- Lower bounds on arithmetic circuits via partial derivatives
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Multi-linear formulas for permanent and determinant are of super-polynomial size
- Natural proofs
- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- Nonuniform ACC circuit lower bounds
- Number-theoretic constructions of efficient pseudo-random functions
- On Algebraic Branching Programs of Small Width
- On computing the determinant in small parallel time using a small number of processors
- On identity testing of tensors, low-rank recovery and compressed sensing
- On the Computational Complexity of Algorithms
- On the power of homogeneous depth 4 arithmetic circuits
- Open Problems in Mathematics
- Parity, circuits, and the polynomial-time hierarchy
- Progress on polynomial identity testing
- Progress on polynomial identity testing. II
- Proof complexity lower bounds from algebraic circuit complexity
- Pseudorandom bits for constant depth circuits
- Pseudorandom functions in \(\text{TC}^0\) and cryptographic limitations to proving lower bounds
- Read-once polynomial identity testing
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Separation of multilinear circuit and formula size
- Simple Constructions of Almost k-wise Independent Random Variables
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Subexponential size hitting sets for bounded depth multilinear formulas
- Succinct hitting sets and barriers to proving algebraic circuits lower bounds
- The complexity of partial derivatives
- The gap between monotone and non-monotone circuit complexity is exponential
- The monotone circuit complexity of Boolean functions
- Turing machines that take advice
- Unifying known lower bounds via geometric complexity theory
- \(\Sigma_ 1^ 1\)-formulae on finite structures
Cited in
(9)- A PSPACE construction of a hitting set for the closure of small algebraic circuits
- A generalized sylvester-gallai type theorem for quadratic polynomials
- Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
- Hitting sets and reconstruction for dense orbits in VPe and ΣΠΣ circuits
- Succinct hitting sets and barriers to proving algebraic circuits lower bounds
- Generalized matrix completion and algebraic natural proofs
- scientific article; zbMATH DE number 7471587 (Why is no real title available?)
- Computing Hitting Set Kernels By AC^0-Circuits
- Feasibly constructive proofs of succinct weak circuit lower bounds
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)
