Pith. sign in

REVIEW 5 minor 27 references

A Bicriterion Concentration Inequality and Prophet Inequalities for $k$-Fold Matroid Unions

T0 review · 0 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 This paper proves every k-fold matroid union admits a prophet inequality with competitive ratio approaching 1, while large girth alone cannot beat 1/2.

desk verdict Novel bicriterion concentration inequality that is proved correctly and powers a strong OCRS/prophet inequality for k-fold matroid unions; only presentation-level issues need fixing. read the letter →

arxiv 2411.11741 v2 pith:RELCTMCX submitted 2024-11-18 cs.DS math.PR

Noga Alon , Nick Gravin , Tristan Pollner , Aviad Rubinstein , Hongao Wang , S. Matthew Weinberg , Qianfan Zhang This is my paper · ORCID
classification cs.DSmath.PR MSC 60E1505B3568W2790C2760G40
keywords ProphetinequalitiesOnlinecontentionresolutionschemesk-foldmatroidunionsBicriterionconcentrationinequalitygirthSelf-boundingfunctionsEntropymethodDimension-freetailbounds
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

This paper asks which feasibility families admit prophet inequalities with competitive ratio approaching 1, in the way that k-uniform matroids do. It proves two answers: large girth alone is not enough, because there are graphic matroids of girth at least k on which no algorithm beats 1/2; but k-fold matroid unions are enough, because every such union admits a $1-O(\sqrt{\log k/k})$-competitive prophet inequality. The positive result is built from an online contention resolution scheme whose selectability rests on a new bicriterion concentration inequality: after scaling every item's activation probability down by $e^{-s}$, any monotone 1-Lipschitz function over independent Bernoulli items has a dimension-free exponential tail of size $e^{-st}$. This inequality supplies the 'Chernoff-strength' concentration that the matroid-union setting needs, even though the occupancy functions involved are not self-bounding.

What carries the argument

The key machinery is the bicriterion concentration inequality of Theorem 3: for every monotone 1-Lipschitz $f$ and every $s\in(0,1]$, $t>0$, $\Pr[f(X^{(s)})\ge \mathbb{E}[f(X)]+t]\le e^{-st}$, where $X^{(s)}$ has probabilities $e^{-s}p$. The proof studies $F(\lambda)=\mathbb{E}[e^{\lambda f(X^{(\lambda)})}]$, in which $\lambda$ acts simultaneously as the tail parameter and the scaling factor; a derivative estimate combined with a modified logarithmic Sobolev inequality yields the differential inequality $\lambda F'(\lambda)\le F(\lambda)\log F(\lambda)$, and Markov's inequality converts the resulting bound on $F$ into the tail bound. This inequality is what makes the chain-decomposition OCRS work: it turns the expected-occupancy bound $\mathbb{E}[\omega_e(R(x^*)\cup N_1)]\le bk$ into a high-probability guarantee that $\omega_e$ stays below $k$ after the extra scaling by $e^{-(1-b)}$.

What would settle it

A direct test: for a small k-fold matroid union, take the occupancy function from Definition 14, choose probabilities $p$ so that $\mathbb{E}[f(X)]\approx k$, set $s=\sqrt{\log k/k}$ and $t=\sqrt{k\log k}$, and numerically evaluate $\Pr[f(X^{(s)})\ge \mathbb{E}[f(X)]+t]$. Theorem 3 requires this tail to be at most $e^{-st}\approx 1/k$; a single violation for a monotone 1-Lipschitz $f$ would refute the central technical claim. A simpler surrogate is $f(x)=\min(m,\sum_i x_i)$ with $m\gg k$, where the exponent $-st$ is known to be sharp up to a constant, so checking whether the bound holds there tests the inequality's tightness.

Watch

Extended reading notes

Core claim

