Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

Binary Search with Distributional Predictions

T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A predicted distribution, not a single point, can drive binary search to the query-optimal tradeoff $O(H(p)+\log\eta)$.

desk verdict The main upper bound is false — the endpoint argument gives √η, not log η — but the model and the lower bound are worth a serious look. read the letter →

arxiv 2411.16030 v1 pith:7ZKH2IUJ submitted 2024-11-25 cs.LG cs.DS

Michael Dinitz , Sungjin Im , Thomas Lavastida , Benjamin Moseley , Aidin Niaparast , Sergei Vassilvitskii This is my paper · ORCID
classification cs.LGcs.DS
keywords distributionalpredictionsbinarysearchearthmover'sdistanceentropyalgorithmswithoptimaltreequerycomplexitylowerbound
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks what binary search can do when the prediction it receives is not a single array position but a whole distribution over positions, as modern machine-learning systems naturally output. It tries to establish that the right performance target is $O(H(p)+\log\eta)$: the entropy of the true query distribution plus the logarithm of the earth mover's distance between the true and predicted distributions. A reduction to any single point prediction is shown to fail on simple two-atom distributions, so the full distribution must be used. The paper gives an interleaved algorithm that alternates phases of median-of-predicted-distribution bisection with binary search at the endpoints of the remaining range, and proves this bound. It also proves a matching lower bound, showing the tradeoff between entropy and earth-mover error is optimal up to constants.

What carries the argument

The load-bearing object is an interleaving of two classical search routines, executed in iterations $i=0,1,2,\dots$. In the Bisection phase the algorithm spends $2^i$ comparisons probing the median of the predicted distribution restricted to the current range, halving the predicted mass each time; in the Endpoint-Binary-Search phase it probes distance $d=2^{2i}$ inward from both ends and, if the target is there, finishes with ordinary binary search on that small block. The proof's key accounting step is the observation that a key not found by iteration $k$ has left a predicted mass below $p_i/2$ inside the range, so the true distribution must transport at least $p_i/2$ mass across the distance $D_i$ from the key to the range boundary; summing these distances lower-bounds the earth mover's distance $\eta$. Concavity of $\log$ then converts the per-key distance sum into the $\log\eta$ term, while early-found keys are bounded by $p_i\log(1/p_i)$ and hence by $H(p)$.

What would settle it

Look at the lower-bound construction: keys $1,\dots,n$, true distribution a singleton at position $i$, predicted distribution uniform on $\{1,\dots,\eta\}$. If any comparison-based algorithm were found whose expected number of comparisons on this family is $o(\log\eta)$ for arbitrarily large $\eta$, the claimed $\Omega(\log\eta)$ bound would be false. On the upper-bound side, running the proposed algorithm on $n$ keys with $p=\hat p$ uniform should give expected queries at most $4\log n+O(1)$; measured query counts growing like $c\log n$ with $c$ clearly above $4$ would indicate the analysis is off.

Watch

Extended reading notes

Core claim

On its own terms, the central discovery is that a predicted distribution can be exploited nearly as well as the true distribution, with graceful degradation as the prediction drifts. If the target key is drawn from $p$ and the algorithm is handed $\hat p$, the interleaved algorithm has expected query complexity at most $4H(p)+8\max(\log(\eta)+2,1)+8$, where $\eta$ is the earth mover's distance between $p$ and $\hat p$; this is $O(H(p)+\log\eta)$. The analysis splits keys: those found after at most $\log\log(4/p_i)$ iterations are charged to the entropy term, while keys that survive longer force at least $p_i/2$ probability mass to be moved across a distance $D_i$, so their cost is charged to $\eta$ through Jensen's inequality. The matching lower bound uses an instance family in which the true distribution is a singleton at one of $\eta$ positions and the prediction is uniform over those $\eta$ positions; any comparison-based algorithm must pay $\Omega(\log\eta)$ there, and combining this with the classical $\Omega(H(p))$ lower bound for known distributions proves the tradeoff tight.

