A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over 2-sqrt 2 Entails Exponential Queries or Linear Recourse
cs.DS, cs.LG
Submitted: 2026-09-09
Updated: 2026-09-09
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Terminology
Related papers
- Cascaded Learned Bloom Filter for Optimizing Model-Filter Size Balance and Fast Rejection
- Computational and Statistical Hardness of Calibration Distance
- Edge-Private Matching Kernels Through Local Decoding
- Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples
- Local Node Differential Privacy
- Cheaper by the Batch: Shared Traversal for Genotype Graph Editing