The central claim is that a k-fold matroid union supports a $1-O(\sqrt{\log k/k})$-selectable online contention resolution scheme, and therefore a prophet inequality with the same competitive ratio for arbitrary value distributions. The proof defines an occupancy function $\omega_e(S)=k-\mathrm{rank}(S\cup(\{e\}\times[k]))+\mathrm{rank}(S)$ on the extended k-fold union, which is monotone, 1-Lipschitz, and detects when an element is spanned; a chain decomposition protects elements whose expected occupancy is close to k. Selectability reduces to a tail bound on the monotone 1-Lipschitz function $f(S)=\omega_e(S\cup N_1)$, and the paper proves the bicriterion inequality $\Pr[f(X^{(s)})\ge \mathbb{E}[f(X)]+t]\le e^{-st}$ for the scaled Bernoulli vector $X^{(s)}\sim\mathrm{Ber}(e^{-s}p)$. The concentration inequality is the technical heart: it gives dimension-free exponential concentration for functions that need not be self-bounding, at the price of comparing $f(X^{(s)})$ with $\mathbb{E}[f(X)]$ rather than $f(X)$.

Load-bearing premise

The load-bearing premise is the new bicriterion concentration inequality (Theorem 3) for monotone 1-Lipschitz functions; if it fails for some occupancy function, the selectability estimate in Subsection 4.3.3, and with it the near-1 prophet inequality for k-fold matroid unions, collapses.

Editorial extensions

If this is right

  • Every k-fold matroid union admits a $1-O(\sqrt{\log k/k})$-competitive prophet inequality, matching the k-uniform matroid guarantee up to a logarithmic factor.
  • The implied online contention resolution scheme is $1-O(\sqrt{\log k/k})$-selectable, so each element is accepted with almost its marginal probability even under an adversary that sees all past realizations.
  • Large girth does not yield near-1 prophet inequalities: for every k, there exist graphic matroids of girth k whose optimal competitive ratio is $1/2$, so the k-fold union property is doing the real work.
  • The bicriterion concentration inequality is a standalone tool: for any monotone 1-Lipschitz function over independent items, an exponential scaling of probabilities forces a dimension-free $e^{-st}$ upper tail.
  • Whether the $O(\sqrt{\log k/k})$ rate can be sharpened to $O(1/\sqrt{k})$ for k-fold unions remains open.

Reading between the lines

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

  • The bicriterion inequality likely transfers to other online selection problems with feasibility defined by a matroid union or packing constraint: scale down arrival probabilities, prove occupancy concentration, then recover selectability.
  • The negative result for large girth suggests that the right combinatorial property for near-1 prophet inequalities is not cycle-freeness but union-of-matroids structure; one could test whether other matroid operations (truncation, direct sums, transversal matroids) preserve the guarantee.
  • The theorem leaves a natural quantitative question: whether the $e^{-s}$ scaling in the concentration inequality is necessary, or whether a milder scaling such as $p\to(1-c\sqrt{\log k/k})p$ would suffice for the specific occupancy functions used.
  • A numerical search over small matroids could calibrate the constant in the $e^{-st}$ exponent and check whether the bound is tight for the exact class of occupancy functions, not just for linear $f$.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 5 minor

Summary. The paper studies prophet inequalities for k-fold matroid unions. It first shows that large girth alone is not sufficient: for every k there is a graphic matroid of girth at least k whose optimal competitive ratio is at most 1/2+epsilon (Theorem 1). It then proves a near-optimal prophet inequality with competitive ratio 1-O(sqrt(log k/k)) for every k-fold matroid union (Theorem 2), obtained from a (1-O(sqrt(log k/k)))-selectable online contention resolution scheme (Theorem 9). The key technical ingredient is a new bicriterion concentration inequality (Theorem 3): for any monotone 1-Lipschitz function f over independent Bernoulli variables X and any s in (0,1], Pr[f(X^(s)) >= E[f(X)] + t] <= e^{-st}, where X^(s) has probabilities scaled by e^{-s}. The proof combines an entropy-method differential inequality with Massart's modified logarithmic Sobolev inequality. I verified the main logical chain: Theorem 3 follows from Lemmas 21-24, the OCRS analysis in Section 4.3.3 applies the concentration bound to a carefully defined occupancy function, Lemma 18 establishes the required chain decomposition, and Section 3 gives an explicit hardness construction.

