Log Depth Circuits for Division and Related Problems

No abstract is available for this paper.

• Publication year

  1984

• Venue

  SIAM journal on computing (Print)

• Publication date

  1984-10-24

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/0215070
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Comparison of arithmetic functions with respect to boolean circuit depth

  1984cited by this paper
• The Classifikation of Problems which have Fast Parallel Algorithms

  1983cited by this paper
• Logarithmic depth circuits for algebraic functions

  1983cited by this paper
• Introduction to number theory

  1982cited by this paper
• On uniform circuit complexity

  1979cited by this paper
• On Relating Time and Space to Size and Depth

  1977cited by this paper

• IPS Lower Bounds for Formulas and Sum of ROABPs

  2025cites this paper
• Linear Decomposition of the Majority Boolean Function using the Ones on Smaller Variables

  2025cites this paper
• Efficient Floating-Point Divider based on Hybrid Cubic-Quadratic Goldschmidt Algorithm

  2025cites this paper
• Bounding the computational power of bosonic systems

  2025cites this paper
• The Probably Approximately Correct Learning Model in Computational Learning Theory

  2025cites this paper
• Reducing the Number of Qubits in Quantum Factoring

  2024cites this paper
• The Space Just Above One Clean Qubit

  2024cites this paper
• Optimal Traitor Tracing from Pairings

  2024cites this paper
• Launching Identity Testing into (Bounded) Space

  2024cites this paper
• Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs

  2024cites this paper
• Generation of small complexity classes using logical formulas, schemes and operations of bounded concatenation

  2023cites this paper
• Guest Column

  2023cites this paper
• Learning quantum states and unitaries of bounded gate complexity

  2023cites this paper
• A Numerical-based Parametric Error Analysis Method for Goldschmidt Floating Point Division

  2023cites this paper
• Improved Linear Decomposition of Majority and Threshold Boolean Functions

  2023cites this paper
• On the complexity of algebraic numbers, and the bit-complexity of straight-line programs

  2023cites this paper
• Scooby: Improved Multi-party Homomorphic Secret Sharing Based on FHE

  2023cites this paper
• A super-polynomial quantum advantage for combinatorial optimization problems

  2022cites this paper
• The GKR Protocol Revisited: Nearly Optimal Prover-Complexity for Polynomial-Time Wiring Algorithms and for Primality Testing in n1/2+o(1) Rounds

  2022cites this paper
• Privacy Preserving Computation in Cloud Using Reusable Garbled Oblivious RAMs

  2022cites this paper
• Delay Encryption by Cubing

  2022influential citation
• Low-Latency ASIC Algorithms of Modular Squaring of Large Integers for VDF Evaluation

  2022cites this paper
• Generating Very Large RNS Bases

  2022cites this paper
• An in-principle super-polynomial quantum advantage for approximating combinatorial optimization problems via computational learning theory.

  2022cites this paper
• On Structure-Preserving Cryptography and Lattices

  2022cites this paper
• Direct computation of branching programs and its applications to more efficient lattice-based cryptography

  2022cites this paper
• Skew circuits of small width. (English)

  2022cites this paper
• A Novel Exploitation of Errors in Redundant Residue Number System Architecture

  2021cites this paper
• Ring-Based Identity Based Encryption - Asymptotically Shorter MPK and Tighter Security

  2021cites this paper
• Unitary Branching Programs: Learnability and Lower Bounds

  2021cites this paper
• Generating Residue Number System Bases

  2021cites this paper
• Compact Designated Verifier NIZKs from the CDH Assumption Without Pairings

  2021cites this paper
• Round-optimal Honest-majority MPC in Minicrypt and with Everlasting Security

  2021cites this paper
• A New Minimax Theorem for Randomized Algorithms (Extended Abstract)

  2020cites this paper
• Cyclotomic Identity Testing and Applications

  2020cites this paper
• Compact NIZKs from Standard Assumptions on Bilinear Maps

  2020cites this paper
• Iterated multiplication in VTC0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ VTC ^0$$\end{document}

  2020influential citation
• Design and Implementation of a Low-Latency Modular Multiplication Algorithm

  2020cites this paper
• Low-Latency ASIC Algorithms of Modular Squaring of Large Integers for VDF Applications

  2020cites this paper
• Iterated multiplication in VTC0

  2020influential citation
• Expander Construction in VNC1

  2020cites this paper
• Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity

  2019cites this paper
• Designated Verifier/Prover and Preprocessing NIZKs from Diffie-Hellman Assumptions

  2019cites this paper
• Design and Analysis of Algorithms: A Contemporary Perspective

  2019cites this paper
