More Like this

1. Leibniz International Proceedings in Informatics (LIPIcs):50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

   https://doi.org/10.4230/LIPIcs.ICALP.2023.30  

   Braverman, Vladimir; Krauthgamer, Robert; Krishnan, Aditya; Sapir, Shay (January 2023, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Etessami, Kousha; Feige, Uriel; Puppis, Gabriele (Ed.)

   Many streaming algorithms provide only a high-probability relative approximation. These two relaxations, of allowing approximation and randomization, seem necessary - for many streaming problems, both relaxations must be employed simultaneously, to avoid an exponentially larger (and often trivial) space complexity. A common drawback of these randomized approximate algorithms is that independent executions on the same input have different outputs, that depend on their random coins. Pseudo-deterministic algorithms combat this issue, and for every input, they output with high probability the same "canonical" solution. We consider perhaps the most basic problem in data streams, of counting the number of items in a stream of length at most n. Morris’s counter [CACM, 1978] is a randomized approximation algorithm for this problem that uses O(log log n) bits of space, for every fixed approximation factor (greater than 1). Goldwasser, Grossman, Mohanty and Woodruff [ITCS 2020] asked whether pseudo-deterministic approximation algorithms can match this space complexity. Our main result answers their question negatively, and shows that such algorithms must use Ω(√{log n / log log n}) bits of space. Our approach is based on a problem that we call Shift Finding, and may be of independent interest. In this problem, one has query access to a shifted version of a known string F ∈ {0,1}^{3n}, which is guaranteed to start with n zeros and end with n ones, and the goal is to find the unknown shift using a small number of queries. We provide for this problem an algorithm that uses O(√n) queries. It remains open whether poly(log n) queries suffice; if true, then our techniques immediately imply a nearly-tight Ω(log n/log log n) space bound for pseudo-deterministic approximate counting. 

   more » « less
2. Automata Learning from Preference and Equivalence Queries

   https://doi.org/10.1007/978-3-031-98685-7_5  

   Hsiung, Eric; Biswas, Joydeep; Chaudhuri, Swarat (January 2025, Springer Nature Switzerland)

   Abstract Active automata learning from membership and equivalence queries is a foundational problem with numerous applications. We propose a novel variant of the active automata learning problem: actively learn finite automata usingpreference queries—i.e., queries about the relative position of two sequences in a total preorder—instead of membership queries. Our solution isRemap, a novel algorithm which leverages a symbolic observation table along with unification and constraint solving to navigate a space of symbolic hypotheses (each representing a set of automata), and uses satisfiability-solving to construct a concrete automaton (specifically a Moore machine) from a symbolic hypothesis.Remapis guaranteed to correctly infer the minimal automaton with polynomial query complexity under exact equivalence queries, and achieves PAC–identification ($$\varepsilon $$ $\epsilon$ -approximate, with high probability) of the minimal automaton using sampling-based equivalence queries. Our empirical evaluations ofRemapon the task of learning reward machines for two reinforcement learning domains indicateRemapscales to large automata and is effective at learning correct automata from consistent teachers, under both exact and sampling-based equivalence queries. 

   more » « less
3. Streaming Periodicity with Mismatches

   Ergun, F; Grigorescu, E.; Sadeqi Azer, E.; Zhou, S. (August 2017, RANDOM)

   We study the problem of finding all $$k$$-periods of a length-$$n$$ string $$S$$, presented as a data stream. $$S$$ is said to have $$k$$-period $$p$$ if its prefix of length $n-p$ differs from its suffix of length $n-p$ in at most $$k$$ locations. We give a one-pass streaming algorithm that computes the $$k$$-periods of a string $$S$$ using $$\poly(k, \log n)$$ bits of space, for $$k$$-periods of length at most $$\frac{n}{2}$$. We also present a two-pass streaming algorithm that computes $$k$$-periods of $$S$$ using $$\poly(k, \log n)$$ bits of space, regardless of period length. We complement these results with comparable lower bounds. 

   more » « less
4. Random Linear Streaming Codes in the Finite Memory Length and Decoding Deadline Regime

   https://doi.org/10.1109/ISIT45174.2021.9518162  

   Su, Pin-Wen; Huang, Yu-Chih; Lin, Shih-Chun; Wang, I-Hsiang; Wang, Chih-Chun (July 2021, 2021 IEEE International Symposium on Information Theory (ISIT))

   Streaming codes take a string of source symbols as input and output a string of coded symbols in real time, which effectively eliminate the queueing delay and are regarded as a promising scheme for low latency communications. Aiming at quantifying the fundamental latency performance of random linear streaming codes (RLSCs) over i.i.d. symbol erasure channels, this work derives the exact error probability under, simultaneously, the finite memory length and finite decoding deadline constraints. The result is then used to examine the tradeoff among memory length (complexity), decoding deadline (delay), and error probability (reliability) of RLSCs for the first time in the literature. Two critical observations are made: (i) Too much memory can adversely impact the performance under a finite decoding deadline constraint, a surprising finding not captured by the traditional wisdom that large memory length monotonically improves the performance in the asymptotic regime; (ii) The end-to-end delay of the RLSC is roughly 50% of that of the MDS block code when under identical code rate and error probability requirements. This implies that switching from block codes to RLSCs not only eliminates the queueing delay (thus 50%) but also has little negative impact on the error probability. 

   more » « less
5. Representation Obliviousness and Pseudodeterminism in Streaming Algorithms

   https://doi.org/10.1145/3767718  

   Chen, Michael; Chakraborty, Sourav; Pavan, A; Vinodchandran, N V (November 2025, Proceedings of the ACM on Management of Data)

   In this work, we study the notion ofrepresentation obliviousnessin the context of pseudodeterministic streaming algorithms. A (randomized) streaming algorithm A is pseudodeterministic, if for every stream D, there is a ''canonical value'' g(D) so that with probability at least 2/3, A on input stream D outputs g(D). Intuitively, a randomized algorithm is representation oblivious if the output distribution of the algorithm does not depend on the representation of the input. We investigate this notion in the context of streaming algorithms, more specifically, distinct elements estimation (F₀estimation) in data streams. In this context, representation obliviousness captures the idea that the output distribution of an algorithm for estimating F₀should only depend on the set of distinct elements of the stream. This is a natural notion, as we note that standard streaming algorithms are representation-oblivious in this sense. We prove that any representation oblivious pseudodeterministic streaming algorithm for estimating F₀must use Ω(n) space, where [n] is the universe. More generally, we prove that any representation oblivious pseudodeterministic t(n)-pass streaming algorithm requires Ω(n/t(n)) space. This lower bound matches the space requirement of the straightforward multi-pass deterministic algorithm that exactly computes F₀. 

   more » « less