pith. sign in

arxiv: 2605.19181 · v1 · pith:FPHBG2GJnew · submitted 2026-05-18 · 💻 cs.CC

Risk of Bad Tails: CVaR-Aware Pandora's Box and Prophet Inequality

Jingwei Ji This is my paper

Pith reviewed 2026-05-20 06:51 UTC · model grok-4.3

classification 💻 cs.CC
keywords Conditional Value-at-RiskPandora's boxprophet inequalityonline algorithmsrisk-aware optimizationWeitzman indexIFRA distributionsapproximation algorithms
0
0 comments X

The pith

CVaR-aware Pandora's box admits an exact Weitzman-style index solution after one-dimensional variational reduction, while CVaR prophet inequality admits no constant approximation without distributional structure but does under recentered IF

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

This paper examines Conditional Value-at-Risk versions of two classic sequential decision problems. For Pandora's box the risk-aware objective reduces variationally to a one-dimensional problem that preserves an exact index policy. For the prophet inequality the CVaR objective, which evaluates only the worst alpha-fraction of outcomes, prevents any online policy from securing a positive constant approximation ratio in general. The paper proves this impossibility even in two-item instances where the benchmark can be driven arbitrarily large while every online CVaR value stays bounded. When reward distributions are continuous and obey a recentered increasing-failure-rate-average condition, a threshold policy recovers an explicit constant bound.

Core claim

The paper shows that the CVaR-aware Pandora's box problem retains an exact Weitzman-style index solution after a one-dimensional variational reduction. For the prophet inequality it establishes that for every CVaR level alpha in (0,1) no positive constant approximation guarantee can hold without distributional structure, in contrast to the risk-neutral case, and characterizes the tight instance-dependent guarantee; already in two-item hard instances the prophet's CVaR benchmark can be made arbitrarily large while every online policy's CVaR remains bounded. Under continuous reward distributions satisfying the recentered IFRA condition a threshold policy achieves an explicit constant bound.

What carries the argument

One-dimensional variational reduction that converts the CVaR Pandora's box objective into a form solvable by a Weitzman-style index, together with the recentered increasing-failure-rate-average condition that enables a threshold policy for the CVaR prophet inequality.

If this is right

  • An optimal policy for the CVaR Pandora's box can be computed by solving a one-dimensional variational problem and then applying the resulting index rule.
  • No online policy for the CVaR prophet inequality can guarantee a positive constant factor without further assumptions on the reward distributions.
  • The impossibility result already appears in simple two-item settings where the offline CVaR benchmark is unbounded.
  • A threshold policy achieves a fixed constant approximation ratio whenever the distributions are continuous and recentered IFRA.
  • The CVaR objective's focus on only the worst alpha-fraction explains why compromises that preserve high payoffs in the upper tail do not improve the online guarantee.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The variational reduction technique may extend to other risk measures that can be expressed as expectations over tail quantiles in sequential selection problems.
  • Similar distributional conditions could be needed to recover constant-factor guarantees for CVaR versions of additional online problems such as online matching or secretary problems.
  • In practice the result suggests that risk-aware online algorithms may need to estimate or enforce failure-rate properties of the input distributions before deployment.
  • The sharp separation between the index solution for Pandora and the impossibility for prophets highlights how the presence of a stopping decision versus a fixed horizon changes the impact of tail-risk objectives.

Load-bearing premise

The reward distributions must be continuous and satisfy the recentered increasing-failure-rate-average condition to restore a uniform constant approximation guarantee for the CVaR prophet inequality.

What would settle it

A continuous distribution violating the recentered IFRA condition for which every threshold policy fails to achieve any fixed constant approximation to the CVaR benchmark, or a two-item instance in which the CVaR benchmark grows without bound while all online policies keep bounded CVaR.

Figures

Figures reproduced from arXiv: 2605.19181 by Jingwei Ji.

