Showing 2025Show all
2 papers · 1 filter
cs.LO2025
FO-Query Enumeration over SLP-Compressed Structures of Bounded Degree
Markus Lohrey, Sebastian Maneth, Markus L. Schmid
Enumerating the result set of a first-order query over a relational structure of bounded degree can be done with linear preprocessing and constant delay. In this work, we extend th…
cs.DS2025
Streaming algorithms for products of probabilities
Markus Lohrey, Leon Rische, Louisa Seelbach Benkner +1
We consider streaming algorithms for approximating a product of input probabilities up to multiplicative error of . It is shown that every randomized streaming algorithm for t…