1 citations · 1 across the 4 of their papers we have counts for
4 papers
Graph Quasirandomness for Hypothesis Testing of Stochastic Block Models
Kiril Bangachev, Guy Bresler
The celebrated theorem of Chung, Graham, and Wilson on quasirandom graphs implies that if the 4-cycle and edge counts in a graph are both close to their typical number in $\mat…
Partial and Exact Recovery of a Random Hypergraph from its Graph Projection
Guy Bresler, Chenghao Guo, Yury Polyanskiy +1
Consider a -uniform random hypergraph on vertices in which hyperedges are included iid so that the average degree is . The projection of a hypergraph is a graph on the…
Thresholds for Reconstruction of Random Hypergraphs From Graph Projections
Guy Bresler, Chenghao Guo, Yury Polyanskiy
The graph projection of a hypergraph is a simple graph with the same vertex set and with an edge between each pair of vertices that appear in a hyperedge. We consider the problem o…
Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations
Kiril Bangachev, Guy Bresler, Stefan Tiegel +1
We present a polynomial-time reduction from solving noisy linear equations over in dimension with a un…