22 papers
Allocation Before the Clock: Graph, Set and Game Theory of Professional League of Legends Objective Setups
Zheng Gao, Zhenyu Liu, Yifan Yang +1
Before every neutral objective in professional League of Legends, each team decides which of its five players walk to the pit, which hold a lane, and when to commit. The leading an…
Learning a Group Element from Its Action: Galois Correspondences, Optimal ERM, and an Abel-Ruffini Threshold for the Natarajan Dimension
Xiaoyu Li
We study learning an unknown element of a group acting with finite orbits on a countable set, from examples . After a sample on , the consistent hypotheses are the r…
CoRA-NAS: Coarse Ranking and Anchor-Residual Refinement for Neural Architecture Search
Yifan Yang, Zhaoyan Wang, Zheng Gao +2
Zero-cost proxies rank architectures cheaply, but their reliability varies across search spaces. We introduce CoRA-NAS (COarse Ranking + Anchor-residual), a two-stage framework com…
Characterizing Language Generation in the Limit: Finite Witnesses and a Separation-Width Hierarchy
Xiaoyu Li, Andi Han, Jiaojiao Jiang +1
Language generation in the limit asks for valid unseen elements from every exhaustive positive presentation of an unknown infinite language. We characterize this task for arbitrary…
TrajMark: Ownership Attribution and Segment-Level Tamper Localization for Coding-Agent Trajectories
Bokang Zeng, Zheng Gao, Xiaoyu Li +2
Watermarking the final patch produced by a coding agent provides provenance evidence for the submitted artifact, but does not authenticate the visible process that produced it. Beh…
Nearly Tight Rademacher Bounds for Sparsely Activated Neural Networks
Xiaoyu Li, Zhizhou Sha, Jiaojiao Jiang +2
An input may activate few hidden units even when different inputs collectively use an entire network. We study the statistical complexity of this input-dependent sparsity in the on…
DRIFT: Removing Diffusion Watermarks by Deflecting the Generative Trajectory
Rui Bao, Zheng Gao, Xiaoyu Li +3
Diffusion watermarking embeds verifiable signals into the generative process and commonly verifies them by recovering trajectory-dependent evidence, making the marks robust to conv…
IRIS: Visual-Semantic Binding for Forgery-Resistant Watermarking of Diffusion Images
Xiaoyan Feng, Zheng Gao, Tong Guan +4
Most in-generation diffusion watermarks embed patterns independent of the image that carries them, and attackers transplant the marks onto images the generator did not produce, res…
Optimistic Rates for Multiclass PAC Learning
Xiaoyu Li, Andi Han, Jiaojiao Jiang +1
Worst-case multiclass bounds do not become smaller when the best classifier is already nearly correct: what is missing is an optimistic rate, a guarantee whose fluctuation scales w…
On Computational Hardness of Mistake-Bounded Language Generation: A Random-Oracle Query Separation
Xiaoyu Li, Andi Han, Dai Shi +2
Generation in the limit guarantees eventual generation for every countable collection of infinite languages in the model of Kleinberg and Mullainathan [KM24], while closure dimensi…
Watermark Forensics for Generative Models: An Information-Theoretic Perspective
Xiaoyu Li, Zheng Gao, Xiaoyan Feng +3
A watermark in a generative model's output is usually asked only whether a text is machine-made. The same mark can do more: attribute it to the user who produced it, extract a hidd…
TRACE: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories
Zheng Gao, Xiaoyu Li, Xiaoyan Feng +5
LLM agents reach users through resellers, who may rebrand a developer's agent or substitute a cheaper model. When provenance is disputed, attribution rests on the trajectory log (t…
The Exact Worst-Case Tail Probability under Bounded Kurtosis
Xiaoyu Li, Andi Han, Jiaojiao Jiang +1
We determine exactly what a kurtosis bound buys for one-sided tail control. For the class of real random variables with mean , variance , and fourth moment a…
Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model
Xiaoyu Li, Junwei Yu, Jiaojiao Jiang +2
The John ellipsoid of a symmetric polytope , , is computed by a long line…
Flood and Harvest: The Provable Necessity of Trivia for Generating Valuable Mathematics via the Lens of Language Generation in the Limit
Xiaoyu Li, Andi Han, Dai Shi +3
AI systems coupled to proof assistants now generate formal mathematics at scale, and the gap between what a checker can verify and what a mathematician would value has become the b…
Contrastive Identification and Generation in the Limit
Xiaoyu Li, Andi Han, Jiaojiao Jiang +1
In the classical identification in the limit model of Gold [1967], a stream of positive examples is presented round by round, and the learner must eventually recover the target hyp…
On the Price of Privacy for Language Identification and Generation
Xiaoyu Li, Andi Han, Jiaojiao Jiang +1
As large language models (LLMs) are increasingly trained on sensitive user data, understanding the fundamental cost of privacy in language learning becomes essential. We initiate t…
LAVA: Layered Audio-Visual Anti-tampering Watermarking for Robust Deepfake Detection and Localization
Bokang Zeng, Zheng Gao, Xiaoyu Li +2
Proactive watermarking offers a promising approach for deepfake tamper detection and localization in short-form videos. However, existing methods often decouple audio and visual ev…
SHIFT: Stochastic Hidden-Trajectory Deflection for Removing Diffusion-based Watermark
Rui Bao, Zheng Gao, Xiaoyu Li +3
Diffusion-based watermarking methods embed verifiable marks by manipulating the initial noise or the reverse diffusion trajectory. However, these methods share a critical assumptio…
SLICE: Semantic Latent Injection via Compartmentalized Embedding for Image Watermarking
Zheng Gao, Yifan Yang, Xiaoyu Li +4
Watermarking the initial noise of diffusion models has emerged as a promising approach for image provenance, but content-independent noise patterns can be forged via inversion and…
Breaking Semantic-Aware Watermarks via LLM-Guided Coherence-Preserving Semantic Injection
Zheng Gao, Xiaoyu Li, Zhicheng Bao +2
Generative images have proliferated on Web platforms in social media and online copyright distribution scenarios, and semantic watermarking has increasingly been integrated into di…
Implicit Hypergraph Neural Networks: A Stable Framework for Higher-Order Relational Learning with Provable Guarantees
Xiaoyu Li, Guangyu Tang, Jiaojiao Jiang
Many real-world interactions are group-based rather than pairwise such as papers with multiple co-authors and users jointly engaging with items. Hypergraph neural networks have sho…