Affordable Access

Lower bounds for prams over Z

Authors
  • Pellissier, Luc
  • Seiller, Thomas
Publication Date
Feb 21, 2020
Source
HAL-SHS
Keywords
Language
English
License
Unknown
External links

Abstract

This paper presents a new abstract method for proving lower bounds in computational complexity. Based on the notion of topological entropy for dynamical systems, the method captures four previous lower bounds results from the literature in algebraic complexity. Among these results lies Mulmuley's proof that "prams without bit operations" do not compute the maxflow problem in polylogarithmic time, which was the best known lower bounds in the quest for a proof that NC = Ptime. Inspired from a refinement of Steele and Yao's lower bounds, due to Ben-Or, we strengthen Mulmuley's result to a larger class of machines, showing that prams over integer do not compute maxflow in polylogarithmic time.

Report this publication

Statistics

Seen <100 times