4 citations · 7 across the 7 of their papers we have counts for
9 papers
Primal/Dual Method for the Grothendieck Constant
Steven Heilman, Chris Jones, Giulio Malavolta
We determine the hundredths digit of the real Grothendieck constant by proving . Furthermore, numerical heuristics suggest the estimate $K_G \approx 1.7…
Deterministic counting Lovász local lemma beyond linear programming
Kun He, Chunyang Wang, Yitong Yin
We give a simple combinatorial algorithm to deterministically approximately count the number of satisfying assignments of general constraint satisfaction problems (CSPs). Suppose t…
Improved Bounds for Sampling Solutions of Random CNF Formulas
Kun He, Kewen Wu, Kuan Yang
Let be a random -CNF formula on variables and clauses, where each clause is a disjunction of literals chosen independently and uniformly. Our goal is to sample a…
Sampling Lovász Local Lemma For General Constraint Satisfaction Solutions In Near-Linear Time
Kun He, Chunyang Wang, Yitong Yin
We give a fast algorithm for sampling uniform solutions of general constraint satisfaction problems (CSPs) in a local lemma regime. Suppose that the CSP has variables with doma…
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…
Dynamic inference in probabilistic graphical models
Weiming Feng, Kun He, Xiaoming Sun +1
Probabilistic graphical models, such as Markov random fields (MRFs), are useful for describing high-dimensional distributions in terms of local dependence structures. The probabili…
Null-free False Discovery Rate Control Using Decoy Permutations
Kun He, Mengjie Li, Yan Fu +2
The traditional approaches to false discovery rate (FDR) control in multiple hypothesis testing are usually based on the null distribution of a test statistic. However, all types o…
Quantum Lovász Local Lemma: Shearer's Bound is Tight
Kun He, Qian Li, Xiaoming Sun +1
The Lovász Local Lemma (LLL) is a very powerful tool in combinatorics and probability theory to show the possibility of avoiding all bad events under some weakly dependent conditio…
A Tighter Relation between Sensitivity and Certificate Complexity
Kun He, Qian Li, Xiaoming Sun
The sensitivity conjecture which claims that the sensitivity complexity is polynomially related to block sensitivity complexity, is one of the most important and challenging proble…