Pith. sign in

REVIEW 2 cited by

Algorithms with Predictions

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2006.09123 v1 pith:O3LP7XZY submitted 2020-06-16 cs.DS

Michael Mitzenmacher , Sergei Vassilvitskii This is my paper · ORCID
classification cs.DS
keywords predictionsalgorithmswhenanalysisappliedbehaviorcasecircumvent
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

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 when these predictions are good, but recover the prediction-less worst case behavior when the predictions have large errors.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Primal-Dual Online Algorithms for the Parking Permit Problem

    cs.DS 2026-07 accept novelty 7.0 of 10

    The deterministic competitive ratio of the Parking Permit Problem is exactly K; the randomized ratio is at most ln K + ln ln K + O(1) and at least ln K + ln ln K + o(1).

  2. Learned LSM-trees: Two Approaches Using Learned Bloom Filters

    cs.DS 2025-07 reject novelty 4.0 of 10

    A classifier that skips Bloom filter probes can halve measured GET latency in an LSM-tree but introduces false negatives, while a learned Bloom filter cuts per-level memory 70-80% with zero false negatives in static tests.

Pith tools