Working with Sliding-Window Algorithms part1(Computer Science)
- Pseudorandom Generators for Sliding-Window Algorithms(arXiv)
Author : Augusto Modanese
Abstract : A sliding-window algorithm of window size t is an algorithm whose current operation depends solely on the last tsymbols read. We construct pseudorandom generators (PRGs) for low-space randomized sliding-window algorithms that have access to a binary randomness source. More specifically, we lift these algorithms to the non-uniform setting of branching programs and study them as a subclass thereof that we call sliding-window branching programs (SWBPs), accordingly. For general SWBPs, given a base PRG Gbase with seed length dbase that εbase-fools width-w, length-t (general) branching programs, we give two PRG constructions for fooling any same-width SWBP of length n and window size t (where we assume w≥n). The first uses an additional dbase+O(log(n/t)log(1/εbase)) random bits, whereas the second has a seed length of O((dbase+loglog(n/t)+log(1/εbase))log(dbase+log(1/εbase))). Both PRGs incur only a (n/2t)O(1) multiplicative loss in the error parameter. As an application, we show how to decide the language of a sublinear-time probabilistic cellular automaton using small space. More specifically, these results target the model of PACAs, which are probabilistic cellular automata that accept if and only if all cells are simultaneously accepting. For (sublinear) T(n)=Ω(logn)1.01, we prove that every language accepted by a T-time one-sided error PACA (the PACA equivalent of RP) can be decided using only O(T)space. Meanwhile, forgoing the previous requirement on T, we show the same holds for T-time two-sided error PACA (the PACA equivalent of BPP) if we use O~(T)+O(logn) space instead (where the O~ notation hides only polylog(T) factors).
2.Low-Latency Sliding Window Algorithms for Formal Languages (arXiv)
Author : Moses Ganardi, Louis Jachiet, Markus Lohrey, Thomas Schwentick
Abstract : Low-latency sliding window algorithms for regular and context-free languages are studied, where latency refers to the worst-case time spent for a single window update or query. For every regular language L it is shown that there exists a constant-latency solution that supports adding and removing symbols independently on both ends of the window (the so-called two-way variable-size model). We prove that this result extends to all visibly pushdown languages. For deterministic 1-counter languages we present a O(logn) latency sliding window algorithm for the two-way variable-size model where n refers to the window size. We complement these results with a conditional lower bound: there exists a fixed real-time deterministic context-free language L such that, assuming the OMV (online matrix vector multiplication) conjecture, there is no sliding window algorithm for L with latency n1/2−ε for any ε>0, even in the most restricted sliding window model (one-way fixed-size model). The above mentioned results all refer to the unit-cost RAM model with logarithmic word size. For regular languages we also present a refined picture using word sizes O(1), O(loglogn), and O(logn)
