4 papers
Approximate Replicability in Learning
Max Hopkins, Russell Impagliazzo, Christopher Ye
Replicability, introduced by (Impagliazzo et al. STOC '22), is the notion that algorithms should remain stable under a resampling of their inputs (given access to shared randomness…
Non-Signaling Locality Lower Bounds for Dominating Set
Noah Fleming, Max Hopkins, Yuichi Yoshida
Minimum dominating set is a basic local covering problem and a core task in distributed computing. Despite extensive study, in the classic LOCAL model there exist significant gaps…
High Rate Efficient Local List Decoding from HDX
Yotam Dikstein, Max Hopkins, Russell Impagliazzo +1
We construct the first (locally computable, approximately) locally list decodable codes with rate, efficiency, and error tolerance approaching the information theoretic limit, a co…
From Generative to Episodic: Sample-Efficient Replicable Reinforcement Learning
Max Hopkins, Sihan Liu, Christopher Ye +1
The epidemic failure of replicability across empirical science and machine learning has recently motivated the formal study of replicable learning algorithms [Impagliazzo et al. (2…