Load-bearing premise

The paper's optimality claim inherits the classical lower bound that a search strategy for a known distribution needs $\Omega(H(p))$ comparisons; if that outside theorem, or its application to algorithms that are also given the predicted distribution, turned out to be false, the matching lower bound would not follow.

Editorial extensions

If this is right

  • If the bound is right, no comparison-based search algorithm can make asymptotically better use of a distributional prediction: the $O(H(p)+\log\eta)$ tradeoff is optimal up to constant factors.
  • A possibly wrong predicted distribution can be turned into a binary search tree whose expected lookup time under the true distribution is $O(H(p)+\log\eta)$; this is described as the first optimal-BST result that tolerates a wrong input distribution.
  • Point-prediction reductions are ruled out: on a two-atom distribution with zero earth-mover error and entropy $1$, every choice of a single predicted location forces $\Omega(\log n)$ expected comparisons, so the distribution itself is necessary.
  • With $m$ predicted distributions the algorithm remains competitive with the best one, at an extra $O(\log m)$ factor: $O(\log m\,(H(p)+\min_k\log\eta_k))$.
  • In the paper's experiments on temporal network data, the learned search tree cuts comparison counts by 20-25% versus baselines on two datasets and degrades smoothly as $\log\eta$ grows.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural editorial extension: any search structure that can be tuned to a distribution could use the same interleave-and-charge-to-EMD pattern, replacing the endpoint binary search with whatever worst-case fallback exists; the entropy-plus-transport-distance form may be a template for other algorithms with distributional predictions.
  • The lower-bound construction suggests the $\log\eta$ term is driven by long-range mass movement; if real predictors make only local errors, restricting the earth mover's distance to a bounded neighborhood might give better constants or a refined bound.
  • The algorithm's constants and the doubling schedule $d=2^{2i}$ are analysis artifacts rather than necessary design choices; the experiments already push $d$ to $2^{8\cdot 2^i}$, so a data-dependent schedule could reduce practical overhead while preserving the asymptotic guarantee.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper introduces a model of binary search with distributional predictions, in which the algorithm receives a predicted distribution over key locations rather than a single point prediction, and the prediction error is measured by the earth mover's distance eta between the predicted and true distributions. The main claimed result (Theorem 1) is an algorithm that interleaves a distribution-median bisection phase with endpoint binary search and has expected query complexity O(H(p)+log eta), where H(p) is the entropy of the true distribution. The paper complements this with a lower bound Omega(H(p)+log eta) (Corollary 3), an extension to portfolios of predictions (Theorem 4), and synthetic and real-data experiments.

Significance. The modeling contribution is attractive: distributional predictions are a natural generalization of point predictions, and the earth mover's distance is a well-motivated measure of prediction error in this geometric setting. The lower-bound component, based on Yao's principle and Mehlhorn's entropy lower bound, is coherent, and the experiments address a real data setup. However, the main upper bound is not established: the proof of Theorem 1 contains a concrete inequality error, and the proposed algorithm in fact fails the claimed guarantee on a simple instance. Since the advertised optimal tradeoff rests on this upper bound, the paper's central claim is unsupported as submitted.

