scientific article; zbMATH DE number 7561765
From MaRDI portal
Publication:5092488
DOI10.4230/LIPIcs.CCC.2020.37MaRDI QIDQ5092488
Publication date: 21 July 2022
Full work available at URL: https://arxiv.org/abs/2005.10885
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Arithmetic circuits: the chasm at depth four gets wider
- On defining integers and proving arithmetic circuit lower bounds
- Finding paths of length \(k\) in \(O^{*}(2^k)\) time
- Matching is as easy as matrix inversion
- Constructing a perfect matching is in random NC
- Equivalence of free Boolean graphs can be decided probabilistically in polynomial time
- Factoring numbers in O(log n) arithmetic steps
- Hardness vs randomness
- Completeness and reduction in algebraic complexity theory
- Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields.
- PRIMES is in P
- Improved bounds for reduction to depth 4 and depth 3
- Arithmetic Circuits: A Chasm at Depth 3
- Progress on Polynomial Identity Testing-II
- Arithmetic Circuits: A survey of recent results and open questions
- Field Theory
- Primality and identity testing via Chinese remaindering
- Simple extractors for all min-entropies and a new pseudorandom generator
- Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits
- Progress on Polynomial Identity Testing - II
- Greatest common divisors of polynomials given by straight-line programs
- COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
- Bootstrapping variables in algebraic circuits
- Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits
- Tensor-Rank and Lower Bounds for Arithmetic Formulas
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Pseudo-random generators for all hardnesses
