PRAMs over integers do not compute maxflow efficiently
share
Finding lower bounds in complexity theory has proven to be an extremely difficult task. In this article, we analyze two proofs of complexity lower bound: Ben-Or's proof of minimal height of algebraic computational trees deciding certain problems and Mulmuley's proof that restricted Parallel Random Access Machines (prams) over integers can not decide P-complete problems efficiently. We present the aforementioned models of computation in a framework inspired by dynamical systems and models of linear logic : graphings. This interpretation allows to connect the classical proofs to topological entropy, an invariant of these systems; to devise an algebraic formulation of parallelism of computational models; and finally to strengthen Mulmuley's result by separating the geometrical insights of the proof from the ones related to the computation and blending these with Ben-Or's proof. Looking forward, the interpretation of algebraic complexity theory as dynamical system might shed a new light on research programs such as Geometric Complexity Theory.
READ FULL TEXT