major comments (3)
  1. [Section 3.1, proof of Theorem 1] The step 'Since a_i is not found before iteration k_i, we conclude that 2^{2k_i-1} < D_i, which means that 2^{k_i} <= 2 log(D_i)' is incorrect in two ways. The endpoint phase at iteration k_i-1 probes at distance d=2^{2(k_i-1)}=2^{2k_i-2}, so the correct inference is D_i > 2^{2k_i-2}; moreover, even from D_i > 2^{2k_i-2} one obtains 2^{k_i} = O(sqrt(D_i)), not O(log D_i). The subsequent Jensen step therefore bounds the I_2 cost by O(sqrt(eta)) rather than O(log eta), so the proof does not establish Theorem 1.
  2. [Section 3, Theorem 1] The described algorithm fails the claimed bound on a concrete instance. Let n=4^m, let the predicted distribution be the geometric distribution p_hat_j proportional to 2^{-j} over [n], and let the true distribution be a point mass at i=n/2. Then H(p)=0 and eta=Theta(n), so Theorem 1 promises O(log n) queries. However, in every bisection step the median of the remaining geometric mass is the leftmost remaining index, so iteration t advances the left boundary by only 2^t bisection steps, while the endpoint phase removes 2^{2t} positions from each side; the target is reached only after K approximately log_4 n iterations, and the cost is dominated by the sum over t<=K of 2^t, which is Theta(2^K)=Theta(sqrt(n)). Thus Theorem 1 is false as stated for the proposed algorithm.
  3. [Appendix A, proof of Theorem 4] The portfolio analysis inherits the same invalid inference. Equations (1)-(5) use the relation 2^{T_i} <= 2 log(D_i), which fails by the same argument as in the proof of Theorem 1; hence Theorem 4 is not supported either. Because Corollary 3's optimality claim depends on the unproven upper bound, the claimed tight tradeoff is not established, although the Omega(log eta) component via Yao's principle and the cited lower bound appears sound.
minor comments (5)
  1. [Section 5.2] Figures 3 and 4 show only mean values for the real-data experiments; no error bars or other variance measures are reported, so statements such as '20-25% comparisons on average' lack a significance assessment.
  2. [Section 5] The experiments replace the analyzed parameter d=min(2^{2i}, r-l) with d=min(2^{8*2^i}, r-l), so the implemented variant is not the algorithm analyzed in Section 3; the later claim that the results 'validate the theory' is therefore overstated.
  3. [Section 5.1] The word 'erorr' should be 'error'.
  4. [Section 3.1] The entropy notation should state the standard convention that 0 log 0 = 0 for zero-probability keys.
  5. [Theorem 2] The quantification 'For any eta in [n]' should be stated more precisely as 'for every integer eta with 1 <= eta <= n'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the main bound is a genuine function of H(p) and the EMD between p and the predicted distribution, with no fitted input renamed as a prediction and no load-bearing self-citation chain.

full rationale

The paper's central result, Theorem 1, bounds expected query complexity as O(H(p) + log(eta)) where H(p) is the entropy of the true distribution and eta is the earth mover's distance between the true distribution p and the predicted distribution hat(p). Neither H(p) nor eta is fitted from the algorithm's own performance; both are defined by the input distributions before the algorithm runs. The algorithm's bisection phase uses the predicted median from hat(p), and the endpoint phase uses a fixed schedule d = 2^{2i} that does not depend on p or hat(p). The proof charges bisection costs to the entropy of the true distribution and endpoint costs to the transportation distance eta; this is a direct analytic bound, not a restatement of the algorithm's definition. The reduction-to-point-predictions lower bound in Section 2.1 is an impossibility argument against a natural class of algorithms, not a circular derivation of the main theorem. The lower bound in Theorem 2 invokes Mehlhorn's external entropy lower bound [27] and Yao's principle; this is an external, independently established result, not a self-citation, and it is not used to define the algorithm's performance. Corollary 3 simply combines two external lower bounds, [27] and the new Theorem 2, with no circular dependence on the upper bound. The experiments choose empirical parameters such as a widened d and lambda = 0.5 for a baseline, but these choices are explicitly implementation details and do not feed back into the theoretical claims. The skeptic's objection that Theorem 1's proof may contain an erroneous step is a correctness concern, not a circularity concern: a false or unproven bound is not the same as a bound that is equivalent to its inputs by construction. No circular step was found; the derivation chain is self-contained given the stated external entropy lower bound.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The algorithm itself has no fitted constants; the theoretical guarantees are parameter-free with explicit constants. The analysis relies on standard background: Mehlhorn's entropy bounds for known-distribution search, the optimal-transport definition of EMD, Jensen's inequality, and Yao's principle. No new unverified entities are introduced. Experimental constants (lambda=0.5, the d multiplier) are not part of the central claim.