Significance. If the results hold, Theorems 2 and 9 give a substantial generalization of the known near-optimal prophet inequalities for k-uniform matroids to all k-fold matroid unions, and the OCRS is directly useful. The concentration inequality (Theorem 3) is novel and dimension-free in a bicriterion sense; it applies to all monotone 1-Lipschitz functions, a class for which ordinary dimension-free upper-tail bounds are impossible, so it may well be of independent interest. The paper contains fully written proofs of the central lemmas, including the entropy-method derivation and the explicit high-girth construction, and it does not rely on fitted parameters or circular reasoning. The main weakness is a small number of local proof-completeness issues that should be fixed, but they do not affect the validity of the asymptotic results.

minor comments (5)
  1. [Section 4.3.3, final paragraph] The displayed chain 'Pr[(e,i) is accepted | (e,i) is active] >= 1 - Pr[f(X') >= k]' omits the e^{-(1-b)} factor coming from the initial rejection step in Algorithm 4. The correct inequality is Pr[(e,i) accepted | (e,i) active] >= e^{-(1-b)} * (1 - Pr[f(X') >= k]). The final selectability formula already contains this factor, so the issue is local, but the displayed chain should be corrected.
  2. [Appendix B, proof of Lemma 18] The proof needs one additional justification: when bounding the stopping condition for e_i, one must replace S0_before x [k] by {e_1,...,e_{i-1}} x [k]. This is valid because {e_1,...,e_{i-1}} is a basis of S0_before in M, so {e_1,...,e_{i-1}} x [k] spans S0_before x [k] in the extended k-fold union. As written, the equalities involving span are false (span is not equal to S0 unless S0 is closed), and the transfer of the condition E[omega_e_i(R cup S)] > bk to the smaller set is asserted without proof.
  3. [Theorem 1 statement vs. Section 3 proof] The theorem states that the constructed matroid has girth exactly k, but the proof only establishes girth at least 2k (after the edge-splitting construction). The abstract uses 'girth >= k', which is what the proof supports. To match the theorem statement, either weaken it to 'girth at least k' or explicitly add a disjoint k-cycle to the construction.
  4. [Theorem 2 statement] The theorem is stated for every k >= 1, but the claimed bound 1 - O(sqrt(log k/k)) is false for k = 1: any matroid is the 1-fold union of itself, and not every matroid admits a 1-competitive prophet inequality. The proof itself shows the selectability is (1-1/k)*b*e^{-(1-b)}, which is 0 for k = 1. The statement should be restricted to sufficiently large k or handled separately.
  5. [Section 4.3.3, notation after Fact 10] In the sentence 'we prove Theorem 9 by showing the existence of an OCRS for all k-fold union M^k and x* in P_{M^k}', the symbol x* is used both for the extended ground set and the original ground set. Please distinguish the original vector x from the extended vector x* to avoid confusion.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central derivation is self-contained and rests on external lemmas.

full rationale

I examined the paper's claimed derivation chain. Theorem 1 uses an external dense high-girth graph construction [18] and an embedding argument; it does not presuppose the positive result. Theorem 2 is derived from Theorem 9, whose proof applies Theorem 3. Theorem 3 is proved from the external modified logarithmic Sobolev inequality (Lemma 21, cited to Massart [20]) via a self-contained differential inequality for F(λ) = E[e^{λZ(λ)}] (Lemma 22). The proof of Lemma 22 is algebraic, using only monotonicity and 1-Lipschitzness, and does not assume the target tail bound. The subsequent comparison with G0(λ) = λE[Z(0)] and Markov's inequality is a standard closure of the argument. In the OCRS analysis, no parameter is fitted from data and then called a prediction; the scaling factor e^{-(1-b)} and threshold sqrt(k log k) are chosen explicitly, and the selectability bound follows by direct substitution into Theorem 3. The few self-citations appearing in the related-work discussion are not load-bearing; the actual proof relies on external prior work [12, 18, 20]. The only issues I identified are at the presentation/correctness level (the Theorem 1 statement says girth k while the construction gives girth at least k, and the k=1 case is not handled by the asymptotic statement) and do not constitute circularity. The derivation is therefore self-contained against external benchmarks.

