mlsanityData to 7 Oct 2026

Online Computation with Untrusted Advice

arXiv 1905.05655 ↗First posted 14 May 2019cs.DScited by 42

Not on the map. Why?

Abstract (arXiv)

We study a generalization of the advice complexity model of online computation in which the advice is provided by an untrusted source. Our objective is to quantify the impact of untrusted advice so as to design and analyze online algorithms that are robust if the advice is adversarial, and efficient is the advice is foolproof. We focus on four well-studied online problems, namely ski rental, online bidding, bin packing and list update. For ski rental and online bidding, we show how to obtain algorithms that are Pareto-optimal with respect to the competitive ratios achieved, whereas for bin packing and list update, we give online algorithms with worst-case tradeoffs in their competitiveness, depending on whether the advice is trusted or adversarial. More importantly, we demonstrate how to prove lower bounds, within this model, on the tradeoff between the number of advice bits and the competitiveness of any online algorithm.

Key facts. Cited by 42 papers in the map (data through 7 Oct 2026). First posted on arXiv 14 May 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 5; 2023: 7; 2024: 7; 2025: 10; 2026: 5.

42 papers.

Sort:

  1. 2021Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Boundscited by 20
  2. 2021Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problemscited by 19
  3. 2022Chasing Convex Bodies and Functions with Black-Box Advicecited by 19
  4. 2023Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysiscited by 16
  5. 2023Sorting with Predictionscited by 14
  6. 2024Online bipartite matching with imperfect advicecited by 13
  7. 2022A Regression Approach to Learning-Augmented Online Algorithmscited by 12
  8. 2021Online Bin Packing with Predictionscited by 11
  9. 2021(Optimal) Online Bipartite Matching with Degree Informationcited by 11
  10. 2021Double Coverage with Machine-Learned Advicecited by 10
  11. 2021Robustification of Online Graph Exploration Methodscited by 10
  12. 2023Active causal structure learning with advicecited by 10
30 more
  1. 2023Improved Frequency Estimation Algorithms with and without Predictionscited by 10
  2. 2022Learning-Augmented Algorithms for Online TSP on the Linecited by 8
  3. 2024Contract Scheduling with Distributional and Multiple Advicecited by 8
  4. 2024Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithmscited by 8
  5. 2022Leveraging Initial Hints for Free in Stochastic Linear Banditscited by 7
  6. 2025On Tradeoffs in Learning-Augmented Algorithmscited by 7
  7. 2025Algorithms with Calibrated Machine Learning Predictionscited by 7
  8. 2024Robust Learning-Augmented Dictionariescited by 6
  9. 2024Learning-Based Algorithms for Graph Searching Problemscited by 4
  10. 2024Learning multivariate Gaussians with imperfect advicecited by 4
  11. 2025Approximate Proportionality in Online Fair Divisioncited by 4
  12. 2021Online Primal-Dual Algorithms with Predictions for Packing Problemscited by 3
  13. 2025Learning-Augmented Online Bidding in Stochastic Settingscited by 3
  14. 2021Online Search With Best-Price and Query-Based Predictionscited by 2
  15. 2023Sorting and Hypergraph Orientation under Uncertainty with Predictionscited by 2
  16. 2023On Optimal Consistency-Robustness Trade-Off for Learning-Augmented Multi-Option Ski Rentalcited by 2
  17. 2024Primal-Dual Algorithms with Predictions for Online Bounded Allocation and Ad-Auctions Problemscited by 2
  18. 2025Learning-Augmented Online Bipartite Matching in the Random Arrival Order Modelcited by 2
  19. 2022Online TSP with Predictionscited by 1
  20. 2023Online Covering with Multiple Expertscited by 1
  21. 2025Optimizing Health Coverage in Ethiopia: A Learning-augmented Approach and Persistent Proportionality Under an Online Budgetcited by 1
  22. 2025Learning-Augmented Streaming Algorithms for Correlation Clusteringcited by 1
  23. 2025Product distribution learning with imperfect advicecited by 1
  24. 2026Learning-Augmented Online Minimization with Dual Predictionscited by 1
  25. 2025Decision-Theoretic Approaches for Improved Learning-Augmented Algorithmscited by 0
  26. 2025On multiagent online problems with predictionscited by 0
  27. 2026Analyzing the effect of prediction accuracy on the distributionally-robust competitive ratiocited by 0
  28. 2026Online Algorithms with Unreliable Guidancecited by 0
  29. 2026Robust and Consistent Ski Rental with Distributional Advicecited by 0
  30. 2026Online Allocation with Unknown Shared Supplycited by 0