assumptions (4)
  • domain assumption Mehlhorn's entropy bounds for known-distribution comparison-based search: expected cost at least Omega(H(p)) and bisection achieves H(p)+O(1)
    Invoked in Section 1.1 for the H(p) term and in Theorem 2/Corollary 3 via the uniform distribution over [eta]. The paper cites [27] without re-deriving these bounds.
  • domain assumption Any comparison-based search strategy can be represented as a binary search tree, so the distributional-prediction search result applies to optimal BST construction
    Used in Section 1.1 to frame the result as distributionally-robust optimal BSTs. The paper states the equivalence without proof.
  • standard math The earth mover's distance is defined by optimal transport and satisfies the monotonicity and Jensen inequalities used in the proof of Theorem 1
    Used in Section 2 and Section 3.1 when lower-bounding eta by sum_i p_i D_i / 2 and applying Jensen's inequality.
  • standard math Yao's minimax principle for converting randomized lower bounds to deterministic ones
    Used in the proof of Theorem 2 to show a deterministic lower bound from a distribution over instances.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Binary Search with Distributional Predictions." pith.science (2026). https://pith.science/paper/7ZKH2IUJ

@misc{pith2026241116030,
  author       = {Pith},
  title        = {Pith review of: Binary Search with Distributional Predictions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7ZKH2IUJ}},
  note         = {Machine review of arXiv:2411.16030}
}
abstract

Algorithms with (machine-learned) predictions is a powerful framework for combining traditional worst-case algorithms with modern machine learning. However, the vast majority of work in this space assumes that the prediction itself is non-probabilistic, even if it is generated by some stochastic process (such as a machine learning system). This is a poor fit for modern ML, particularly modern neural networks, which naturally generate a distribution. We initiate the study of algorithms with distributional predictions, where the prediction itself is a distribution. We focus on one of the simplest yet fundamental settings: binary search (or searching a sorted array). This setting has one of the simplest algorithms with a point prediction, but what happens if the prediction is a distribution? We show that this is a richer setting: there are simple distributions where using the classical prediction-based algorithm with any single prediction does poorly. Motivated by this, as our main result, we give an algorithm with query complexity $O(H(p) + \log \eta)$, where $H(p)$ is the entropy of the true distribution $p$ and $\eta$ is the earth mover's distance between $p$ and the predicted distribution $\hat p$. This also yields the first distributionally-robust algorithm for the classical problem of computing an optimal binary search tree given a distribution over target keys. We complement this with a lower bound showing that this query complexity is essentially optimal (up to constants), and experiments validating the practical usefulness of our algorithm.

Figures

Figures reproduced from arXiv: 2411.16030 by the authors.

