Chicago Journal of Theoretical (2003)
Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, Georg Gottlob, Gil Neiger, ...
We present a Logspace, many-one reduction from the undirected Abstract-1 s--t connectivity problem to its complement. This shows that SL = coSL.
Rapidly Mixing Markov Chains (2001)
Dr. Ketan Mulmuley, Dr. Sundar Vishwanathan, Rahul T. Shah
The computational difficulty of the problems of counting the elements of a finite set of combinatorial structures has led to the development of randomized algorithms. The problem of generating at...
A Lower Bound on Computing Blocking Flows in Graphs (2001)
We show that the Maximum Blocking Flow problem on a graph of n vertices cannot be computed in time o(n 1/8 ) with polynomially many processors on an unbounded fan-in PRAM without bit operations, even...
A Lower Bound for the Shortest Path Problem (2001)
We show that the Shortest Path Problem cannot be solved in o(log n) time on an unbounded fan-in PRAM without bit operations using poly(n) processors even when the bit-lengths of the weights on the...
Full abstraction and semantic equivalence / (1985)
Thesis (Ph.D.)--Carnegie-Mellon University.
Lower Bounds In A Parallel Model Without Bit Operations (1970)
Ketan Mulmuley, Siam J. Comput
. We define a natural and realistic model of parallel computation called the PRAM model without bit operations. It is like the usual PRAM model, the main di#erence being that no bit operations are...