Speaker: Ketan Mulmuley from the Department of Computer Science, University of Chicago
Title: P ≠ NC without bit operations
Abstract: This talk will give an overview of an old lower bound result, a special case of the P ≠ NC conjecture, called the P ≠ NC result without bit operations. It says that the maxflow problem cannot be solved in the PRAM model without bit operations in polylog(N) time using poly(N) processors, where N denotes the total bit-length of the input. This result was the beginning of geometric complexity theory (GCT), an approach to the P vs. NP and related problems via algebraic geometry, whose overview will be given in the subsequent two talks in the Fields Institute on Oct. 15 and 16.