Browse/search for people

Publication - Dr Raphael Clifford

    Approximate Hamming distance in a stream

    Citation

    Clifford, R & Starikovskaia, T, 2016, ‘Approximate Hamming distance in a stream’. in: Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, Davide Sangiorgi (eds) 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, pp. 20:1-20:14

    Abstract

    We consider the problem of computing a (1+ε)-approximation of the
    Hamming distance between a pattern of length n and successive substrings
    of a stream. We first look at the one-way randomised communication
    complexity of this problem, giving Alice the first half of the stream and
    Bob the second half. We show the following:
    - If Alice and Bob both share the pattern then there is an O-4 log2n) bit randomised one-way communication protocol.
    - If only Alice has the pattern then there is an O-2log n) bit randomised one-way communication protocol.

    We then go on to develop small space streaming algorithms for (1 + ε)- approximate Hamming distance which give worst case running time guarantees per arriving symbol.
    - For binary input alphabets there is an O-3√ n log2 n) space and O-2 log n) time streaming (1+ε)-approximate Hamming distance algorithm.
    - For general input alphabets there is an O-5√ n log4 n) space and O-4 log3 n) time streaming (1+ε)-approximate Hamming distance algorithm.

    Full details in the University publications repository