Figure 1
Figure 1. Figure 1: The IFRA bound 𝜌(𝛼) = max{𝜌env (𝛼), 𝜌cap (𝛼)} for 0 < 𝛼 ≤ 1. The solid curve is 𝜌, the dashed curve is 𝜌env, and the dash-dotted curve is 𝜌cap. The larger-cap bound is active near the risk-neutral endpoint; at 𝛼 = 1, the feasible choice 𝑞 = 1/2 gives 𝐺cap (1, 1/2) = 1/2, while the optimized endpoint value is 𝜌cap (1) ≈ 0.503. the threshold payoff at a larger cap. We visualize the resulting bound 𝜌 in [PIT… view at source ↗
read the original abstract

We study Conditional Value-at-Risk (CVaR) variants of two canonical sequential decision problems: Pandora's box and the prophet inequality. For Pandora's box, the risk-aware problem retains an exact Weitzman-style index solution after a one-dimensional variational reduction. For the prophet inequality, the picture is different: for every CVaR level $\alpha\in(0,1)$, no positive constant approximation guarantee can hold without distributional structure, in sharp contrast with the risk-neutral case $\alpha=1$, and we characterize the tight instance-dependent guarantee. Already in two-item hard instances, the prophet's CVaR benchmark can be made arbitrarily large while every online policy's CVaR remains bounded. This impossibility is due to the nature of CVaR objective: it measures only the worst $\alpha$-fraction of outcomes, so any compromise an online policy makes to preserve the chance of a large payoff in the upper $(1-\alpha)$-fraction does not help its CVaR. It turns out that additional distributional structure restores a uniform result: under continuous reward distributions satisfying a recentered increasing-failure-rate-average (IFRA) condition, a threshold policy achieves an explicit constant bound.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript studies Conditional Value-at-Risk (CVaR) variants of Pandora's box and the prophet inequality. It claims that the CVaR-aware Pandora's box retains an exact Weitzman-style index solution after a one-dimensional variational reduction. For the prophet inequality, it shows that for every α in (0,1) no positive constant approximation holds without distributional structure (in contrast to the risk-neutral case α=1), characterizes the tight instance-dependent guarantee, and exhibits two-item hard instances where the benchmark CVaR can be made arbitrarily large while every online policy's CVaR remains bounded. Under continuous reward distributions satisfying a recentered IFRA condition, a threshold policy achieves an explicit constant bound.

Significance. If the derivations hold, the results meaningfully extend the classical theory of Pandora's box and prophet inequalities to risk-sensitive objectives. The exact index preservation for Pandora's box and the clean separation between impossibility without structure and a positive constant under recentered IFRA are technically interesting and highlight how CVaR's focus on the lower tail alters the approximability landscape relative to expectation. The explicit contrast with the risk-neutral case and the instance-dependent characterization add clarity to the literature on online decision-making under tail risk.

minor comments (2)
  1. [§3] §3 (Pandora's box section): the one-dimensional variational reduction is central; a brief explicit statement of the reduced objective and the mapping back to the original index would improve readability for readers unfamiliar with CVaR.
  2. [Prophet inequality section] The recentered IFRA condition is invoked for the positive prophet result; a short paragraph comparing it to standard IFRA and discussing its necessity would help situate the assumption.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of our work and for recommending minor revision. The provided summary accurately captures the key contributions regarding the CVaR variants of Pandora's box and the prophet inequality, including the exact index solution, the impossibility results without distributional assumptions, and the positive constant under the recentered IFRA condition. We have no specific major comments to address point-by-point, as none were raised. We will incorporate minor revisions to improve clarity, notation, and presentation where helpful.

Circularity Check

0 steps flagged

No significant circularity; derivations are self-contained theoretical analysis

full rationale

The paper derives its main results through direct analysis of the CVaR objective function. For Pandora's box, a one-dimensional variational reduction yields an exact Weitzman-style index policy without redefining quantities in terms of the output. For the prophet inequality, the impossibility result for any fixed α without structure follows from the tail-only nature of CVaR, and the positive constant under the recentered IFRA assumption on continuous distributions is obtained by explicit construction of a threshold policy. No step reduces a claimed prediction to a fitted input by construction, invokes a self-citation as the sole justification for a uniqueness claim, or renames an empirical pattern as a new derivation. The central claims remain conditional on explicitly stated distributional assumptions and are not tautological with the inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

The analysis rests on standard mathematical foundations for optimization and probability together with domain assumptions on the reward distributions; no free parameters or invented entities are indicated in the abstract.

axioms (3)
  • standard math Standard axioms of real analysis and probability theory.
    Invoked for defining CVaR, optimization, and sequential decision processes.
  • domain assumption Reward distributions are continuous.
    Stated as necessary for the positive constant-bound result on the prophet inequality.
  • domain assumption Distributions satisfy the recentered increasing-failure-rate-average (IFRA) condition.
    Load-bearing assumption used to recover the explicit constant approximation guarantee.

pith-pipeline@v0.9.0 · 5737 in / 1516 out tokens · 64496 ms · 2026-05-20T06:51:58.802879+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

144 extracted references · 144 canonical work pages

  1. [1]

    Mathematical Finance , volume =

    Artzner, Philippe and Delbaen, Freddy and Eber, Jean-Marc and Heath, David , title =. Mathematical Finance , volume =

    work page

  2. [2]

    Tyrrell and Uryasev, Stanislav , title =

    Rockafellar, R. Tyrrell and Uryasev, Stanislav , title =. Journal of Risk , volume =

    work page

  3. [3]

    Tyrrell and Uryasev, Stanislav , title =

    Rockafellar, R. Tyrrell and Uryasev, Stanislav , title =. Journal of Banking and Finance , volume =

    work page

  4. [4]

    , title =

    Pflug, Georg Ch. , title =. Probabilistic Constrained Optimization: Methodology and Applications , editor =

    work page

  5. [5]

    Journal of Banking and Finance , volume =

    Acerbi, Carlo and Tasche, Dirk , title =. Journal of Banking and Finance , volume =

    work page

  6. [6]

    Shapiro, Alexander and Dentcheva, Darinka and Ruszczy\'nski, Andrzej , title =

    work page

  7. [7]

    Markov Decision Processes with Average-Value-at-Risk Criteria , journal =

    B. Markov Decision Processes with Average-Value-at-Risk Criteria , journal =

    work page

  8. [8]

    More Risk-Sensitive

    B. More Risk-Sensitive. Mathematics of Operations Research , volume =

    work page

  9. [9]

    Minimizing Spectral Risk Measures Applied to

    B. Minimizing Spectral Risk Measures Applied to. Mathematical Methods of Operations Research , volume =

    work page

  10. [10]

    Mathematical Methods of Operations Research , year =

    B. Mathematical Methods of Operations Research , year =

    work page

  11. [11]

    Advances in Neural Information Processing Systems 27 , pages =

    Chow, Yinlam and Ghavamzadeh, Mohammad , title =. Advances in Neural Information Processing Systems 27 , pages =

    work page

  12. [12]

    Advances in Neural Information Processing Systems 28 , pages =

    Chow, Yinlam and Tamar, Aviv and Mannor, Shie and Pavone, Marco , title =. Advances in Neural Information Processing Systems 28 , pages =

    work page

  13. [13]

    Proceedings of the 29th AAAI Conference on Artificial Intelligence , pages =

    Tamar, Aviv and Glassner, Yonatan and Mannor, Shie , title =. Proceedings of the 29th AAAI Conference on Artificial Intelligence , pages =

    work page

  14. [14]

    IEEE Transactions on Automatic Control , volume =

    Tamar, Aviv and Chow, Yinlam and Ghavamzadeh, Mohammad and Mannor, Shie , title =. IEEE Transactions on Automatic Control , volume =

    work page

  15. [15]

    and Jain, Rahul , title =

    Haskell, William B. and Jain, Rahul , title =. SIAM Journal on Control and Optimization , volume =

    work page

  16. [16]

    Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence , pages =

    Petrik, Marek and Subramanian, Dharmashankar , title =. Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence , pages =

    work page

  17. [17]

    Advances in Neural Information Processing Systems 25 , pages =

    Sani, Amir and Lazaric, Alessandro and Munos, R\'emi , title =. Advances in Neural Information Processing Systems 25 , pages =

    work page

  18. [18]

    Proceedings of the 5th Asian Conference on Machine Learning , series =

    Galichet, Nicolas and Sebag, Mich\`ele and Teytaud, Olivier , title =. Proceedings of the 5th Asian Conference on Machine Learning , series =

    work page

  19. [19]

    Algorithmic Learning Theory , series =

    Maillard, Odalric-Ambrym , title =. Algorithmic Learning Theory , series =

    work page

  20. [20]

    Proceedings of the 31st Conference on Learning Theory , series =

    Cassel, Asaf and Mannor, Shie and Zeevi, Assaf , title =. Proceedings of the 31st Conference on Learning Theory , series =

    work page

  21. [21]

    Proceedings of the 38th International Conference on Machine Learning , series =

    Baudry, Dorian and Gautron, Romain and Kaufmann, Emilie and Maillard, Odalric-Ambrym , title =. Proceedings of the 38th International Conference on Machine Learning , series =

    work page

  22. [22]

    NeurIPS Workshop on Safety and Robustness in Decision Making , year =

    Tamkin, Alex and Keramati, Ramtin and Dann, Christoph and Brunskill, Emma , title =. NeurIPS Workshop on Safety and Robustness in Decision Making , year =

    work page

  23. [23]

    Advances in Neural Information Processing Systems 32 , pages =

    Kagrecha, Anmol and Nair, Jayakrishnan and Jagannathan, Krishna , title =. Advances in Neural Information Processing Systems 32 , pages =

    work page

  24. [24]

    Operations Research Letters , volume =

    Khajonchotpanya, Natthawut and Xue, Yifei and Rujeerapaiboon, Napat , title =. Operations Research Letters , volume =

    work page

  25. [25]

    Chang, Joel Q. L. and Tan, Vincent Y. F. , title =. Proceedings of the 36th AAAI Conference on Artificial Intelligence , year =

    work page

  26. [26]

    and Prashanth, L

    Bhat, Sanjay P. and Prashanth, L. A. , title =. Advances in Neural Information Processing Systems 32 , pages =

    work page

  27. [27]

    Prashanth, L. A. and Jagannathan, Krishna and Kolla, Ravi Kumar , title =. Proceedings of the 37th International Conference on Machine Learning , series =

    work page

  28. [28]

    Tan, Vincent Y. F. and Agrawal, Prashanth L. A. and Kalyanakrishnan, Shivaram , title =. Proceedings of the 31st International Joint Conference on Artificial Intelligence, Survey Track , year =

    work page

  29. [29]

    Algorithmic Learning Theory (ALT) , series =

    Even-Dar, Eyal and Kearns, Michael and Wortman, Jennifer , title =. Algorithmic Learning Theory (ALT) , series =

    work page

  30. [30]

    , title =

    Mhammedi, Zakaria and Guedj, Benjamin and Williamson, Robert C. , title =. Advances in Neural Information Processing Systems 33 , year =

    work page

  31. [31]

    and Jegelka, Stefanie and Krause, Andreas , title =

    Curi, Sebastian and Levy, Kfir Y. and Jegelka, Stefanie and Krause, Andreas , title =. Advances in Neural Information Processing Systems 33 , year =

    work page

  32. [32]

    Holland, Matthew J. and. Learning with. Proceedings of the 24th International Conference on Artificial Intelligence and Statistics , series =

    work page

  33. [33]

    Soma, Tasuku and Yoshida, Yuichi , title =

    work page

  34. [34]

    , title =

    Brown, David B. , title =. Operations Research Letters , volume =

    work page

  35. [35]

    , title =

    Fan, Lin and Glynn, Peter W. , title =. Operations Research , year =

    work page

  36. [36]

    Simchi-Levi, David and Zheng, Zeyu and Zhu, Feng , title =

    work page

  37. [37]

    Advances in Neural Information Processing Systems 22 , year =

    Chaudhuri, Kamalika and Freund, Yoav and Hsu, Daniel , title =. Advances in Neural Information Processing Systems 22 , year =

    work page

  38. [38]

    and van Erven, Tim , title =

    Koolen, Wouter M. and van Erven, Tim , title =. Proceedings of the 28th Conference on Learning Theory , series =

    work page

  39. [39]

    Harvey, Nicholas J. A. and Liaw, Christopher and Sanches Portella, Victor , title =. Journal of Machine Learning Research , volume =

    work page

  40. [40]

    Proceedings of the 32nd International Conference on Machine Learning , series =

    Daniely, Amit and Gonen, Alon and Shalev-Shwartz, Shai , title =. Proceedings of the 32nd International Conference on Machine Learning , series =

    work page

  41. [41]

    , title =

    Luo, Haipeng and Schapire, Robert E. , title =. Proceedings of the 28th Conference on Learning Theory , series =

    work page

  42. [42]

    Proceedings of the 20th International Conference on Artificial Intelligence and Statistics , series =

    Jun, Kwang-Sung and Orabona, Francesco and Wright, Stephen and Willett, Rebecca , title =. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics , series =

    work page

  43. [43]

    Advances in Neural Information Processing Systems 31 , pages =

    Zhang, Lijun and Lu, Shiyin and Zhou, Zhi-Hua , title =. Advances in Neural Information Processing Systems 31 , pages =

    work page

  44. [44]

    Proceedings of the 37th International Conference on Machine Learning , series =

    Cutkosky, Ashok , title =. Proceedings of the 37th International Conference on Machine Learning , series =

    work page

  45. [45]

    , title =

    Hazan, Elad and Seshadhri, C. , title =. Proceedings of the 26th International Conference on Machine Learning , pages =

    work page

  46. [46]

    , title =

    Weitzman, Martin L. , title =. Econometrica , volume =

    work page

  47. [47]

    Proceedings of the 17th ACM Conference on Economics and Computation , pages =

    Kleinberg, Robert and Waggoner, Bo and Weyl, Eric Glen , title =. Proceedings of the 17th ACM Conference on Economics and Computation , pages =

    work page

  48. [48]

    Proceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms , pages =

    Singla, Sahil , title =. Proceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms , pages =

    work page

  49. [49]

    Journal of Economic Theory , volume =

    Doval, Laura , title =. Journal of Economic Theory , volume =

    work page

  50. [50]

    Proceedings of the 2019 ACM Conference on Economics and Computation , pages =

    Beyhaghi, Hedyeh and Kleinberg, Robert , title =. Proceedings of the 2019 ACM Conference on Economics and Computation , pages =

    work page 2019

  51. [51]

    Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages =

    Beyhaghi, Hedyeh and Cai, Linda , title =. Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages =

    work page

  52. [52]

    Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages =

    Fu, Hu and Li, Jiawei and Liu, Daogao , title =. Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages =

    work page

  53. [53]

    Mathematics of Operations Research , volume =

    Boodaghians, Shant and Fusco, Federico and Lazos, Philip and Leonardi, Stefano , title =. Mathematics of Operations Research , volume =

    work page

  54. [54]

    Proceedings of the 61st IEEE Symposium on Foundations of Computer Science , pages =

    Chawla, Shuchi and Gergatsouli, Evangelia and Teng, Yifeng and Tzamos, Christos and Zhang, Ruimin , title =. Proceedings of the 61st IEEE Symposium on Foundations of Computer Science , pages =

    work page

  55. [55]

    Advances in Neural Information Processing Systems 36 , year =

    Gergatsouli, Evangelia and Tzamos, Christos , title =. Advances in Neural Information Processing Systems 36 , year =

    work page

  56. [56]

    Proceedings of the 38th AAAI Conference on Artificial Intelligence , pages =

    Atsidakou, Alexia and Caramanis, Constantine and Gergatsouli, Evangelia and Papadigenopoulos, Orestis and Tzamos, Christos , title =. Proceedings of the 38th AAAI Conference on Artificial Intelligence , pages =

    work page

  57. [57]

    Operations Research , volume =

    Aouad, Ali and Ji, Jingwei and Shaposhnik, Yaron , title =. Operations Research , volume =. 2026 , doi =

    work page 2026

  58. [58]

    ACM SIGecom Exchanges , volume =

    Beyhaghi, Hedyeh and Cai, Linda , title =. ACM SIGecom Exchanges , volume =

    work page

  59. [59]

    Bulletin of the American Mathematical Society , volume =

    Krengel, Ulrich and Sucheston, Louis , title =. Bulletin of the American Mathematical Society , volume =

    work page

  60. [60]

    Probability on

    Krengel, Ulrich and Sucheston, Louis , title =. Probability on

    work page

  61. [61]

    The Annals of Probability , volume =

    Samuel-Cahn, Ester , title =. The Annals of Probability , volume =

    work page

  62. [62]

    and Kertz, Robert P

    Hill, Theodore P. and Kertz, Robert P. , title =. Z. Wahrsch. Verw. Gebiete , volume =

    work page

  63. [63]

    and Kertz, Robert P

    Hill, Theodore P. and Kertz, Robert P. , title =. Strategies for Sequential Search and Selection in Real Time , series =

    work page

  64. [64]

    Proceedings of the 18th ACM Conference on Economics and Computation , pages =

    Correa, Jos\'e and Foncea, Patricio and Hoeksma, Ruben and Oosterwijk, Tim and Vredeveld, Tjark , title =. Proceedings of the 18th ACM Conference on Economics and Computation , pages =

    work page

  65. [65]

    Mathematics of Operations Research , volume =

    Correa, Jos\'e and Foncea, Patricio and Hoeksma, Ruben and Oosterwijk, Tim and Vredeveld, Tjark , title =. Mathematics of Operations Research , volume =

    work page

  66. [66]

    Matthew , title =

    Kleinberg, Robert and Weinberg, S. Matthew , title =. Games and Economic Behavior , volume =

    work page

  67. [67]

    Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms , pages =

    Rubinstein, Aviad and Singla, Sahil , title =. Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms , pages =

    work page

  68. [68]

    ACM SIGecom Exchanges , volume =

    Lucier, Brendan , title =. ACM SIGecom Exchanges , volume =

    work page

  69. [69]

    Mathematics of Operations Research , volume =

    Ezra, Tomer and Feldman, Michal and Gravin, Nick and Tang, Zhihao Gavin , title =. Mathematics of Operations Research , volume =

    work page

  70. [70]

    Mathematical Programming , volume =

    Correa, Jos\'e and Saona, Raimundo and Ziliotto, Bruno , title =. Mathematical Programming , volume =

    work page

  71. [71]

    Proceedings of the 24th ACM Conference on Economics and Computation , pages =

    Bubna, Aditya and Chiplunkar, Ashish , title =. Proceedings of the 24th ACM Conference on Economics and Computation , pages =

    work page

  72. [72]

    D. An. Proceedings of the 61st IEEE Symposium on Foundations of Computer Science , pages =

    work page

  73. [73]

    and Kertz, Robert P

    Kennedy, Douglas P. and Kertz, Robert P. , title =. The Annals of Probability , volume =

    work page

  74. [74]

    Proceedings of the 26th ACM Conference on Economics and Computation , pages =

    Livanos, Vasilis and Mehta, Ruta , title =. Proceedings of the 26th ACM Conference on Economics and Computation , pages =. 2025 , doi =

    work page 2025

  75. [75]

    Proceedings of the ACM on Measurement and Analysis of Computing Systems , volume =

    Alijani, Reza and Banerjee, Siddhartha and Gollapudi, Sreenivas and Munagala, Kamesh and Wang, Kangning , title =. Proceedings of the ACM on Measurement and Analysis of Computing Systems , volume =. 2020 , doi =

    work page 2020

  76. [76]

    Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming , series =

    Giambartolomei, Giordano and Mallmann-Trenn, Frederik and Saona, Raimundo , title =. Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming , series =. 2025 , doi =

    work page 2025

  77. [77]

    Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms , pages =

    Livanos, Vasilis and Mehta, Ruta , title =. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms , pages =. 2024 , doi =

    work page 2024

  78. [78]

    and Kleinberg, Robert and Weinberg, S

    Azar, Pablo D. and Kleinberg, Robert and Weinberg, S. Matthew , title =. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms , pages =. 2014 , doi =

    work page 2014

  79. [79]

    Cesa-Bianchi, Nicol\`o and Lugosi, G\'abor , title =

    work page

  80. [80]

    , title =

    Freund, Yoav and Schapire, Robert E. , title =. Journal of Computer and System Sciences , volume =

    work page

Showing first 80 references.