1 citations · 1 across the 6 of their papers we have counts for
4 papers · 1 filter
Private Learning of Littlestone Classes, Revisited
Xin Lyu
We consider online and PAC learning of Littlestone classes subject to the constraint of approximate differential privacy. Our main result is a private learner to online-learn a Lit…
Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case
Venkatesan Guruswami, Xin Lyu, Weiqiang Yuan
A recent work (Korten, Pitassi, and Impagliazzo, FOCS 2025) established an insightful connection between static data structure lower bounds, range avoidance of circui…
Trade-offs in Data Memorization via Strong Data Processing Inequalities
Vitaly Feldman, Guy Kornowski, Xin Lyu
Recent research demonstrated that training large language models involves memorization of a significant fraction of training data. Such memorization can lead to privacy violations…
More efficient sifting for grid norms, and applications to multiparty communication complexity
Zander Kelley, Xin Lyu
Building on the techniques behind the recent progress on the 3-term arithmetic progression problem \cite{KelleyM2023strong}, Kelley, Lovett, and Meka \cite{KelleyLM2024-nof} constr…