Now showing items 1-6 of 6

    • Computational Complexity and the Existence of Complexity Gaps 

      Borodin, Allan B. (Cornell University, 1969-08)
      Computational Complexity and the Existence of Complexity Gaps
    • Fast Parallel Matrix and GCD Computations 

      Borodin, Allan B.; Von zur Gathen, Joachim; Hopcroft, John E. (Cornell University, 1982-04)
      We present parallel algorithms to compute the determinant and characteristic polynomial of n x n-matrices and the gcd of polynomials of degree $\leq$n. The algorithms use parallel time $O(\log^{2}n)$ and a polynomial ...
    • Merging on Parallel Models of Computation 

      Borodin, Allan B.; Hopcroft, John E. (Cornell University, 1981-09)
      A variety of models have been proposed for the study of synchronous parallel computation. We review these models and study further some prototype problems. Within a spectrum of shared memory models, we show that $\log ...
    • On the Efficiency of Programs in Subrecursive Formalisms 

      Constable, Robert L.; Borodin, Allan B. (Cornell University, 1970-03)
      NO ABSTRACT SUPPLIED
    • Routing in Networks 

      Borodin, Allan B.; Hopcroft, John E. (Cornell University, 1981-11)
      NO ABSTRACT SUPPLIED
    • Some Comments on Functional Self-Reducibility and the NP Hierarchy 

      Borodin, Allan B.; Demers, Alan J. (Cornell University, 1976-07)
      In Valiant [11] and Schnorr [9], concepts of "functional self-reducibility" are introduced and investigated. We concentrate on the class NP and on the NP hierarchy of Meyer and Stockmeyer [7] to further investigate these ...