ECCC-Report TR14-124https://eccc.weizmann.ac.il/report/2014/124Comments and Revisions published for TR14-124en-usTue, 07 Oct 2014 11:44:06 +0300
Paper TR14-124
| The Depth Irreducibility Hypothesis |
Periklis Papakonstantinou
https://eccc.weizmann.ac.il/report/2014/124We 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.Tue, 07 Oct 2014 11:44:06 +0300https://eccc.weizmann.ac.il/report/2014/124