Parallel algorithm for matroid basis computation with O(n^{1/3} log^{1/3} n) round complexity, nearly matching the KUW lower bound.
hub Canonical reference
Rodrigo Nogueira, Zhiying Jiang, Ronak Pradeep, and Jimmy Lin
Canonical reference. 80% of citing Pith papers cite this work as background.
21
Pith papers citing it
2,925
external citations · Crossref
Background
80% of classified citations
hub tools
citation-role summary
background 4
method 1
citation-polarity summary
years
2026 21representative citing papers
Extending curvature to all submodular functions yields the first multiplicative greedy approximation guarantees that apply even when the function takes negative values.
Develops polynomial-time algorithms achieving competitive ratios of ~1/14.85 (general) and 1/6.86 (unit costs) for submodular welfare maximization with budgets under random-order item arrival.
A new algorithm finds a matroid basis in tilde O(n to the 3/7) adaptive rounds via independence oracle.
ContextualJailbreak uses evolutionary search over simulated primed dialogues with novel mutations to reach 90-100% attack success on open LLMs and transfers to some closed frontier models at 15-90% rates.
A covariance-adapting algorithm for semi-bandits achieves asymptotically tight regret bounds under a new sub-exponential distribution family, with direct application to sparse rewards.
Optimal layer-patching order for boomerang distillation is a shortest path on a KL-weighted Boolean lattice; greedy KLPatch and simple sequential orders often yield near-optimal interpolations.
EnvProbe, a budgeted structural scoring policy for environment queries, raises terminal world-state accuracy over periodic probing by 6.45 points overall, mainly via criticality and dependency cues rather than verbalized uncertainty.
Adaptive scaling algorithm achieves 1.373 competitive ratio for incremental submodular maximization, improving on greedy's 1.582 with a 1.25 lower bound.
Presents the Cascade Log, a reference-stable tiered append structure using a coalescing interval map for handles, with Θ(A) space, O(log A) point resolution, and sublinear cost on append-dominated histories where A is the fragmentation measure.
Multi-response training retains multiple responses per prompt to reduce uncertainty about the conditional output distribution, yielding improved distributional generalization especially in high response-diversity and low prompt-redundancy regimes.
SeedER uses initial dense seeding followed by RL-driven selective expansion to improve recall on compositional KG queries while limiting candidate set size.
SkillLens organizes skills into policies-strategies-procedures-primitives layers, retrieves via degree-corrected random walk, and uses a verifier for local adaptation, yielding up to 6.31 pp gains on MuLocbench and raising ALFWorld success from 45% to 51.31%.
MechaRule localizes sparse agonist neurons via contrastive hierarchical ablation and adaptive group testing to ground rule extraction, recalling 97% of high-effect activations at 2.14% cost while enabling near-total elimination of target behaviors.
A reformulation of Bayesian OED as dense matrix subset selection plus a pipelined Schur-complement greedy algorithm on hundreds of GPUs enables optimization of 175-sensor networks for billion-degree-of-freedom tsunami models with near-perfect scaling.
A question-adaptive greedy frame selector combines SigLIP relevance and DINOv2 coverage under a submodular objective with a text classifier routing to preset trade-offs, yielding accuracy gains on MLVU especially at low frame budgets.
Revenue maximization for pricing datasets to budget-constrained buyers is APX-hard, with a 2-approximation for online arrivals and a (1-1/e)^{-1}-approximation for offline.
Selective prediction abstains unless all Lipschitz-consistent heads in the version space agree on a certified label for each pool point.
RCD balances relevance, coverage, and diversity in a knapsack-constrained selection framework, with experiments showing that selector choice and budget level determine optimal unitization strategies on clinical datasets.
Empirical tests on three real networks show Shapley-value node selection for coverage under reachability rules reaches ~0.9 approximation ratio and beats degree baseline, with one case covering half of Cora using 26 nodes.
citing papers explorer
-
A Near-Optimal Parallel Algorithm for Finding Matroid Bases
Parallel algorithm for matroid basis computation with O(n^{1/3} log^{1/3} n) round complexity, nearly matching the KUW lower bound.
-
Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions
Extending curvature to all submodular functions yields the first multiplicative greedy approximation guarantees that apply even when the function takes negative values.
-
Submodular Welfare Maximization with Budget Constraints in the Random-Order Model
Develops polynomial-time algorithms achieving competitive ratios of ~1/14.85 (general) and 1/6.86 (unit costs) for submodular welfare maximization with budgets under random-order item arrival.
-
An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
A new algorithm finds a matroid basis in tilde O(n to the 3/7) adaptive rounds via independence oracle.
-
ContextualJailbreak: Evolutionary Red-Teaming via Simulated Conversational Priming
ContextualJailbreak uses evolutionary search over simulated primed dialogues with novel mutations to reach 90-100% attack success on open LLMs and transfers to some closed frontier models at 15-90% rates.
-
Covariance-adapting algorithm for semi-bandits with application to sparse rewards
A covariance-adapting algorithm for semi-bandits achieves asymptotically tight regret bounds under a new sub-exponential distribution family, with direct application to sparse rewards.
-
Understanding Layer Patching in Model Size Interpolation
Optimal layer-patching order for boomerang distillation is a shortest path on a KL-weighted Boolean lattice; greedy KLPatch and simple sequential orders often yield near-optimal interpolations.
-
Ask the World Before Acting: Environment Probing for Calibrated Agent World Models
EnvProbe, a budgeted structural scoring policy for environment queries, raises terminal world-state accuracy over periodic probing by 6.45 points overall, mainly via criticality and dependency cues rather than verbalized uncertainty.
-
Incremental Submodular Maximization: Better Than Greedy
Adaptive scaling algorithm achieves 1.373 competitive ratio for incremental submodular maximization, improving on greedy's 1.582 with a 1.25 lower bound.
-
The Cascade Log: Reference-Stable Windowing over Tiered Append Sequences
Presents the Cascade Log, a reference-stable tiered append structure using a coalescing interval map for handles, with Θ(A) space, O(log A) point resolution, and sublinear cost on append-dominated histories where A is the fragmentation measure.
-
Escaping the Mode Lottery: Multi-Response Training Improves Language Model Generalization
Multi-response training retains multiple responses per prompt to reduce uncertainty about the conditional output distribution, yielding improved distributional generalization especially in high response-diversity and low prompt-redundancy regimes.
-
SeedER: Seed-and-Expand Retrieval from Knowledge Graphs
SeedER uses initial dense seeding followed by RL-driven selective expansion to improve recall on compositional KG queries while limiting candidate set size.
-
SkillLens: Adaptive Multi-Granularity Skill Reuse for Cost-Efficient LLM Agents
SkillLens organizes skills into policies-strategies-procedures-primitives layers, retrieves via degree-corrected random walk, and uses a verifier for local adaptation, yielding up to 6.31 pp gains on MuLocbench and raising ALFWorld success from 45% to 51.31%.
-
Neuron-Anchored Rule Extraction for Large Language Models via Contrastive Hierarchical Ablation
MechaRule localizes sparse agonist neurons via contrastive hierarchical ablation and adaptive group testing to ground rule extraction, recalling 97% of high-effect activations at 2.14% cost while enabling near-total elimination of target behaviors.
-
Sensor Placement for Tsunami Early Warning via Large-Scale Bayesian Optimal Experimental Design
A reformulation of Bayesian OED as dense matrix subset selection plus a pipelined Schur-complement greedy algorithm on hundreds of GPUs enables optimization of 175-sensor networks for billion-degree-of-freedom tsunami models with near-perfect scaling.
-
Adaptive Greedy Frame Selection for Long Video Understanding
A question-adaptive greedy frame selector combines SigLIP relevance and DINOv2 coverage under a submodular objective with a text classifier routing to preset trade-offs, yielding accuracy gains on MLVU especially at low frame budgets.
-
Revenue-Optimal Pricing for Budget-Constrained Buyers in Data Markets
Revenue maximization for pricing datasets to budget-constrained buyers is APX-hard, with a 2-approximation for online arrivals and a (1-1/e)^{-1}-approximation for offline.
-
Selective Prediction from Agreement: A Lipschitz-Consistent Version Space Approach
Selective prediction abstains unless all Lipschitz-consistent heads in the version space agree on a certified label for each pool point.
-
Budget-Aware Routing for Long Clinical Text
RCD balances relevance, coverage, and diversity in a knapsack-constrained selection framework, with experiments showing that selector choice and budget level determine optimal unitization strategies on clinical datasets.
-
Sphere of Influence Centrality via Shapley Values: Empirical Approximation and Network Coverage Analysis
Empirical tests on three real networks show Shapley-value node selection for coverage under reachability rules reaches ~0.9 approximation ratio and beats degree baseline, with one case covering half of Cora using 26 nodes.
- Connections Between Determinantal Point Processes and Gramians in Control