11 papers
Analysis of Polynomial Threshold Functions on Random Regular Graphs: Computational Complexity of Detecting Noisy Random Lifts
Xifan Yu
In this work, we present the first analysis of low-degree polynomial threshold functions for the natural hypothesis testing problem of detecting the noisy random lift of a base …
Inequalities for rank-two permanents and finite free convolutions
Dmitriy Kunisky, Daniel A. Spielman, Xifan Yu
Bang (1976) proved the inequality for matrix permanents , where is the all-ones matrix and is any…
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…
Inference of rankings planted in random tournaments
Dmitriy Kunisky, Daniel A. Spielman, Xifan Yu
We consider the problem of inferring an unknown ranking of items from a random tournament on vertices whose edge directions are correlated with the ranking. We establish, i…
Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
Dmitriy Kunisky, Xifan Yu
We introduce a new conjecture on the computational hardness of detecting random lifts of graphs: we claim that there is no polynomial-time algorithm that can distinguish between a…
Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph
Xifan Yu, Ilias Zadik, Peiyuan Zhang
We study the computational limits of the following general hypothesis testing problem. Let H=H_n be an \emph{arbitrary} undirected graph on n vertices. We study the detection task…
A degree 4 sum-of-squares lower bound for the clique number of the Paley graph
Dmitriy Kunisky, Xifan Yu
We prove that the degree 4 sum-of-squares (SOS) relaxation of the clique number of the Paley graph on a prime number of vertices has value at least . This is in con…