A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse

1.1 Our Results

• β=2−sqrt2≈0.5858 is the supremum achievable with polynomially many value queries and worst-case constant recourse.Every coefficient below β is attainable, whereas any fixed improvement requires exponentially many queries before a critical arrival or Ω(k) changes at that arrival, even with unlimited subsequent computation.Source: §1 · p. 2, §1.1 · p. 2

1.3 Related Work

• The model fixes an oblivious stream and objective, measures approximation in expectation at each fixed time, and requires recourse on every random path.Algorithms may retain all old elements and query any currently available subset, while exact-oracle and bounded-bit rational implementations use the stated query and encoding conventions.Source: §1.1 · p. 2, §1.3 · pp. 4–5

1.1 Our Results

• 1−(sqrt2−1)ϑ is the exact curvature-dependent threshold, with exact optimality at ϑ=0 and linear-recourse-or-exponential-query barriers for fixed ϑ>0.For weighted coverage, the paper instead attains 1−1/e−ε with O(ε^-1) recourse using only aggregate value queries.Source: §1.1 · p. 3
• Future-price certificates always exist at 1−1/e, but constructing them efficiently at any fixed coefficient above β requires exponentially many current queries.Coefficients below β are efficiently constructible, so the certificate framework exposes a computational limit without replacing the all-algorithm threshold of Theorem 1.1.Source: §1.1 · p. 3

1.2 Proof Overview

• The upper bound builds anchored greedy cores and gradually installs them through checkpoint reductions and randomized migration windows that limit changes per update.A short greedy prefix is combined with samples from a longer prefix through a linear program, preserving feasibility while interpolating value guarantees.Source: §1.2 · pp. 3–4
• The matching lower bound hides a useful current complement for one final arrival, using algebraically flat rational profiles whose answers reveal only query size.This hidden-group construction yields the same threshold and establishes the query–recourse tradeoff for randomized value-oracle algorithms.Source: §1.1 · p. 3, §1.2 · p. 4

2.1 Anchoring a Greedy Prefix

• Anchored interpolation retains the first a greedy elements and samples uniformly from the next b − a, certifying the chord between endpoint values at capacity κ.The construction keeps every sampled set feasible and requires no independence between inclusion indicators.Source: §2.1 · p. 5, Figure 1 · p. 6
• The labelled-action linear program has value Γ = infη≥0 maxℓ(aℓ + ηbℓ), admits support on at most two actions, and is computable in O(κ^2 log(κ + 1)).A dual-hull computation produces the optimal mixture from the greedy chain.Source: §2.1 · p. 6

2 A Future-Robust Core and Its Online Implementation

• A future-robust core guarantees E[h(A)] ≥ βP_h for every legal future branch using O(|X|κ) current value queries and polynomial computation.The benchmark P_h is a free-future capacity-κ optimum used only analytically, while the online output must remain feasible under capacity k.Source: §2 · p. 5, §2.2 · p. 7

2.2 The Finite-Cardinality Constant

• Every finite capacity achieves βκ > β, with βκ approaching β at rate Θ(1/κ), while the proof relies on anchored chords crossing the feasible cardinality.The section does not claim optimality for any fixed capacity.Source: §2.2 · p. 7

2.3 An Online Schedule with Hard Recourse

• Checkpoint conversion yields expected approximation α(1 − 2/B)(1 − 1/B) with hard symmetric recourse at most 8B^2 + 2 for every B ≥ 4.The schedule migrates between old and new cores during a randomized window while maintaining a feasible superset and controlling recourse.Source: §2.3 · p. 8, Figure 2 · p. 8
• Choosing B = ⌈6/ε⌉ and using bounded-bit rounding and sampling establishes the algorithmic half of Theorem 1.1 without compromising feasibility or hard recourse.The implementation rounds the two-action mixture weight dyadically and samples anchored completions and migration windows with bounded-bit procedures.Source: §2.3 · p. 8

3.1 Coupled Current and Future Profiles

• The construction couples current and future concave profiles so the balanced unit-size set has value near R(T), while the hidden complement has value at least one.The profiles meet tangentially, share an exponential tail after contact, and are rationalized while preserving the value geometry up to explicitly bounded errors.Source: §3.1 · p. 9

