## Abstract

A solution is given by a representation and a query algorithm so that . The time of the query algorithm is the number of bits it reads in .

In this paper, we consider the case of *succinct* representations where for some *redundancy* . For a boolean version of the problem of polynomial evaluation with preprocessing of coefficients, we show a lower bound on the redundancy-query time tradeoff of the form

In particular, for very small redundancies , we get an almost optimal lower bound stating that the query algorithm has to inspect almost the entire data structure (up to a logarithmic factor). We show similar lower bounds for problems satisfying a certain combinatorial property of a coding theoretic flavor. Previously, no lower bounds were known on in the general model for explicit functions, even for very small redundancies.

By restricting our attention to *systematic* or *index* structures satisfying for some map (where denotes concatenation) we show similar lower bounds on the redundancy-query time tradeoff for the natural data structuring problems of Prefix Sum and Substring Search.

Boolean version of the problem of polynomial evaluation with preprocessing of coefficients, we show a lower bound on the redundancy–query time tradeoff of the form

*r*, we get an almost optimal lower bound stating that the query algorithm has to inspect almost the entire data structure (up to a logarithmic factor). We show similar lower bounds for problems satisfying a certain combinatorial properties of a coding theoretic flavor, and obtain (

*r*+1)

*t*≥

*Ω*(

*n*) for certain problems. Previously, no

*ω*(

*m*) lower bounds were known on

*t*in the general model for explicit Boolean problems, even for very small redundancies.

By restricting our attention to *systematic* or *index* structures satisfying (*x*)=*x*^{*}(*x*) for some map ^{*} (where denotes concatenation), we show similar lower bounds on the redundancy–query time tradeoff for the natural data structuring problems of Prefix Sum and Substring Search.

Originalsprog | Engelsk |
---|---|

Titel | Automata, Languages and Programming : 30th International Colloquium, ICALP 2003 Eindhoven, The Netherlands, June 30 - July 4, 2003 Proceedings |

Redaktører | Jos C.M. Baeten, Jan Karel Lenstra, Joachim Parrow, Gerhard J. Wöeginger |

Antal sider | 12 |

Forlag | Springer |

Publikationsdato | 2003 |

Sider | 442-453 |

ISBN (Trykt) | 9783540405436 |

ISBN (Elektronisk) | 3540405437 |

DOI | |

Status | Udgivet - 2003 |

Begivenhed | International Colloquium on Automata, Languages and Programming. ICALP 2003 - Eindhoven, Holland Varighed: 30 jun. 2003 → 4 jul. 2003 Konferencens nummer: 30 |

### Konference

Konference | International Colloquium on Automata, Languages and Programming. ICALP 2003 |
---|---|

Nummer | 30 |

Land/Område | Holland |

By | Eindhoven |

Periode | 30/06/2003 → 04/07/2003 |

Navn | Lecture Notes in Computer Science |
---|---|

Vol/bind | 2719 |

ISSN | 0302-9743 |