Yitong Yin

activity

20062023

most citedSpatial mixing and approximation algorithms for graphs with bounded connective constant

37 citations · 120 across the 35 of their papers we have counts for

collaborators

Showing 2016Show all

3 papers · 1 filter

cs.DM2016★ 5 cited

Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model

Charilaos Efthymiou, Thomas P. Hayes, Daniel Stefankovic +2

We study the hard-core model defined on independent sets of an input graph where the independent sets are weighted by a parameter $λ > 0$ . For constant $Δ$ , previous work of Weitz (2…

cs.DS2016★ 3 cited

Randomized approximate nearest neighbor search with limited adaptivity

Mingmou Liu, Xiaoyin Pan, Yitong Yin

We study the fundamental problem of approximate nearest neighbor search in $d$ -dimensional Hamming space ${0, 1}^{d}$ . We study the complexity of the problem in the famous cell-prob…

cs.DS2016★ 3 cited

Simple average-case lower bounds for approximate near-neighbor from isoperimetric inequalities

Yitong Yin

We prove an $Ω (d / lo g \frac{s w}{n d})$ lower bound for the average-case cell-probe complexity of deterministic or Las Vegas randomized algorithms solving approximate near-neighbor (…