3.2 Exact Hiding and Adaptive Queries

• With probability at least 1 − 2(Q + 1)e^(−δ^2k/2), all pre-arrival answers and the current output match a reference cardinality oracle, whose output imbalance is at most δ.Adaptive queries are handled by fixing the reference transcript first; outside an exceptional event, answers equal G(|S|/k) independently of the hidden partition.Source: §3.2 · p. 11

3.3 A Finite Query–Recourse Bound

• The finite hard instance uses exact rational oracle answers with O_T,m,τ(log(k + 1)) bits, while its value bound remains at most R(T) + 76/m + 10(C + 1)/k + 2(Q + 1)e^(−k/(8192m^2)).The proposition permits adaptive, arbitrarily large pre-arrival queries and unrestricted post-arrival queries; every current singleton has value at most 5/k.Source: §3.3 · pp. 11–12
• A fixed improvement forces C = Ωζ(k) recourse at the final arrival or Q = exp(Ωζ(k)) pre-arrival queries, even when post-arrival queries are unrestricted.The hard instance is chosen before the algorithm’s random tape, so the adversary is oblivious; the tradeoff also extends to expected resources under the stated instance-wise guarantees.Source: §3.3 · p. 12

4 Universal Future Prices: Existence and Query Complexity

• Universal future prices certify current responses against every legal future, while computing bounded prices above β requires exponentially many queries.Prices satisfy a comparator inequality uniformly over compatible futures and belong to the coordinatewise box [0, M_i].Source: §4 · p. 13

4.1 From Current Prices to a Future-Robust Core

• A price gap η yields H_h(x) ≥ (α−ξ−η)P_h simultaneously for every legal future, and bounded-price routines produce feasible robust cores.Projected online linear optimization and future-oblivious dependent rounding support the construction; at most 32κn/η^2 calls are needed.Source: §4.1 · pp. 13–14

4.2 Computable Prices from a Scale Potential

• A scale potential produces universal prices with coefficient T/(1+T), with coordinates in [0, M_i] and polynomial-work approximation for every coefficient below β.The construction queries only the current function and achieves prescribed additive accuracy without exact exponential or expectation evaluation.Source: §4.2 · p. 15

4.3 Decoupling a Future from Its Comparator

• Unknown-future Poisson decoupling preserves 1−1/e when independent samples use shared comparator marginals, even if each future is arbitrarily correlated with its comparator.The coefficient is exact for this response and asymptotically tight for an empty future with a uniformly random singleton comparator.Source: §4.3 · pp. 16–17

4.4 Minimax Produces One Price for Every Future

• Minimax proves that a universal price exists at α_0=1−1/e for every current point, but direct computation may require exponential-size value tables and constraints.The selector depends only on the current restriction, budget-independently; this is an existence result rather than a polynomial-size optimization formulation.Source: §4.4 · pp. 17–18

4.5 An Exponential-Query Obstruction for Every Bounded Price Vector

• Exponential queries are necessary to find any bounded price vector valid for all legal futures and comparators, even with success probability at least 2/3.For every β < α ≤ α0 and η > 0, the worst-case query complexity is exp(Ω_α(n)).Source: §4.5 · pp. 18–19
• The same exponential lower bound holds when certificate validity is required separately for each fixed constraint, rather than simultaneously across all constraints.The constraint-by-constraint formulation concerns expected certificate validity over internal randomness, while retaining a deterministic query cap on every random tape and oracle transcript.Source: §4.5 · p. 19
• The lower bound applies to arbitrary bounded vector outputs without potential or symmetry assumptions and yields an unconditional query separation, not an NP-hardness claim.Together with Section 4.2, it separates the α0 existence threshold from the β polynomial-query construction threshold for prescribed additive certificate error and failure probability.Source: §4.5 · pp. 19–20

Algorithmic upper bound

