12 citations · 21 across the 7 of their papers we have counts for
Showing cs.DSShow all
2 papers · 1 filter
cs.DS2022
Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models
Ilias Diakonikolas, Daniel M. Kane, Yuxin Sun
We establish optimal Statistical Query (SQ) lower bounds for robustly learning certain families of discrete high-dimensional distributions. In particular, we show that no efficient…
cs.DS2017★ 5 cited
What can be sampled locally?
Weiming Feng, Yuxin Sun, Yitong Yin
The local computation of Linial [FOCS'87] and Naor and Stockmeyer [STOC'93] concerns with the question of whether a locally definable distributed computing problem can be solved lo…