Feb'23: in my first paper at bioRxiv,
we develop a new framework for representing k-mer sets based on the shortest superstring problem
(another "theory meets practice" paper). UPDATE: accepted to RECOMB-seq, to appear in iScience.
Feb'23: update of the paper on streaming facility location (FOCS'22):
thanks to Arnold Filtser, our algorithmic framework gives a constant, that is O(1/ε), approximation in one pass,
albeit with space increased to nε.
We prove a tight lower bound for the space used by a deterministic comparison-based quantile summary,
which keeps track of all quantiles in a data stream (where items are linearly ordered), up to a small error.
The lower bound matches the worst-case performance of the Greenwald-Khanna algorithm, up to a constant factor,
and holds even for finding an approximate median in a data stream in the comparison-based model,
where an algorithm only compares items and is otherwise completely oblivious of the universe of items.
We designed a φ-competitive deterministic algorithm for bounded-delay packet scheduling.
In this problem, packets arrive online into a buffer, each with a deadline, a weight, and of length 1.
The goal is to schedule a packet in each time slot to maximize the total weight of scheduled packets.
Our algorithm is based on the plan which is the maximum-weight subset of pending packets that can be
scheduled starting from the current slot.
We proved PSPACE-hardness of online coloring in which vertices of a known
graph G arrives online and Painter colors them immediately without knowing to which
induced subgraph of G the colored vertices correspond.
Previously, PSPACE-hardness was known only in the variant in which some part of the graph is precolored
(which makes the hardness proof substantially easier).