250 citations · 1.1k across the 76 of their papers we have counts for
7 papers · 1 filter
Erdös-Szekeres Partitioning Problem
Michael Mitzenmacher, Saeed Seddighin
In this note, we present a substantial improvement on the computational complexity of the Erdös-Szekeres partitioning problem and review recent works on dynamic \textsf{LIS}.
PINT: Probabilistic In-band Network Telemetry
Ran Ben Basat, Sivaramakrishnan Ramanathan, Yuliang Li +3
Commodity network devices support adding in-band telemetry measurements into data packets, enabling a wide range of applications, including network troubleshooting, congestion cont…
Queues with Small Advice
Michael Mitzenmacher
Motivated by recent work on scheduling with predicted job sizes, we consider the performance of scheduling algorithms with minimal advice, namely a single bit. Besides demonstratin…
Algorithms with Predictions
Michael Mitzenmacher, Sergei Vassilvitskii
We introduce algorithms that use predictions from machine learning applied to the input to circumvent worst-case analysis. We aim for algorithms that have near optimal performance…
Partitioned Learned Bloom Filter
Kapil Vaidya, Eric Knorr, Tim Kraska +1
Bloom filters are space-efficient probabilistic data structures that are used to test whether an element is a member of a set, and may return false positives. Recently, variations…
Faster and More Accurate Measurement through Additive-Error Counters
Ran Ben Basat, Gil Einziger, Michael Mitzenmacher +1
Counters are a fundamental building block for networking applications such as load balancing, traffic engineering, and intrusion detection, which require estimating flow sizes and…