1 citations · 5 across the 13 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2026
Rigorous Implications of the Low-Degree Heuristic
Jun-Ting Hsieh, Daniel M. Kane, Pravesh K. Kothari +3
Over the past decade, the low-degree heuristic has been used to estimate the algorithmic thresholds for a wide range of average-case planted vs null distinguishing problems. Such r…
cs.CC2024★ 1 cited
Improved Hardness Results for Learning Intersections of Halfspaces
Stefan Tiegel
We show strong (and surprisingly simple) lower bounds for weakly learning intersections of halfspaces in the improper setting. Strikingly little is known about this problem. For in…