Derandomization for sliding window algorithms with strict correctness

DOI10.1007/s00224-020-10000-1OpenAlexW4247886945MaRDI QIDQ5918353

Moses Ganardi, Markus Lohrey, Danny Hucke

Publication date: 3 August 2021

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-020-10000-1

zbMATH Keywords

randomized algorithmsstreaming algorithmssliding window algorithms

Mathematics Subject Classification ID

Theory of data (68Pxx) Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Streaming algorithms for language recognition problems
• Optimal sampling from sliding windows
• On randomized one-round communication complexity
• The space complexity of approximating the frequency moments
• Sliding window algorithms for regular languages
• Succinct summing over sliding windows
• Data streams. Models and algorithms.
• Dynamic Graphs in the Sliding-Window Model
• Edit Distance to Monotonicity in Sliding Windows
• Querying Regular Languages over Sliding Windows
• Maintaining Stream Statistics over Sliding Windows
• Communication Complexity
• Probabilistic automata
• Derandomization for sliding window algorithms with strict correctness