6 papers
Nearly Optimal Internal Dictionary Matching
Jingbang Chen, Jiangqi Dai, Qiuyang Mang +2
We study the internal dictionary matching (IDM) problem where a dictionary containing substrings of a text is given, and each query concerns the occurrences o…
Resizable Retrieval
William Kuszmaul, Aaron Putterman, Tingqiang Xu +2
A dynamic retrieval data structure encodes a function for a set , while supporting queries for , insertions \texttt{Insert}$…
Beyond Problem Solving: UOJ-Bench for Evaluating Code Generation, Hacking, and Repair in Competitive Programming
Tingqiang Xu, Hangrui Zhou, Tianle Cai +2
Despite strong performance in competitive programming, the role of Large Language Models (LLMs) in supporting human learning in the same setting remains largely unexplored. In this…
Low-probability Tokens Sustain Exploration in Reinforcement Learning with Verifiable Reward
Guanhua Huang, Tingqiang Xu, Mingze Wang +7
Reinforcement Learning with Verifiable Rewards (RLVR) has propelled Large Language Models in complex reasoning, yet its scalability is often hindered by a training bottleneck where…
Reinforcement Learning on Pre-Training Data
Siheng Li, Kejiao Li, Zenan Xu +33
The growing disparity between the exponential scaling of computational resources and the finite growth of high-quality text data now constrains conventional scaling approaches for…
Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval
William Kuszmaul, Aaron Putterman, Tingqiang Xu +2
Retrieval data structures are data structures that answer key-value queries without paying the space overhead of explicitly storing keys. The problem can be formulated in four sett…