5 papers
Strong Refutation of Random Ordering CSPs
Xifan Yu
In this work, we initiate the study of strongly refuting the satisfiability of random ordering constraint satisfaction problems. We show that there is a polynomial-time $\varepsilo…
Differentially Private Language Generation and Identification in the Limit
Anay Mehrotra, Grigoris Velegkas, Xifan Yu +1
We initiate the study of language generation in the limit, a model recently introduced by Kleinberg and Mullainathan [KM24], under the constraint of differential privacy. We consid…
Stable Algorithms Lower Bounds for Estimation
Xifan Yu, Ilias Zadik
In this work, we show that for all statistical estimation problems, a natural MMSE instability (discontinuity) condition implies the failure of stable algorithms, serving as a vers…
Language Generation with Infinite Contamination
Anay Mehrotra, Grigoris Velegkas, Xifan Yu +1
We study language generation in the limit, where an algorithm observes an adversarial enumeration of strings from an unknown target language and must eventually generate new, u…
Statistical inference of a ranked community in a directed graph
Dmitriy Kunisky, Daniel A. Spielman, Alexander S. Wein +1
We study the problem of detecting or recovering a planted ranked subgraph from a directed graph, an analog for directed graphs of the well-studied planted dense subgraph model. We…