Randomized vs. Deterministic Separation in time-space tradeoffs of multi-output functions

Huacheng Yu, Wei Zhan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We prove the first polynomial separation between randomized and deterministic time-space tradeoffs of multi-output functions. In particular, we present a total function that on the input of n elements in [n], outputs O(n) elements, such that: There exists a randomized oblivious algorithm with space O(log n), time O(n log n) and one-way access to randomness, that computes the function with probability 1-O(1/n); Any deterministic oblivious branching program with space S and time T that computes the function must satisfy T2S ≥ Δ(n2.5/ log n). This implies that logspace randomized algorithms for multi-output functions cannot be black-box derandomized without an eΔ(n1/4) overhead in time. Since previously all the polynomial time-space tradeoffs of multi-output functions are proved via the Borodin-Cook method, which is a probabilistic method that inherently gives the same lower bound for randomized and deterministic branching programs, our lower bound proof is intrinsically different from previous works. We also examine other natural candidates for proving such separations, and show that any polynomial separation for these problems would resolve the long-standing open problem of proving n1+Δ(1)time lower bound for decision problems with polylog(n) space.

Original languageEnglish (US)
Title of host publication15th Innovations in Theoretical Computer Science Conference, ITCS 2024
EditorsVenkatesan Guruswami
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959773096
DOIs
StatePublished - Jan 2024
Event15th Innovations in Theoretical Computer Science Conference, ITCS 2024 - Berkeley, United States
Duration: Jan 30 2024Feb 2 2024

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume287
ISSN (Print)1868-8969

Conference

Conference15th Innovations in Theoretical Computer Science Conference, ITCS 2024
Country/TerritoryUnited States
CityBerkeley
Period1/30/242/2/24

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Borodin-Cook method
  • Randomness
  • Time-space tradeoffs

Fingerprint

Dive into the research topics of 'Randomized vs. Deterministic Separation in time-space tradeoffs of multi-output functions'. Together they form a unique fingerprint.

Cite this