Division in logspace-uniformNC1
From MaRDI portal
Publication:2773023
DOI10.1051/ita:2001119zbMath1014.68062OpenAlexW2125463200MaRDI QIDQ2773023
Andrew Chiu, George Davida, Bruce Litow
Publication date: 20 February 2002
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: http://www.numdam.org/item?id=ITA_2001__35_3_259_0
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (25)
Uniform constant-depth threshold circuits for division and iterated multiplication. ⋮ Iterated multiplication in \(VTC^0\) ⋮ Dual VP classes ⋮ Log-space algorithms for paths and matchings in \(k\)-trees ⋮ On parallel complexity of analytic functions ⋮ A transfer method from bounded existential Diophantine equations to Tarski algebra formulas ⋮ The dynamic complexity of transitive closure is in DynTC\(^{0}\). ⋮ Census algorithms for chinese remainder pseudorank ⋮ On the complexity of regular-grammars with integer attributes ⋮ Small space analogues of Valiant's classes and the limitations of skew formulas ⋮ Mathematical logic: proof theory, constructive mathematics. Abstracts from the workshop held November 8--14, 2020 (hybrid meeting) ⋮ Root finding with threshold circuits ⋮ Counting paths in VPA is complete for \(\#\mathrm{NC}^1\) ⋮ Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}} ⋮ On the reducibility of sets inside NP to sets with low information content ⋮ Factoring and Testing Primes in Small Space ⋮ Fast arithmetics using Chinese remaindering ⋮ On the complexity of some problems on groups input as multiplication tables ⋮ Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs ⋮ Space complexity of abelian groups ⋮ Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\) ⋮ Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\) ⋮ Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics ⋮ Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\) ⋮ Parallel algorithms for matroid intersection and matroid parity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Counting problems and algebraic formal power series in noncommuting variables
- A complexity theory of efficient parallel algorithms
- On uniform circuit complexity
- On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
- Computing a context-free grammar-generating series
- On uniformity within \(NC^ 1\)
- A taxonomy of problems with fast parallel algorithms
- Logarithmic Depth Circuits for Algebraic Functions
- Log Depth Circuits for Division and Related Problems
- Fast Parallel Arithmetic via Modular Representation
- On Relating Time and Space to Size and Depth
- Space-Efficient Deterministic Simulation of Probabilistic Automata
- Integer division in residue number systems
This page was built for publication: Division in logspace-uniformNC1
