An Improved Lower Bound for Matroid Intersection Prophet inequalities
summary
Proves an improved impossibility: the prophet inequality for an intersection of q partition matroids is at least q^{1/2+1/\log\log q} (so super-√q). Uses the KW12 p^p groups framework (groups of p Bernoulli boxes so offline ≈ p, online only constant) and shows the group-feasibility can be written as an intersection of q = about p^{2-1/\log\log p} partition matroids. Main construction builds a p^p family of vectors by recursive concatenation and scaling operations and plugs in an AA20 combinatorial lemma to trim length; the construction is explicit and yields the claimed lower bound, leaving the polynomial gap to upper bounds open.
AI-written summary · about
chapters (11)
- 0:00Prophet inequalities intro
- 3:51Matroid intersection bounds
- 6:48Improved lower bound
- 9:42Proof framework
- 11:26Partition matroids
- 13:12Forward matroid construction
- 16:00Backward vector reformulation
- 18:10Covering family construction
- 21:43Recursive family construction
- 23:10Optimizing parameters
- 25:13Conclusion
related talks
30mParameterized Inapproximability of Max k-Subset Intersection under ETH
31mConstructive Algorithm for Matroid Pathwidth
01h 02mFine-Grained Counting Complexity I
31mNew Unconditional Lower Bounds for Algorithms and Enumeration Problems
26mLower Bounds on the Running Time for Scheduling and Packing Problems
A Formal Disproof of Hirsch Conjecture
01h 02mFine-Grained Counting Complexity II
28mSettling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams