Home

Krzysztof Onak

  1. An Efficient Partitioning Oracle for Bounded-Treewidth Graphs.

    Fri, 06/24/2011 - 15:01 — SomNambul
    Authors: Krzysztof Onak, Avinatan Hassidim, Alan Edelman, Huy N. Nguyen
    Subjects: Data Structures and Algorithms
    Abstract

    Partitioning oracles were introduced by Hassidim et al. (FOCS 2009) as a
    generic tool for constant-time algorithms. For any epsilon > 0, a partitioning
    oracle provides query access to a fixed partition of the input bounded-degree
    minor-free graph, in which every component has size poly(1/epsilon), and the
    number of edges removed is at most epsilon*n, where n is the number of vertices
    in the graph.

  2. Streaming Algorithms from Precision Sampling.

    Mon, 11/08/2010 - 16:01 — SomNambul
    Authors: Krzysztof Onak, Alexandr Andoni, Robert Krauthgamer
    Subjects: Data Structures and Algorithms
    Abstract

    In STOC'05, Indyk and Woodruff introduced a new technique that yielded a
    near-optimal space algorithm for $F_k$ moment estimation problem. Since then,
    the technique has inspired a number of advances in streaming algorithmics. We
    show that at least several of these results follow easily from the application
    of a single probabilistic technique, called Precision Sampling. Using it, we
    obtain simple streaming algorithms that maintain a randomized sketch of an
    input vector $x=(x_1,...,x_n)$, useful for the following applications:
    Estimating the $F_k$ moment of $x$, for $k>2$.

  3. Testing Distribution Identity Efficiently.

    Tue, 10/20/2009 - 12:53 — SomNambul
    Authors: Krzysztof Onak
    Subjects: Data Structures and Algorithms
    Abstract

    We consider the problem of testing distribution identity. Given a sequence of
    independent samples from an unknown distribution on a domain of size n, the
    goal is to check if the unknown distribution approximately equals a known
    distribution on the same domain. While Batu, Fortnow, Fischer, Kumar,
    Rubinfeld, and White (FOCS 2001) proved that the sample complexity of the
    problem is O~(sqrt(n) * poly(1/epsilon)), the running time of their tester is
    much higher: O(n) + O~(sqrt(n) * poly(1/epsilon)). We modify their tester to
    achieve a running time of O~(sqrt(n) * poly(1/epsilon)).

Math-arch

Syndicate content