4 papers
Masked Erosion: How Acceptance Gates Lose Redundant Safeguards in Self-Improving Agents
Hau-Sing So, Daixian Liu, Weicai Long
Self-improving LLM agents edit their own harness, the prompts and rules around a fixed model, and keep an edit only if an acceptance gate scores it higher on a batch of tasks. Such…
Integrality-Gap Bounds for Weighted Matchoids and Matroid Intersection
Yu Cong, Yajie Zhao
The weighted -matroid intersection problem asks for a maximum-weight set that is independent in each of matroids on a common ground set. The natural LP relaxation optimizes…
Large-Scale Trade-Off Curve Computation for Incentive Allocation with Cardinality and Matroid Constraints
Yu Cong, Chao Xu, Yi Zhou
We consider a large-scale incentive allocation problem where the entire trade-off curve between budget and profit has to be maintained approximately at all times. The application o…
Derandomizing Karger's Contraction Algorithm for Matroids
Yu Cong, Chao Xu, Yajie Zhao
Karger's randomized contraction algorithm finds a minimum-weight cocircuit of a matroid whenever the cogirth-density ratio is bounded. We prove that the same hypothesis yields a de…