Record Details

Lower bounds in a parallel model without bit operations

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Lower bounds in a parallel model without bit operations
 
Creator MULMULEY, K
 
Subject maximum-flow problem
complexity
algorithm
computational complexity
parallel algorithms
lower bounds
 
Description 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 difference being that no bit operations are provided. It encompasses virtually all known parallel algorithms for (weighted) combinatorial optimization and algebraic problems. In this model we prove that for some large enough constant b, the mincost-flow problem for graphs with n vertices cannot be solved deterministically (or with randomization) in root n/b (expected) time using 2(root n/b) processors; this is so even if we restrict every cost and capacity to be an integer (nonnegative if it is a capacity) of bitlength at most an for some large enough constant a. A similar lower bound is also proved for the max-flow problem. It follows that these problems cannot be solved in our model deterministically (or with randomization) in Omega(N-c) (expected) time with 2(Omega(Nc)) processors, where c is an appropriate positive constant and N is the total bitlength of the input. Since these problems were known to be P-complete, this provides concrete support for the belief that P-completeness implies high parallel complexity and for the P not equal NC conjecture. Our lower bounds also extend to the PRAM model with limited bit operations, which provides instructions for parity and left or right shift by one bit. Our proof is based on basic algebraic geometry. So we investigate if the algebrogeometric approach could also work for the P versus NC problem. Our results support this possibility, and a close analysis of the limitation of our technique in this context suggests that such a proof of P not equal NC should somehow use geometric invariant theory in a deep way.
 
Publisher SIAM PUBLICATIONS
 
Date 2011-08-29T05:17:55Z
2011-12-26T12:58:25Z
2011-12-27T05:48:20Z
2011-08-29T05:17:55Z
2011-12-26T12:58:25Z
2011-12-27T05:48:20Z
1999
 
Type Article
 
Identifier SIAM JOURNAL ON COMPUTING, 28(4), 1460-1509
0097-5397
http://dx.doi.org/10.1137/S0097539794282930
http://dspace.library.iitb.ac.in/xmlui/handle/10054/11973
http://hdl.handle.net/10054/11973
 
Language en