4 papers
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…
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…
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…
Optimal Static Dictionary with Worst-Case Constant Query Time
Yang Hu, Jingxun Liang, Huacheng Yu +2
In this paper, we design a new succinct static dictionary with worst-case constant query time. A dictionary data structure stores a set of key-value pairs with distinct keys in $[U…