• The construction preserves the modular part linearly while applying the scale potential only to the residual submodular component, avoiding value loss from Poissonizing a modular objective.The hybrid certificate is used for disjoint future suffixes through a single future-oblivious core law.Source: §5 · pp. 20, 22
• The checkpoint and lazy-superset schedule converts the static hybrid certificate into hard recourse at most 8B^2+2, while finite-bit rounding and polynomial-work caps preserve feasibility and recourse.For small k, recomputation after each arrival still gives the required bound because consecutive outputs differ by fewer than 8B^2 elements.Source: §5 · pp. 21–23
• Theorem 5.2 guarantees E[f(S_t)] ≥ max_{|O|≤k}{ℓ(O)+βg(O)}−εOPT_k(f,X_t) with polynomially many current queries and O(ε^-2) hard symmetric recourse.The guarantee applies when f=g+ℓ, with g normalized monotone submodular and ℓ nonnegative modular.Source: §5 · p. 21

Curvature lower bound

• The matching lower bound uses exact rational instances of full-stream curvature at most ϑ, with logarithmic-bit oracle answers and no restriction on post-arrival queries or computation.The hard instances contain (m+1)k current elements and one final element, and the modular regularizer is retained at finite m.Source: §5 · pp. 23–24
• For any fixed improvement ζ over the curvature-dependent threshold, the lower bound forces either C=Ωϑ,ζ(k) symmetric changes at the final arrival or Q=exp(Ωϑ,ζ(k)) queries beforehand.The result holds for rational curvature parameters and extends to arbitrary fixed real ϑ by approximation.Source: §5 · p. 24

6.1 An Aggregate-Oracle Certificate

• Aggregate current values suffice to implement the stronger coverage certificate without revealing atom identities or weights.The current extension and gradient are determined by the aggregate function, even though the proof uses an atom representation.Source: §6 · p. 24, §6.1 · p. 25

6 When Stronger Prices Are Accessible

• Coverage attains α0−ε with hard recourse at most 4⌈2/ε⌉+2 using polynomially many current queries and polynomial-bit computation.A fixed improvement above α0 in randomized polynomial time would imply NP ⊆BPP, even without a recourse restriction.Source: §6 · p. 25

6.2 Independent Slots and a Hard Migration Bound

• Independent slots convert fractional cores into feasible sets while concavity guarantees value along every mixture of old and new cores.Categorical domination gives expected value at least the Poisson response, and the mixture inequality applies for arbitrary overlap with the fixed future set.Source: §6.2 · pp. 25–26
• The migration schedule changes at most c positions per update pathwise, including block boundaries and recent-set resets.The invariants |Kt| ≤κ, |Rt| ≤2L, and Tt ⊆St ⊆Xt establish the hard recourse bound; for coverage, B=⌈2/ε⌉ yields fewer than 4B changes in the small-k branch.Source: §6.2 · pp. 27–28

6.3 The Role of Matroid Representation

• The represented matroid result does not recover hidden decompositions: aggregate current values may not determine principal prices or their valid future extension.Thus represented and hidden-MRS models remain distinct.Source: §6.3 · p. 29

7 Discussion

• The loss arises because a single obliviously chosen final arrival can reveal useful old elements only after bounded recourse prevents installing them, even with unlimited subsequent queries.Thus the obstruction is not limited post-arrival computation or adaptivity, but information hidden during gradual movement.Source: §7 · p. 29
• The exact threshold is a joint information–movement constant, while the curvature law shows how preserving more modular value reduces the loss.It is therefore not solely an oracle-hardness or stability constant.Source: §7 · p. 29
• Universal product-response certificates exist at the offline coefficient 1−1/e, but any uniform oracle procedure computing one above 2−sqrt2 requires exponentially many queries.This separates the existence of a certificate from its efficient computation.Source: §7 · p. 29
• Coverage avoids this barrier through a concave Poisson response, whereas represented matroid-rank sums use explicit principal-partition prices and persistent component access.These positive algorithms query neither actual future arrivals nor a distribution over them.Source: §7 · p. 29
• The results apply to insertion-only streams with an oblivious adversary, fixed-time expected approximation, and pathwise symmetric recourse, while allowing infeasible queries, full-prefix retention, and polynomial update work.They do not establish space, amortized-recourse, simultaneous-high-probability, deletion, adaptive-order, feasible-query-only, or small-memory guarantees.Source: §7 · p. 29
• Open questions concern hard recourse needed for β−ε, the approximation curve at fractional recourse, smaller storage and worst-case update time, and aggregate-query-only algorithms for matroid-rank sums.The present work determines the general and curvature-dependent constant-recourse thresholds but leaves these finer tradeoffs unresolved.Source: §7 · p. 29

