6 citations · 12 across the 9 of their papers we have counts for
Showing 2021Show all
2 papers · 1 filter
cs.DS2021★ 4 cited
Perfect Sampling for (Atomic) Lovász Local Lemma
Kun He, Xiaoming Sun, Kewen Wu
We give a Markov chain based perfect sampler for uniform sampling solutions of constraint satisfaction problems (CSP). Under some mild Lovász local lemma conditions where each cons…
cs.CC2021
Fourier Growth of Parity Decision Trees
Uma Girish, Avishay Tal, Kewen Wu
We prove that for every parity decision tree of depth on variables, the sum of absolute values of Fourier coefficients at level is at most $d^{\ell/2} \cdot O(\ell \…