• Group Signatures without NIZK: From Lattices in the Standard Model

  2019cites this paper
• Some Estimated Likelihoods for Computational Complexity

  2019cites this paper
• A Novel Exploitation of Errors in RRNS Architecture

  2019cites this paper
• Computing and Software Science: State of the Art and Perspectives

  2019cites this paper
• Non-Zero Inner Product Encryption Schemes from Various Assumptions: LWE, DDH and DCR

  2019cites this paper
• Deterministic Approximation of Random Walks in Small Space

  2019cites this paper
• Exploring Constructions of Compact NIZKs from Various Assumptions

  2019cites this paper
• Modular Multiplication Algorithm Suitable For Low-Latency Circuit Implementations

  2019cites this paper
• Approximating the Determinant of Well-Conditioned Matrices by Shallow Circuits

  2019cites this paper
• Proof-of-work certificates that can be efficiently computed in the cloud

  2018cites this paper
• A Study of High Performance Multiple Precision Arithmetic on Graphics Processing Units

  2018cites this paper
• A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates

  2018cites this paper
• On the Hidden Subgroup Problem as a Pivot in Quantum Complexity Theory

  2018cites this paper
• A Remark on Fourier Transform

  2018cites this paper
• The Matching Problem in General Graphs Is in Quasi-NC

  2017cites this paper
• Vector Encoding over Lattices and Its Applications

  2017cites this paper
• Neural Networks and Rational Functions

  2017influential citation
• Polynomial Time Interactive Proofs for Linear Algebra with Exponential Matrix Dimensions and Scalars Given by Polynomial Time Circuits

  2017influential citation
• Asymptotically Compact Adaptively Secure Lattice IBEs and Verifiable Random Functions via Generalized Partitioning Techniques

  2017cites this paper
• Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space

  2017cites this paper
• Polynomial time relatively computable triangular arrays for almost sure convergence

  2016cites this paper
• Bipartite perfect matching is in quasi-NC

  2016cites this paper
• Asymptotic Optimality of Parallel Short Division

  2016cites this paper
• Catalytic computation

  2016cites this paper
• Position-based quantum cryptography and catalytic computation

  2016cites this paper
• 5.1 Recap

  2015cites this paper
• The random oracle model: a twenty-year retrospective

  2015cites this paper
• On Randomness Extraction in AC0

  2015cites this paper
• Efficient Divide-and-Conquer Multiprecision Integer Division

  2015cites this paper
• An In-Depth Analysis of Data Structures Derived from van-Emde-Boas-Trees

  2015cites this paper
• Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs

  2014cites this paper
• A New Algorithm for Carry-Free Addition of Binary Signed-Digit Numbers

  2014cites this paper
• Open induction in a bounded arithmetic for TC0

  2014cites this paper
• Computational Aspects of Infinite-State Verification

  2014cites this paper
• Computing with a full memory: catalytic space

  2014cites this paper
• Open induction in a bounded arithmetic for TC0

  2014cites this paper
• Complexity of computation in finite fields

  2013cites this paper
• Comments on Arithmetic Complexity, Kleene Closure, and Formal Power Series

  2013cites this paper
• On parallel complexity of analytic functions

  2013cites this paper
• Low-depth quantum architectures for factoring

  2013cites this paper
• Branching-Time Model Checking of One-Counter Processes and Timed Automata

  2013cites this paper
• Lower bounds for RAMs and quantifier elimination

  2013cites this paper
• Efficient Algorithms for Zeckendorf Arithmetic

  2012cites this paper
• Determinism versus nondeterminism with arithmetic tests and computation: extended abstract

  2012cites this paper
• Algorithms and hardness results for parallel large margin learning

  2011cites this paper
• On the Complexity of Szilard Languages of Regulated Grammars

  2011cites this paper
• Root finding with threshold circuits

  2011cites this paper
• Parallel multiple precision division by a single precision divisor

  2011cites this paper
• Production , Manufacturing and Logistics Secure collaborative supply chain planning and inverse optimization – The JELS model

  2010cites this paper
• Grammatical compression: compressed equivalence and other problems

  2010cites this paper
• Efficient CRT-based residue-to-binary converter for the arbitrary moduli set

  2010cites this paper
• Circuit Complexity

  2010cites this paper
• Hashing, randomness and dictionaries

  2010cites this paper
• On Approximating the Entropy of Polynomial Mappings

  2010cites this paper
• Branching-time Model Checking of One-counter Processes

  2009cites this paper
• On Defining Integers And Proving Arithmetic Circuit Lower Bounds

  2009cites this paper