Carmosino, Marco L. ;
Impagliazzo, Russell ;
Sabin, Manuel
FineGrained Derandomization: From ProblemCentric to ResourceCentric Complexity
Abstract
We show that popular hardness conjectures about problems from the field of finegrained complexity theory imply structural results for resourcebased complexity classes. Namely, we show that if either kOrthogonal Vectors or kCLIQUE requires n^{epsilon k} time, for some constant epsilon>1/2, to count (note that these conjectures are significantly weaker than the usual ones made on these problems) on randomized machines for all but finitely many input lengths, then we have the following derandomizations:
 BPP can be decided in polynomial time using only n^alpha random bits on average over any efficient input distribution, for any constant alpha>0
 BPP can be decided in polynomial time with no randomness on average over the uniform distribution
This answers an open question of Ball et al. (STOC '17) in the positive of whether derandomization can be achieved from conjectures from finegrained complexity theory. More strongly, these derandomizations improve over all previous ones achieved from worstcase uniform assumptions by succeeding on all but finitely many input lengths. Previously, derandomizations from worstcase uniform assumptions were only know to succeed on infinitely many input lengths. It is specifically the structure and moderate hardness of the kOrthogonal Vectors and kCLIQUE problems that makes removing this restriction possible.
Via this uniform derandomization, we connect the problemcentric and resourcecentric views of complexity theory by showing that exact hardness assumptions about specific problems like kCLIQUE imply quantitative and qualitative relationships between randomized and deterministic time. This can be either viewed as a barrier to proving some of the main conjectures of finegrained complexity theory lest we achieve a major breakthrough in unconditional derandomization or, optimistically, as route to attain such derandomizations by working on very concrete and weak conjectures about specific problems.
BibTeX  Entry
@InProceedings{carmosino_et_al:LIPIcs:2018:9031,
author = {Marco L. Carmosino and Russell Impagliazzo and Manuel Sabin},
title = {{FineGrained Derandomization: From ProblemCentric to ResourceCentric Complexity}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {27:127:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770767},
ISSN = {18688969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9031},
URN = {urn:nbn:de:0030drops90316},
doi = {10.4230/LIPIcs.ICALP.2018.27},
annote = {Keywords: Derandomization, Hardness vs Randomness, FineGrained Complexity, AverageCase Complexity, kOrthogonal Vectors, kCLIQUE}
}
04.07.2018
Keywords: 

Derandomization, Hardness vs Randomness, FineGrained Complexity, AverageCase Complexity, kOrthogonal Vectors, kCLIQUE 
Seminar: 

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Issue date: 

2018 
Date of publication: 

04.07.2018 