A Bounded-Work Oracle Algorithms and Fixed-Bit Sampling

• The appendix supports bounded-work oracle algorithms for exact polynomial-bit rational answers, with runtime depending on prefix size, input bit length, and 1/ε.Randomized routines have deterministic work caps; inaccurate estimates may reduce expected value but preserve feasibility and recourse.Source: A Bounded-Work Oracle Algorithms and… · p. 31

A.1 The Checkpoint Schedule

• Lazy supersets maintain a feasible displayed set containing each target, with displayed symmetric-difference recourse at most twice the target’s insertion changes.The construction adds newly required elements and deletes only enough retained elements to restore capacity.Source: §A.1 · pp. 31–32
• The schedule uses blocks of length L, a κ-position core, and a random migration window of width W, with targets combining the migrating core and recent elements.At each block start, Jq is sampled uniformly and fixed throughout the block; fresh core tuples are computed at block boundaries.Source: §A.1 · p. 32
• Each target changes by at most c + 1 elements per insertion, including across block boundaries, because migration changes at most c core positions while the recent suffix gains one arrival.The migration completes within the selected window because cW ≥ κ.Source: §A.1 · p. 32
• 8B^2 + 2 bounds recourse uniformly: large k uses lazy supersets with at most 2(c + 1) changes, while small k recomputes greedy with symmetric difference below 8B^2.When k < 4B^2, ordinary greedy achieves at least 1 − 1/e approximation and recourse below 8B^2.Source: §A.1 · p. 32
• At any fixed time, migration is exceptional for at most one of the B possible window choices, so nonexceptional targets retain an expected α OPT_κ(X_t) benchmark.The same comparator argument applies before and after migration, and the first block is exact.Source: §A.1 · pp. 32–33
• A uniform κ-subset of an optimal k-set yields OPT_κ(X_t) ≥ (1 − 2/B) OPT_k(X_t), completing the schedule’s comparison to the k-element optimum.This relation follows from κ = k − 2L and the parameter choice L = floor(k/B).Source: §A.1 · pp. 32–33

Implementation

• Polynomial-time implementation uses O(nκ) oracle calls, O(κ^2 log(κ + 1)) arithmetic operations, and polynomial-bit mixture probabilities.It needs neither an exact optimum value nor a search over unknown future scales.Source: §A.2 · p. 33

Core sampling

• Rounding mixture weights to multiples of 2^-ℓ changes the mixture law by total variation at most 2^-ℓ.The remaining mass is assigned to the other action, preserving a two-action mixture with bounded discretization error.Source: §A.2 · p. 33
• Modular combination sampling remains polynomial and yields an implemented core coefficient of at least β − 2^(1−ℓ), with error measured relative to P_h.All combinations remain feasible even when the induced sampling law is not exactly uniform.Source: §A.2 · p. 33

Random windows

• Random windows sampled with bitlength(B) + 2ℓ bits assign each window probability at most 1/B + 2^-2ℓ under fixed-time comparison.The window bits are independent of the core bits, and the fixed-time coupling does not accumulate error across completed checkpoints.Source: §A.2 · pp. 33–34

Resource bounds

• Choosing B = ⌈6/ε⌉ and 2^(1−ℓ) ≤ ε/2 bounds the total loss as required, while the pathwise bound is 8B^2 + 2.The implementation also avoids allocating k objects before the observed prefix is large enough, with conceptual dummy elements omitted from sets and oracle queries.Source: §A.2 · p. 34

• The method starts at x_i=κ/n, repeatedly moves toward the top-κ estimated-gradient coordinates, and stops when the estimated directional gain is at most ηM/2.Updates use x ← x + θ(y − x), deterministic tie-breaking, clipping to known nonnegative coordinate bounds, and a work cap.Source: §A.3 · p. 34
• Accurate gradient estimates make the stopping point’s true first-order gap at most 5ηM/8, while every nonstopping iteration improves the potential by a Hessian-controlled amount.The analysis assumes infinity-norm estimation error at most aM and converts it using the ℓ1 bound on feasible directions.Source: §A.3 · p. 34
• The potential’s bounded range excludes too many nonstopping iterations, so the procedure needs no global maximization of a nonconcave potential.The argument applies to the normalized scale, hybrid, and coverage potentials, with additional slack for the unnormalized scale potential.Source: §A.3 · p. 34
• Current-query estimators support the scale, hybrid, and coverage potentials, with the hybrid estimator adding the known modular weight and rescaling the scale component.Each hybrid random term uses two current queries and is bounded by 2M.Source: §A.3 · p. 35
• Fixed-bit discretization, dyadic exponential approximations, and Hoeffding sampling yield valid adaptive estimates with probability at least 1 − δ_fail and polynomial bit complexity.The implementation remains feasible even with inaccurate estimates and avoids rejection sampling with an unbounded number of trials.Source: §A.3 · p. 35

