Arrow Research search

Author name cluster

April Rasala

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers
2 author rows

Possible papers

9

STOC Conference 2002 Conference Paper

Approximating the smallest grammar: Kolmogorov complexity in natural models

  • Moses Charikar
  • Eric Lehman
  • Ding Liu
  • Rina Panigrahy
  • Manoj Prabhakaran 0001
  • April Rasala
  • Amit Sahai
  • Abhi Shelat

We consider the problem of finding the smallest context-free grammar that generates exactly one given string of length n . The size of this grammar is of theoretical interest as an efficiently computable variant of Kolmogorov complexity. The problem is of practical importance in areas such as data compression and pattern extraction.The smallest grammar is known to be hard to approximate to within a constant factor, and an o (log n /log log n ) approximation would require progress on a long-standing algebraic problem [10]. Previously, the best proved approximation ratio was O ( n 1/2 ) for the Bisection algorithm [8]. Our main result is an exponential improvement of this ratio; we give an O (log ( n/g * )) approximation algorithm, where g * is the size of the smallest grammar.We then consider other computable variants of Kolomogorov complexity. In particular we give an O (log 2 n ) approximation for the smallest non-deterministic finite automaton with advice that produces a given string. We also apply our techniques to "advice-grammars" and "edit-grammars", two other natural models of string complexity.

Details

TCS Journal 2002 Journal Article

On list update and work function algorithms

  • Eric J. Anderson
  • Kirsten Hildrum
  • Anna R. Karlin
  • April Rasala
  • Michael Saks

The list update problem, a well-studied problem in dynamic data structures, can be described abstractly as a metrical task system. In this paper, we prove that a generic metrical task system algorithm, called the work function algorithm, has constant competitive ratio for list update. In the process, we present a new formulation of the well-known “list factoring” technique in terms of a partial order on the elements of the list. This approach leads to a new simple proof that a large class of online algorithms, including Move-To-Front, is (2−1/k)-competitive, for k the list length.

Details DOI
v2026.09.13