McKay, Dylan M. ;
Williams, Richard Ryan
Quadratic TimeSpace Lower Bounds for Computing Natural Functions with a Random Oracle
Abstract
We define a model of sizeS Rway branching programs with oracles that can make up to S distinct oracle queries over all of their possible inputs, and generalize a lower bound proof strategy of Beame [SICOMP 1991] to apply in the case of random oracles. Through a series of succinct reductions, we prove that the following problems require randomized algorithms where the product of running time and space usage must be Omega(n^2/poly(log n)) to obtain correct answers with constant nonzero probability, even for algorithms with constanttime access to a uniform random oracle (i.e., a uniform random hash function):
 Given an unordered list L of n elements from [n] (possibly with repeated elements), output [n]L.
 Counting satisfying assignments to a given 2CNF, and printing any satisfying assignment to a given 3CNF. Note it is a major open problem to prove a timespace product lower bound of n^{2o(1)} for the decision version of SAT, or even for the decision problem MajoritySAT.
 Printing the truth table of a given CNF formula F with k inputs and n=O(2^k) clauses, with values printed in lexicographical order (i.e., F(0^k), F(0^{k1}1), ..., F(1^k)). Thus we have a 4^k/poly(k) lower bound in this case.
 Evaluating a circuit with n inputs and O(n) outputs.
As our lower bounds are based on Rway branching programs, they hold for any reasonable model of computation (e.g. logword RAMs and multitape Turing machines).
BibTeX  Entry
@InProceedings{mckay_et_al:LIPIcs:2018:10149,
author = {Dylan M. McKay and Richard Ryan Williams},
title = {{Quadratic TimeSpace Lower Bounds for Computing Natural Functions with a Random Oracle}},
booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
pages = {56:156:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770958},
ISSN = {18688969},
year = {2018},
volume = {124},
editor = {Avrim Blum},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10149},
URN = {urn:nbn:de:0030drops101493},
doi = {10.4230/LIPIcs.ITCS.2019.56},
annote = {Keywords: branching programs, random oracles, timespace tradeoffs, lower bounds, SAT, counting complexity}
}
08.01.2019
Keywords: 

branching programs, random oracles, timespace tradeoffs, lower bounds, SAT, counting complexity 
Seminar: 

10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Issue date: 

2018 
Date of publication: 

08.01.2019 