A.4 Rounding and the Hybrid Error Budget

• Mean-preserving pair rounding preserves expected multilinear value while producing feasible integral outcomes, with transition discretization contributing at most ρP_R loss.The rounding applies uniformly to every fixed future R and uses at most O(n + κ) rounding steps.Source: §A.4 · p. 35
• Choosing η = δ_fail = ρ = ε/64 and 2 − T ≤ ε/64 makes the static expected loss at most εP_R/16, with P_R ≤ OPT_k(f, X_t).The bound uses M ≤ P_R, g(O ∪ R) ≤ P_R, and the checkpoint condition κ + |R| ≤ k.Source: §A.4 · p. 35
• The explicit recourse bound is 8B2 + 2.Source: §A.4 · p. 35

A.5 Only Active Slot Bits Matter

• Rounding each slot probability to b bits yields per-draw total variation at most n2^-b ≤ ρ/κ when κn2^-b ≤ ρ.Unused probability mass is assigned to the null coordinate, and each draw uses exactly b bits.Source: §A.5 · p. 36
• Only the at most κ active slot draws need coupling, so their joint total variation is at most ρ and causes at most ρOPT_k(X_t) objective loss.There is no accumulation over past refreshes or future times, and approximate slot realizations preserve the pathwise insertion bound.Source: §A.5 · p. 36

A.6 Averaging Arbitrary Bounded Prices

• Lemma 4.2 averages arbitrary bounded, adaptive prices by projected updates on the capped simplex and then rounds a uniformly selected iterate without a union bound over futures.Exact rational water filling and nonexpansive projection establish the trajectory bound, while the same index-selection and rounding laws apply to every legal future.Source: §A.6 · p. 36
• When fixed-future responses are concave, the average iterate supplies the fractional core; otherwise Lemma 4.2 uses a randomly selected iterate, with deterministic price accuracy satisfying reliability.Power-of-two iteration enables log2 I unbiased bits, and dyadic probability approximations give a deterministic polynomial bit budget and at most τP_h loss.Source: §A.6 · pp. 36–37

A.7 The Finite-Capacity Gain

• For every integer κ ≥ 1, the mixture guarantees E h(A) ≥ βκ P h for every legal future.The guarantee follows from the existing LP and sampling law.Source: §A.7 · pp. 37–38
• Finite-capacity slack yields a strict improvement over β for every finite κ.For sufficiently large κ, the active branch approaches β with expansion 2 − 2/κ + O(κ^-2).Source: §A.7 · pp. 37–38
• The implemented static core inherits coefficient βκ − 2^(1−ℓ) from the total-variation calculation, while the uniform bound β supports all online guarantees.The finite-capacity corollary reuses the existing LP and sampling law.Source: §A.7 · p. 38

B Exact Rational Hard Instances

• The exact-rational hard-instance appendix supplies analytic and arithmetic bounds for the hardness lemmas and Proposition 3.2.Its final oracle uses fixed piecewise rational polynomials with exact indistinguishability at every finite k.Source: B Exact Rational Hard Instances · p. 38

B.1 Construction of the Exact Profiles

• The exact profiles fix rational T ∈ [7/5, 3/2] and integer m ≥ 32, together with scalar profiles v, w and constants b, c.The construction defines a = 1 + 1/m, u = x − y/m, t = ay, and s = x + y.Source: §B.1 · p. 38
• The unmodified profiles are F(x,y) = v(t) + uv′(t) + r_m(s) and K(x,y) = w(t) + uv′(t) + r_m(s).These expressions define the current and future profiles used in the construction.Source: §B.1 · p. 38
• The current expression is a tangent upper bound matching v(s) + r_m(s) in value and gradient at u = 0.Moreover, K − F = w(t) − v(t) is nonnegative and coordinatewise nonincreasing, ensuring a nonnegative decreasing marginal for the future element.Source: §B.1 · p. 38

