### Abstract

The construction of perfect hash functions is a well-studied topic. In this paper, this concept is generalized with the following definition. We say that a family of functions from [n] to [k] is a δ-balanced (n, k)-family of perfect hash functions if for every S ⊆ [n], |S| = k, the number of functions that are 1-1 on S is between T/δ and ST for some constant T > 0. The standard definition of a family of perfect hash functions requires that there will be at least one function that is 1-1 on S, for each S of size k. In the new notion of balanced families, we require the number of 1-1 functions to be almost the same (taking δ to be close to 1) for every such S. Our main result is that for any constant δ > 1, a δ-balanced (n, k)-family of perfect hash functions of size 2^{O(k log log k)} log n can be constructed in time 2^{O(k log log k)} n log n. Using the technique of color-coding we can apply our explicit constructions to devise approximation algorithms for various counting problems in graphs. In particular, we exhibit a deterministic polynomial time algorithm for approximating both the number of simple paths of length k and the number of simple cycles of size k for any k ≤ O(log n/log log log n) in a graph with n vertices. The approximation is up to any fixed desirable relative error.

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

Title of host publication | Automata, Languages and Programming - 34th International Colloquium, ICALP 2007, Proceedings |

Publisher | Springer Verlag |

Pages | 435-446 |

Number of pages | 12 |

ISBN (Print) | 3540734198, 9783540734192 |

DOIs | |

State | Published - 2007 |

Event | 34th International Colloquium on Automata, Languages and Programming, ICALP 2007 - Wroclaw, Poland Duration: Jul 9 2007 → Jul 13 2007 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 4596 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 34th International Colloquium on Automata, Languages and Programming, ICALP 2007 |
---|---|

Country | Poland |

City | Wroclaw |

Period | 7/9/07 → 7/13/07 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

### Keywords

- Approximate counting of subgraphs
- Color-coding
- Perfect hashing

## Fingerprint Dive into the research topics of 'Balanced families of perfect hash functions and their applications'. Together they form a unique fingerprint.

## Cite this

*Automata, Languages and Programming - 34th International Colloquium, ICALP 2007, Proceedings*(pp. 435-446). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4596 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-73420-8_39