Log Depth Circuits for Division and Related Problems
From MaRDI portal
Publication:3756526
DOI10.1137/0215070zbMATH Open0619.68047OpenAlexW2003519998MaRDI QIDQ3756526FDOQ3756526
Paul Beame, Stephen Cook, H. James Hoover
Publication date: 1986
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0215070
Recommendations
algorithmmultiple productscircuit complexitydivisibilityspace complexitycircuit depthinteger divisionpoweringdepth complexityoptimal depth Boolean ciruits
Cited In (68)
- Computing a context-free grammar-generating series
- Extensions of an idea of McNaughton
- Root finding with threshold circuits
- Title not available (Why is that?)
- Threshold circuits of small majority-depth
- Space complexity of abelian groups
- Efficient CRT-based residue-to-binary converter for the arbitrary moduli set
- A \#SAT algorithm for small constant-depth circuits with PTF gates
- On the parallel complexity of linear groups
- Sieve algorithms for perfect power testing
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- Efficient parallel circuits and algorithms for division
- Mathematical logic: proof theory, constructive mathematics. Abstracts from the workshop held November 8--14, 2020 (hybrid meeting)
- Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics
- Multiplication, division, and shift instructions in parallel random access machines
- The Extraordinary Power of Division in Straight Line Programs
- Fast arithmetics using Chinese remaindering
- A randomized sublinear time parallel GCD algorithm for the EREW PRAM
- Symmetries and the complexity of pure Nash equilibrium
- Efficient threshold circuits for power series
- Polynomial time relatively computable triangular arrays for almost sure convergence
- On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
- A parametric error analysis of Goldschmidt's division algorithm
- Inversion in finite fields using logarithmic depth
- Title not available (Why is that?)
- Perfect computational equivalence between quantum Turing machines and finitely generated uniform quantum circuit families
- The random oracle model: a twenty-year retrospective
- Division in logspace-uniform NC
- Iterated multiplication in \(VTC^0\)
- On design of circuits of logarithmic depth for inversion in finite fields
- Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\)
- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- Optimal Size Integer Division Circuits
- Effective entropies and data compression
- Secure collaborative supply chain planning and inverse optimization -- the JELS model
- On uniformity within \(NC^ 1\)
- Compact designated verifier NIZKs from the CDH assumption without pairings
- On the complexity of some problems on groups input as multiplication tables
- Ring-based identity based encryption -- asymptotically shorter MPK and tighter security
- Synthesizers and their application to the parallel construction of pseudo-random functions
- Skew circuits of small width
- Boolean circuits versus arithmetic circuits
- An arithmetic model of computation equivalent to threshold circuits
- Counting problems and algebraic formal power series in noncommuting variables
- Isolation, matching, and counting uniform and nonuniform upper bounds
- Highly parallel computations modulo a number having only small prime factors
- Expressing uniformity via oracles
- Parallel models of computation: An introductory survey
- Expander construction in \(\mathrm{VNC}^1\)
- On iterated integer product
- Threshold circuits of bounded depth
- Modular exponentiation via the explicit Chinese remainder theorem
- On small depth threshold circuits
- Complexity of computation in finite fields
- A div(n) depth Boolean circuit for smooth modular inverse
- Ranking and formal power series
- The complexity of computing the number of strings of given length in context-free languages
- Title not available (Why is that?)
- On parallel complexity of analytic functions
- Logarithmic Depth Circuits for Algebraic Functions
- Title not available (Why is that?)
- Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space
- Title not available (Why is that?)
- On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1
- Compact NIZKs from standard assumptions on bilinear maps
- Bipartite Perfect Matching is in Quasi-NC
- Cyclotomic identity testing and applications
- Direct computation of branching programs and its applications to more efficient lattice-based cryptography
This page was built for publication: Log Depth Circuits for Division and Related Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3756526)