B.1.1 Exact flattening and rational replacement

• Exact flattening yields C1 profiles with locally Lipschitz gradients, coordinate derivatives in [0, 4], and strict first- and second-derivative margins of 16e^-s/m.The profiles are monotone and have nonpositive second coordinate derivatives almost everywhere, including diagonal derivatives.Source: §B.1.1 · p. 39
• Certified rational profiles preserve the exact flat band, monotonicity, diminishing gradients, and cross-profile inequalities while approximating values and derivatives within 4τ.All coordinate gradients lie in [0, 5], and the rational profiles satisfy c Kδ ≥ bFδ and ∇c Kδ ≤ ∇bFδ.Source: §B.1.1 · pp. 39–40
• Exact flattening remains algebraic after rational replacement because the inner band has z = s and q = 0, independently of approximation accuracy.Taylor truncation retains the relevant sign margins, piecewise matching, regularity, and nonnegative future increment.Source: §B.1.1 · pp. 39–40

B.1.2 Validity on the full discrete ground set

• The resulting function is normalized, nonnegative, monotone, and submodular on all subsets of the full ground set, including sets exceeding maintained capacity.The proof covers finite differences whose coordinate intervals cross any number of clipping or profile-piece boundaries.Source: §B.1.2 · p. 40
• Five pairwise marginal checks—(A, A), (A, B), (B, B), (A, r), and (B, r)—establish diminishing returns using coordinate concavity and cross-future gradient inequalities.The marginal of r is nonnegative because c Kδ − bFδ is nonnegative.Source: §B.1.2 · p. 40
• Almost-everywhere derivative signs globalize across piecewise regions because continuous locally Lipschitz gradients are absolutely continuous and can be integrated along coordinate segments.This proves the discrete finite-difference inequalities on the normalized count grid, even when segments cross multiple boundaries.Source: §B.1.2 · p. 40

B.2 Derivative Margins and Piecewise Boundaries

• The derivative analysis gives final current gradients at least 22e^-s/m and Hessian entries at most −23e^-s/m, with future bounds 43e^-s/(2m) and −45e^-s/(2m).These stronger bounds imply the convenient 16e^-s/m margins and remain valid across clipping and profile junctions.Source: §B.2 · p. 41
• Cross-future compatibility satisfies ∂iFδ − ∂iKδ ≥ 16δe^-s for i = x, y, together with Kδ ≥ Fδ.The bounds follow by controlling tangent-point perturbations within δ and adding the future correction.Source: §B.2 · pp. 41–42

B.3 A Certified Finite Degree and Exact Arithmetic

• B.3 Exact rational tests certify degree D = O(m + log(1/τ)) without numerical exponential evaluations.The tests N ≥ 6L and 2N ≥ 3L/τ use exact rational arithmetic.Source: §B.3 · p. 42
• B.3 The polynomial tail has exactly the derivative signs required for all value, gradient, and Hessian calculations.The construction establishes E_D−j(h) > 0 for j = 0, 1, 2, 3 throughout the relevant interval.Source: §B.3 · p. 42
• B.3 Polynomial-replacement errors remain below the analytic sign margins, preserving the required gradient, Hessian, boundary, and monotonicity inequalities.The upper gradient bound is 4 + 4τ < 5, while continuity and absolute continuity extend the inequalities across piecewise boundaries.Source: §B.3 · p. 43
• B.3 Exact tail signs also prove the future-value inequality, concavity, nonnegativity, and the comparison c K_δ ≥ b F_δ.The flat-band identity is exact independently of approximation error.Source: §B.3 · p. 43
• B.3 With fixed parameters, the oracle returns canonical rational answers of O_ζ(log n) bits and computes them in polynomial time given A.All coefficients and breakpoints are fixed rationals chosen before the hidden partition, so the construction is a rational value oracle rather than rounded real-valued answers.Source: §B.3 · p. 43

B.4 Concentration, Adaptive Transcripts, and Parameter Order

