Jun '22: An 8-page summary of Relative Error Streaming Quantiles paper published in SIGMOD Record as a research highlight, together with a nice 1-page technical perspective by Rasmus Pagh.
The summary describes a slight variation of the algorithm, compared to the conference version.
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).