Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity
Speaker
Manuel Sabin
UC Berkeley
Host
Akshay Degwekar, Pritish Kamath and Govind Ramnarayan
Abstract: We show that popular hardness conjectures about problems from the field of fine-grained complexity theory imply structural results for resource-based complexity classes. Namely, we show that if either k-Orthogonal Vectors requires $n^{k - o(1)}$ time or k-CLIQUE requires $n^{\omega k/3 - o(1)}$ time (for $\omega$ the matrix multiplication constant) to count on randomized machines for all but finitely many input lengths, then the following hold:
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
DTIME [t(n)] is not contained in BPP, for time-constructible $t(n)=n^{\omega(1)}$
These derandomizations improve over previous ones achieved from worst-case uniform assumptions by succeeding on all but finitely many input lengths, as is wanted in asymptotics. Previously, derandomizations from worst-case uniform assumptions were only know to succeed on infinitely many input lengths. It is specifically the structure and moderate hardness of the k-Orthogonal Vectors and k-CLIQUE problems that makes removing this restriction possible.
Via this uniform derandomization, we connect the problem-centric and resource-centric views of complexity theory by showing that exact hardness assumptions made about specific problems like k-CLIQUE imply structural results like EXP is not equal BPP. Viewed pessimistically, this result poses a barrier to proving some of the main assumptions of fine-grained complexity, lest we also attain major breakthroughs in classical complexity theory. Alternately, we can hope to make progress on problems like EXP vs BPP by working on very concrete conjectures about specific problems.
Joint with: Marco Carmosino, Russell Impagliazzo
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
DTIME [t(n)] is not contained in BPP, for time-constructible $t(n)=n^{\omega(1)}$
These derandomizations improve over previous ones achieved from worst-case uniform assumptions by succeeding on all but finitely many input lengths, as is wanted in asymptotics. Previously, derandomizations from worst-case uniform assumptions were only know to succeed on infinitely many input lengths. It is specifically the structure and moderate hardness of the k-Orthogonal Vectors and k-CLIQUE problems that makes removing this restriction possible.
Via this uniform derandomization, we connect the problem-centric and resource-centric views of complexity theory by showing that exact hardness assumptions made about specific problems like k-CLIQUE imply structural results like EXP is not equal BPP. Viewed pessimistically, this result poses a barrier to proving some of the main assumptions of fine-grained complexity, lest we also attain major breakthroughs in classical complexity theory. Alternately, we can hope to make progress on problems like EXP vs BPP by working on very concrete conjectures about specific problems.
Joint with: Marco Carmosino, Russell Impagliazzo