Assumptions & free parameters 3 free parameters · 4 assumptions · 2 invented entities

The central claims rest on standard matroid theory, the cited entropy-method inequality, and a cited graph construction. The only hand-chosen parameters are the OCRS design parameters b, s, and t, which are explicit in the proof and not fitted to data. The occupancy function and extended union are internal proof devices with no independent empirical status.

free parameters (3)
  • b = 1 - sqrt(log k/k)
    OCRS scaling parameter in Fact 10 and Algorithm 4; chosen by hand to optimize the final selectability bound.
  • s = 1 - b = sqrt(log k/k)
    Scaling factor in the concentration inequality application; equals the thinning exponent.
  • t = sqrt(k log k)
    Deviation threshold in the concentration inequality application; chosen so that E[f(X)] + t is at most k.
assumptions (4)
  • standard math Massart's modified logarithmic Sobolev inequality (Lemma 21)
    Used in Section 5 to derive the differential inequality for F(λ); cited to [20].
  • standard math The k-fold union of a matroid is a matroid (matroid union closure)
    Used in Definition 7 and Lemma 13 to justify that M^k and M^k_* are matroids.
  • domain assumption Existence of dense graphs with arbitrarily large girth (Lazebnik et al.)
    Used in the proof of Theorem 1 to build hard instances; cited to [18].
  • standard math A c-selectable OCRS implies a c-competitive prophet inequality (Lemma 4)
    Used in Section 1 and Section 4 to convert OCRS selectability to a prophet inequality; cited to [12].
invented entities (2)
  • Extended k-fold union M^k_*
    purpose: Introduces k parallel copies of each element to define the occupancy function; Lemma 13 shows an OCRS for M^k_* implies one for M^k.
    Mathematical construct for the proof; its properties are proven internally, but it has no falsifiable handle outside the paper.
  • Occupancy function ω_e
    purpose: Measures the number of occupied slots of element e in a set S; used to define protection sets in Algorithm 3 and to apply the concentration inequality.
    Proof device; its needed properties (monotone, 1-Lipschitz, Lemma 16) are proven in the paper, not empirically evidenced.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Bicriterion Concentration Inequality and Prophet Inequalities for $k$-Fold Matroid Unions." pith.science (2026). https://pith.science/paper/RELCTMCX

@misc{pith2026241111741,
  author       = {Pith},
  title        = {Pith review of: A Bicriterion Concentration Inequality and Prophet Inequalities for $k$-Fold Matroid Unions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RELCTMCX}},
  note         = {Machine review of arXiv:2411.11741}
}
abstract

We investigate prophet inequalities with competitive ratios approaching $1$, seeking to generalize $k$-uniform matroids. We first show that large girth does not suffice: for all $k$, there exists a matroid of girth $\geq k$ and a prophet inequality instance on that matroid whose optimal competitive ratio is $\frac{1}{2}$. Next, we show $k$-fold matroid unions do suffice: we provide a prophet inequality with competitive ratio $1-O(\sqrt{\frac{\log k}{k}})$ for any $k$-fold matroid union. Our prophet inequality follows from an online contention resolution scheme. The key technical ingredient in our online contention resolution scheme is a novel bicriterion concentration inequality for arbitrary monotone $1$-Lipschitz functions over independent items which may be of independent interest. Applied to our particular setting, our bicriterion concentration inequality yields "Chernoff-strength" concentration for a $1$-Lipschitz function that is not (approximately) self-bounding.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

