Showing 2025Show all
3 papers · 1 filter
cs.CC2025
New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String
Lijie Chen, Yang Hu, Hanlin Ren
The *algebrization barrier*, proposed by Aaronson and Wigderson (STOC '08, ToCT '09), captures the limitations of many complexity-theoretic techniques based on arithmetization. Not…
cs.DS2025
Static Retrieval Revisited: To Optimality and Beyond
Yang Hu, William Kuszmaul, Jingxun Liang +3
In the static retrieval problem, a data structure must answer retrieval queries mapping a set of keys in a universe to -bit values. Information-theoretically, retrieva…
cs.DS2025
Nearly Optimal Bounds for Stochastic Online Sorting
Yang Hu
In the online sorting problem, we have an array of cells, and receive a stream of items . When an item arrives, we need to immediately and irrev…