Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR14-124 | 7th October 2014 10:28

The Depth Irreducibility Hypothesis


Authors: Periklis Papakonstantinou
Publication: 7th October 2014 11:44
Downloads: 1839


We propose the following computational assumption: in general if we try to compress the depth of a circuit family (parallel time) more than a constant factor we will suffer super-quasi-polynomial blowup in the size (number of processors). This assumption is only slightly stronger than the popular assumption about the robustness of $NC$, and we observe that it has surprising consequences. Note also that the choice of super-quasi-polynomial blowup is the smallest bound that avoids the circuit class collapse of [Vol98].

In this proposal we put our assumption in perspective, discuss its relation to the existing literature, and show that it has two important consequences. The first consequence is $NC\neq SC$, where $NC$ is the class characterized by uniform circuits of poly-logarithmic depth and polynomial size, and $SC$ is characterized by algorithms that run in poly-logarithmic space and polynomial time. For the second consequence we use an additional but mild complexity assumption to obtain a strong separation between the graph isomorphism GraphIso and the group isomorphism GroupIso problem. In particular, we show that GraphIso is not reducible to GroupIso using circuits of $O(\log n)$ depth.

ISSN 1433-8092 | Imprint