27 extracted references · 15 canonical work pages

  1. [1]

    Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers

    Saeed Alaei. Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM Journal on Computing , 43(2):930--972, 2014. https://doi.org/10.1137/120878422 doi:10.1137/120878422

    doi:10.1137/120878422 2014

  2. [2]

    Bayesian optimal auctions via multi- to single-agent reduction

    Saeed Alaei, Hu Fu, Nima Haghpanah, Jason Hartline, and Azarakhsh Malekian. Bayesian optimal auctions via multi- to single-agent reduction. In Proceedings of the 13th ACM Conference on Electronic Commerce , EC '12, page 17, New York, NY, USA, 2012. Association for Computing Machinery. https://doi.org/10.1145/2229012.2229017 doi:10.1145/2229012.2229017

    arXiv 2012

  3. [3]

    C. J. Argue, Anupam Gupta, Marco Molinaro, and Sahil Singla. Robust secretary and prophet algorithms for packing integer programs. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022 , pages 1273--1297. SIAM, SIAM , ...

    work page doi:10.1137/1.9781611977073.53 2022

  4. [4]

    Matthew Weinberg

    Pablo Daniel Azar, Robert Kleinberg, and S. Matthew Weinberg. Prophet inequalities with limited information. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014 , pages 1358--1377, 2014. https://doi.org/10.1137/1.9781611973402.100 doi:10.1137/1.9781611973402.100

    doi:10.1137/1.9781611973402.100 2014

  5. [5]

    A sharp concentration inequality with applications

    St \'e phane Boucheron, G \'a bor Lugosi, and Pascal Massart. A sharp concentration inequality with applications. Random Structures & Algorithms , 16(3):277--292, 2000. https://doi.org/10.1002/(SICI)1098-2418(200005)16:3\

    work page doi:10.1002/(sici)1098-2418(200005)16:3

  6. [6]

    Concentration inequalities using the entropy method

    St \'e phane Boucheron, G \'a bor Lugosi, and Pascal Massart. Concentration inequalities using the entropy method. The Annals of Probability , 31(3):1583--1614, 2003

    work page 2003

  7. [7]

    On concentration of self-bounding functions

    Stephane Boucheron, Gabor Lugosi, and Pascal Massart. On concentration of self-bounding functions . Electronic Journal of Probability , 14:1884 -- 1899, 2009

    work page 2009

  8. [8]

    Hartline, David L

    Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. Multi-parameter mechanism design and sequential posted pricing. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010 , pages 311--320. ACM , 2010. https://doi.org/10.1145/1806689.1806...

    arXiv 2010

