## Abstract

We study a new model of space-bounded computation, the random-query model. The model is based on a branching-program over input variables x1, . . ., xn. In each time step, the branching program gets as an input a random index i ∈ {1, . . ., n}, together with the input variable xi (rather than querying an input variable of its choice, as in the case of a standard (oblivious) branching program). We motivate the new model in various ways and study time-space tradeoff lower bounds in this model. Our main technical result is a quadratic time-space lower bound for zero-error computations in the random-query model, for XOR, Majority and many other functions. More precisely, a zero-error computation is a computation that stops with high probability and such that conditioning on the event that the computation stopped, the output is correct with probability 1. We prove that for any Boolean function f : {0, 1}^{n} → {0, 1}, with sensitivity k, any zero-error computation with time T and space S, satisfies T · (S + log n) ≥ Ω(n · k). We note that the best time-space lower bounds for standard oblivious branching programs are only slightly super linear and improving these bounds is an important long-standing open problem. To prove our results, we study a memory-bounded variant of the coupon-collector problem that seems to us of independent interest and to the best of our knowledge has not been studied before. We consider a zero-error version of the coupon-collector problem. In this problem, the coupon-collector could explicitly choose to stop when he/she is sure with zero-error that all coupons have already been collected. We prove that any zero-error coupon-collector that stops with high probability in time T, and uses space S, satisfies T · (S + log n) ≥ Ω(n^{2}), where n is the number of different coupons.

Original language | English (US) |
---|---|

Title of host publication | 11th Innovations in Theoretical Computer Science Conference, ITCS 2020 |

Editors | Thomas Vidick |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959771344 |

DOIs | |

State | Published - Jan 2020 |

Event | 11th Innovations in Theoretical Computer Science Conference, ITCS 2020 - Seattle, United States Duration: Jan 12 2020 → Jan 14 2020 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 151 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 11th Innovations in Theoretical Computer Science Conference, ITCS 2020 |
---|---|

Country/Territory | United States |

City | Seattle |

Period | 1/12/20 → 1/14/20 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

- Branching programs
- Random-query model
- Time-space trade-offs