• B.4 Hoeffding concentration applies to every fixed query set, including infeasible queries, because the hidden marked set is sampled without replacement.For a fixed query S, Z = |A ∩ S| counts marked identifiers among a uniformly sampled k-subset.Source: §B.4 · p. 44
• B.4 Conditioning on the algorithm’s random tape couples adaptive reference and actual executions except with probability 2(Q + 1)e^(−δ^2k/2), while allowing unlimited post-arrival queries.Averaging over random tapes and hidden sets produces a fixed hard instance with the claimed expected ratio and the same optimum across hidden instances.Source: §B.4 · p. 44
• B.4 A fixed gap ζ over β requires either exponentially many pre-arrival queries or Ω(k) final-update changes, with exponential complexity also in n for fixed ζ.The parameters are fixed independently of k, the hidden set, and the algorithm’s randomness; n = Θ_ζ(k).Source: §B.4 · p. 44

B.5 Expected Resources and Almost-Sure Termination

• Almost-sure termination lets the lower-bound argument replace deterministic query and running-time caps with finite-transcript coupling and limiting computation caps.The reference execution terminates almost surely, while the hard-family argument uses a truncated simulation and then sends the computation cap to infinity.Source: §B.5 · pp. 44–45, The infimum is at most 2 · pp. 45–46

The infimum is at most 2

• A fixed improvement over β requires linear expected final recourse or exponentially many expected pre-arrival queries, even when post-arrival queries and computation are unrestricted.Proposition B.4 establishes this under almost-sure termination and expected resource bounds on the finite hard family.Source: §B.5 · p. 45, The infimum is at most 2 · p. 46

C Principal Prices with Persistent Matroid-Rank Access

• The access model exposes persistent component identifiers, rational weights, and rank oracles, making aggregate evaluation polynomial in the stated input parameters and stronger than hidden MRS access.The same full matroid identifier exposes its restriction after each arrival.Source: C Principal Prices with Persistent… · p. 46

C.2 A Certificate for Every Future Contraction

• The universal principal-price certificate proves that current prices certify every fixed future contraction, enabling a current-only implementation without recomputing the principal partition.The certificate’s robustness comes from the principal-price inequality rather than maximizing the ordinary current Poisson value.Source: C Principal Prices with Persistent… · p. 46, §C.2 · pp. 49–51

C Principal Prices with Persistent Matroid-Rank Access

• In the persistent matroid-rank access model, every rational ε in (0, α0) admits a randomized polynomial-time (α0−ε)-approximation with hard symmetric recourse at most 4⌈2/ε⌉+2.A fixed polynomial-time improvement above α0 would imply NP ⊆ BPP.Source: C Principal Prices with Persistent… · p. 47

C.1 The Current Principal Partition

• The current principal partition forms a flat chain with nonincreasing densities and block base points, yielding current-only supergradient prices gi = e−qj.The prices remain valid at zero coordinates, where differentiability may fail, and support the principal-partition upper bound on the Poisson extension.Source: §C.1 · pp. 47–48

C.2 A Certificate for Every Future Contraction

• For every future contraction, a common-extension domination lemma supplies a contracted base point bounded by the current block base point.This transfers current block-level rank guarantees to contracted matroids, including overlaps handled by retaining intersecting elements as loops.Source: §C.2 · pp. 49–50

C.3 Exact Current-Rank Computation and the Online Theorem

• Polynomially many submodular minimizations recover each exact maximum-density block by binary search, rational reconstruction, and a perturbation selecting its unique maximal minimizer.The reduced denominator is at most n, and searching below width 1/(8n^2) identifies the density uniquely; contraction and repetition require at most n blocks.Source: §C.3 · p. 51
• poly(n, m, bit length) component-rank calls suffice, because rational objectives are denominator-cleared before minimization and no oracle call recovers an aggregate decomposition.Projection, reconstruction, averaging updates, and weighted price arithmetic all have polynomial bit complexity in the represented input and requested precision.Source: §C.3 · pp. 51–52
• Maximum coverage is represented as explicit rank-one matroids per atom, yielding conditional computational optimality without hardness for unknown-decomposition recovery or a new recourse lower bound.The conclusion follows from the final-output reduction from Theorem 6.1.Source: §C.3 · p. 52