Show all 27 references
  1. [9]

    Contention resolution for the l-fold union of a matroid via the correlation gap

    Chandra Chekuri, Junkai Song, and Weizhong Zhang. Contention resolution for the l-fold union of a matroid via the correlation gap. In 2024 Symposium on Simplicity in Algorithms (SOSA) , pages 396--405. SIAM, 2024. https://doi.org/10.1137/1.9781611977936.36 doi:10.1137/1.978161...

    2024 doi

  2. [10]

    Matthew Weinberg

    Atanas Dinev and S. Matthew Weinberg. Simple and Optimal Online Contention Resolution Schemes for k-Uniform Matroids . In Venkatesan Guruswami, editor, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) , volume 287 of Leibniz International Proceedings in ...

    2024 doi

  3. [11]

    Prophet inequalities made easy: Stochastic optimization by pricing nonstochastic inputs

    Paul D \" u tting, Michal Feldman, Thomas Kesselheim, and Brendan Lucier. Prophet inequalities made easy: Stochastic optimization by pricing nonstochastic inputs. SIAM J. Comput. , 49(3):540--582, 2020. https://doi.org/10.1137/20M1323850 doi:10.1137/20M1323850

    2020 doi

  4. [12]

    Online contention resolution schemes

    Moran Feldman, Ola Svensson, and Rico Zenklusen. Online contention resolution schemes. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016 , pages 1014--1033. SIAM...

    2016 doi

  5. [13]

    Automated online mechanism design and prophet inequalities

    Mohammad Taghi Hajiaghayi, Robert Kleinberg, and Tuomas Sandholm. Automated online mechanism design and prophet inequalities. In AAAI , volume 7, pages 58--65, 2007. URL: http://www.aaai.org/Library/AAAI/2007/aaai07-009.php

    2007

  6. [14]

    Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack

    Jiashuo Jiang, Will Ma, and Jiawei Zhang. Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1221--1246. SIAM, 2022. https://doi.org/10.1137/1.978161197...

    2022 doi

  7. [15]

    o nnis, Klaus Radke, and Berthold V \

    Thomas Kesselheim, Andreas T \"o nnis, Klaus Radke, and Berthold V \"o cking. Primal beats dual on online packing lps in the random-order model. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages 303--312, 2014. https://doi.org/10.1145/259179...

    2014

  8. [16]

    Matthew Weinberg

    Robert Kleinberg and S. Matthew Weinberg. Matroid prophet inequalities. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012 , pages 123--136, 2012. https://doi.org/10.1145/2213977.2213991 doi:10.1145/2213977.2213991

    2012

  9. [17]

    On semiamarts, amarts, and processes with finite value

    Ulrich Krengel and Louis Sucheston. On semiamarts, amarts, and processes with finite value. Advances in Probability and Related Topics , 4:197--266, 1978

    1978

  10. [18]

    A new series of dense graphs of high girth

    Felix Lazebnik, Vasiliy A Ustimenko, and Andrew J Woldar. A new series of dense graphs of high girth. Bulletin of the American mathematical society , 32(1):73--79, 1995

    1995

  11. [19]

    Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities

    Euiwoong Lee and Sahil Singla. Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities . In 26th Annual European Symposium on Algorithms (ESA 2018) , volume 112, pages 57:1--57:14. Schloss Dagstuhl -- Leibniz-Zentrum f \"u r Informatik, 2018. https://doi....

    2018 doi

  12. [20]

    About the constants in talagrand's concentration inequalities for empirical processes

    Pascal Massart. About the constants in talagrand's concentration inequalities for empirical processes. The Annals of Probability , 28(2):863--884, 2000

    2000

  13. [21]

    On the method of bounded differences

    Colin McDiarmid et al. On the method of bounded differences. Surveys in combinatorics , 141(1):148--188, 1989

    1989

  14. [22]

    Concentration for self-bounding functions and an inequality of talagrand

    Colin McDiarmid and Bruce Reed. Concentration for self-bounding functions and an inequality of talagrand. Random Structures & Algorithms , 29(4):549--557, 2006. https://doi.org/10.1002/rsa.20145 doi:10.1002/rsa.20145

    2006 doi

  15. [23]

    Combinatorial prophet inequalities

    Aviad Rubinstein and Sahil Singla. Combinatorial prophet inequalities. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19 , pages 1671--1687, 2017. https://doi.org/10.1137/1.9781611...

    2017 doi

  16. [24]

    Matthew Weinberg

    Aviad Rubinstein and S. Matthew Weinberg. Simple mechanisms for a subadditive buyer and applications to revenue monotonicity. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC '15, Portland, OR, USA, June 15-19, 2015 , pages 377--394, 2015. https:...

    2015

  17. [25]

    Comparison of threshold stop rules and maximum for independent nonnegative random variables

    Ester Samuel - Cahn. Comparison of threshold stop rules and maximum for independent nonnegative random variables. Annals of Probability , 12(4):1213--1216, 1984

    1984

  18. [26]

    Concentration, results and applications

    Gideon Schechtman. Concentration, results and applications. In Handbook of the geometry of Banach spaces , volume 2, pages 1603--1634. Elsevier, 2003

    2003

  19. [27]

    A note on concentration of submodular functions

    Jan Vondr \' a k. A note on concentration of submodular functions. CoRR , abs/1005.2791, 2010. URL: http://arxiv.org/abs/1005.2791, https://arxiv.org/abs/1005.2791 arXiv:1005.2791 , https://doi.org/10.48550/arXiv.1005.2791 doi:10.48550/arXiv.1005.2791

    2010 doi arXiv

Pith tools

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