Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Succinct Description:
TR95-022 | 2nd May 1995
Marek Karpinski, Wojciech Rytter, Ayumi Shinohara

Pattern-Matching for Strings with Short Descriptions

We consider strings which are succinctly described. The description
is in terms of straight-line programs in which the constants are
symbols and the only operation is the concatenation. Such
descriptions correspond to the systems of recurrences or to
context-free grammars generating single words. The descriptive ... more >>>

TR06-002 | 4th January 2006
Eyal Kaplan, Moni Naor, Omer Reingold

Derandomized Constructions of k-Wise (Almost) Independent Permutations

Constructions of k-wise almost independent permutations have been receiving a growing amount of attention in recent years. However, unlike the case of k-wise independent functions, the size of previously constructed families of such permutations is far from optimal.

In this paper we describe a method for reducing the size of ... more >>>

ISSN 1433-8092 | Imprint