TY - GEN
T1 - Randomized vs. Deterministic Separation in time-space tradeoffs of multi-output functions
AU - Yu, Huacheng
AU - Zhan, Wei
N1 - Publisher Copyright:
© 2024 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.
PY - 2024/1
Y1 - 2024/1
N2 - 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.
AB - 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.
KW - Borodin-Cook method
KW - Randomness
KW - Time-space tradeoffs
UR - http://www.scopus.com/inward/record.url?scp=85184137948&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85184137948&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ITCS.2024.99
DO - 10.4230/LIPIcs.ITCS.2024.99
M3 - Conference contribution
AN - SCOPUS:85184137948
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 15th Innovations in Theoretical Computer Science Conference, ITCS 2024
A2 - Guruswami, Venkatesan
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 15th Innovations in Theoretical Computer Science Conference, ITCS 2024
Y2 - 30 January 2024 through 2 February 2024
ER -