Figure 1
Figure 1. Results for synthetic data experiments. The y-axis measures the average cost (query [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
Figure 2
Figure 2. The train and test distributions when t = 50 for the three datasets. 10 20 30 40 50 Percentage of Training Data 6 7 8 9 10 11 Average Cost Classic Bisection Learned BST Convex Combination (a) AskUbuntu 10 20 30 40 50 Percentage of Training Data 8.5 9.0 9.5 10.0 10.5 11.0 11.5 12.0 12.5 Average Cost Classic Bisection Learned BST Convex Combination (b) SuperUser 10 20 30 40 50 Percentage of Training Data 9.5 10.0 10.5… view at source ↗
Figure 3
Figure 3. Results for real data experiments. The y-axis measures the average cost of each algorithm [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Results for real data experiments. The y-axis measures the average cost of each algorithm [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

  1. Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search

    cs.DS 2025-02 accept novelty 8.0 of 10

    The paper constructs a deterministic one-max-search algorithm that simultaneously achieves the best possible consistency-robustness trade-off and the best possible smoothness for prediction errors, for both multiplica...

Reference graph

Works this paper leans on

32 extracted references · 22 canonical work pages · cited by 1 Pith paper

  1. [1]

    Learning- augmented mechanism design: Leveraging predictions for facility location

    Priyank Agrawal, Eric Balkanski, Vasilis Gkatzelis, Tingting Ou, and Xizhi Tan. Learning- augmented mechanism design: Leveraging predictions for facility location. InProceedings of the 23rd ACM Conference on Economics and Computation, pages 497–528, 2022

    2022

  2. [2]

    Two-stage stochastic integer programming: A brief introduction

    Shabbir Ahmed. Two-stage stochastic integer programming: A brief introduction. Wiley encyclopedia of operations research and management science, pages 1–10, 2010

    work page 2010

  3. [3]

    Private algorithms with private predictions

    Kareem Amin, Travis Dick, Mikhail Khodak, and Sergei Vassilvitskii. Private algorithms with private predictions. CoRR, abs/2210.11222, 2022. doi: 10.48550/ARXIV.2210.11222. URL https://doi.org/10.48550/arXiv.2210.11222

    arXiv doi:10.48550/arxiv.2210.11222 2022

  4. [4]

    Online algorithms with multiple predictions

    Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi. Online algorithms with multiple predictions. InProceedings of the 39th International Conference on Machine Learning, ICML 2022, 2022

    work page 2022

  5. [5]

    Contract scheduling with distributional and multiple advice

    Spyros Angelopoulos, Marcin Bienkowski, Christoph Dürr, and Bertrand Simon. Contract scheduling with distributional and multiple advice. In Kate Larson, editor,Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, IJCAI-24, pages 3652–3660. International Joint Conferences on Artificial Intelligence Organization, 8 2024...

    work page doi:10.24963/ijcai.2024/404 2024

  6. [6]

    Generalization in portfolio- based algorithm selection

    Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Generalization in portfolio- based algorithm selection. InThirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 20...

    work page 2021

  7. [7]

    The primal-dual method for learning augmented algorithms

    Étienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning augmented algorithms. In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria- Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, Decembe...

    work page 2020

  8. [8]

    On the power of robust solutions in two-stage stochastic and adaptive optimization problems.Mathematics of Operations Research, 35(2):284–305, 2010

    Dimitris Bertsimas and Vineet Goyal. On the power of robust solutions in two-stage stochastic and adaptive optimization problems.Mathematics of Operations Research, 35(2):284–305, 2010

    work page 2010

Show all 32 references
  1. [9]

    Two-stage sample robust optimization

    Dimitris Bertsimas, Shimrit Shtern, and Bradley Sturt. Two-stage sample robust optimization. Operations Research, 70(1):624–640, 2022

    2022

  2. [10]

    Beyond IID: data-driven decision-making in heterogeneous environments

    Omar Besbes, Will Ma, and Omar Mouchtaki. Beyond IID: data-driven decision-making in heterogeneous environments. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors,Advances in Neural Information Processing Systems 35: Annual Conference on Ne...

    2022

  3. [11]

    Predictive flows for faster ford-fulkerson

    Sami Davies, Benjamin Moseley, Sergei Vassilvitskii, and Yuyan Wang. Predictive flows for faster ford-fulkerson. In International Conference on Machine Learning, pages 7231–7248. PMLR, 2023

    2023

  4. [12]

    Learning online algorithms with distributional advice

    Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Ali Vakilian, and Nikos Zarifis. Learning online algorithms with distributional advice. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 ofProceeding...

    2021

  5. [13]

    Faster matchings via learned duals

    Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassil- vitskii. Faster matchings via learned duals. In Marc’Aurelio Ranzato, Alina Beygelz- imer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Ad- vances in Neural Information P...

    2021

  6. [14]

    Algorithms with prediction portfolios

    Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Algorithms with prediction portfolios. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors,Advances in Neural Information Processing Systems 35: Annual ...

    2022

  7. [15]

    Posted pricing and prophet inequalities with inaccurate priors

    Paul Dütting and Thomas Kesselheim. Posted pricing and prophet inequalities with inaccurate priors. In Anna R. Karlin, Nicole Immorlica, and Ramesh Johari, editors,Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019,...

    2019

  8. [16]

    Online knapsack with frequency predictions

    Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Online knapsack with frequency predictions. In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors,Advances in Neural Information Processing Systems 34: ...

    2021

  9. [17]

    Online covering with multiple experts

    Eniko Kevi and Kim Thang Nguyen. Online covering with multiple experts. CoRR, abs/2312.14564, 2023. doi: 10.48550/ARXIV.2312.14564. URLhttps://doi.org/10.48550/ arXiv.2312.14564

    2023 doi arXiv

  10. [18]

    A guide to sample average approximation

    Sujin Kim, Raghu Pasupathy, and Shane G Henderson. A guide to sample average approximation. Handbook of simulation optimization, pages 207–243, 2015

    2015

  11. [19]

    Donald E. Knuth. Optimum binary search trees. Acta Informatica, 1:14–25, 1971. doi: 10.1007/BF00264289. URL https://doi.org/10.1007/BF00264289

    1971 doi

  12. [20]

    The case for learned index structures

    Tim Kraska, Alex Beutel, Ed H Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. InProceedings of the 2018 International Conference on Management of Data, pages 489–504. ACM, 2018

    2018

  13. [21]

    Online scheduling via learned weights

    Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online scheduling via learned weights. In Shuchi Chawla, editor,Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1859–1...

    2020 doi

  14. [22]

    Learning augmented binary search trees

    Honghao Lin, Tian Luo, and David Woodruff. Learning augmented binary search trees. In International Conference on Machine Learning, pages 13431–13440. PMLR, 2022

    2022

  15. [23]

    Algorithms with predictions

    Alexander Lindermayr and Nicole Megow. Algorithms with predictions. https:// algorithms-with-predictions.github.io/, 2022

    2022

  16. [24]

    Competitive caching with machine learned advice

    Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM (JACM), 68(4):1–25, 2021

    2021

  17. [25]

    Online list labeling with predictions

    Samuel McCauley, Ben Moseley, Aidin Niaparast, and Shikha Singh. Online list labeling with predictions. Advances in Neural Information Processing Systems, 36, 2024

    2024

  18. [26]

    Incremental topo- logical ordering and cycle detection with predictions

    Samuel Mccauley, Benjamin Moseley, Aidin Niaparast, and Shikha Singh. Incremental topo- logical ordering and cycle detection with predictions. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, ed- itor...

    2024

  19. [27]

    Nearly optimal binary search trees.Acta Informatica, 5:287–295, 1975

    Kurt Mehlhorn. Nearly optimal binary search trees.Acta Informatica, 5:287–295, 1975

    1975

  20. [28]

    Cambridge University Press, 2021

    Michael Mitzenmacher and Sergei Vassilvitskii.Algorithms with Predictions, page 646–662. Cambridge University Press, 2021. doi: 10.1017/9781108637435.037. 14

    2021 doi

  21. [29]

    Motifs in temporal networks

    Ashwin Paranjape, Austin R Benson, and Jure Leskovec. Motifs in temporal networks. In Proceedings of the tenth ACM international conference on web search and data mining, pages 601–610, 2017

    2017

  22. [30]

    Improving online algorithms via ml predictions

    Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. In Advances in Neural Information Processing Systems, pages 9661–9670, 2018

    2018

  23. [31]

    Approximation algorithms for 2-stage stochastic optimization problems

    Chaitanya Swamy and David B Shmoys. Approximation algorithms for 2-stage stochastic optimization problems. ACM SIGACT News, 37(1):33–46, 2006

    2006

  24. [32]

    Partitioned learned bloom filters

    Kapil Vaidya, Eric Knorr, Michael Mitzenmacher, and Tim Kraska. Partitioned learned bloom filters. In9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL https://openreview.net/forum?id= 6BRLOfrMh...

    2021

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.