6 papers
A Unified Lower Bound on the Noisy Query Complexity of Boolean Functions
Yuzhou Gu, Xin Li, Yinzhan Xu
We study the query complexity of Boolean functions in the noisy query model introduced by Feige, Raghavan, Peleg and Upfal [SICOMP 1994]. In th…
Local Urysohn Width: A Topological Complexity Measure for Classification
Xin Li
We introduce \emph{local Urysohn width}, a complexity measure for classification problems on metric spaces. Unlike VC dimension, fat-shattering dimension, and Rademacher complexity…
When Relaxation Does Not Help: RLDCs with Small Soundness Yield LDCs
Kuan Cheng, Xin Li, Songtao Mao
Locally decodable codes (LDCs) are error correction codes that allow recovery of any single message symbol by probing only a small number of positions from the (possibly corrupted)…
Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold
Yuzhou Gu, Xin Li, Yinzhan Xu
In the noisy query model, the (binary) return value of every query (possibly repeated) is independently flipped with some fixed probability . In this paper, we obta…
Improved Explicit Near-Optimal Codes in the High-Noise Regimes
Xin Li, Songtao Mao
We study uniquely decodable codes and list decodable codes in the high-noise regime, specifically codes that are uniquely decodable from fraction of error…
Improved Condensers for Chor-Goldreich Sources
Jesse Goodman, Xin Li, David Zuckerman
One of the earliest models of weak randomness is the Chor-Goldreich (CG) source. A -CG source is a sequence of random variables , where…