4 citations · 4 across the 2 of their papers we have counts for
7 papers
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…
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 \…
On the Degree of Boolean Functions as Polynomials over
Xiaoming Sun, Yuan Sun, Jiaheng Wang +3
Polynomial representations of Boolean functions over various rings such as and have been studied since Minsky and Papert (1969). From then on, they have…
Decision list compression by mild random restrictions
Shachar Lovett, Kewen Wu, Jiapeng Zhang
A decision list is an ordered list of rules. Each rule is specified by a term, which is a conjunction of literals, and a value. Given an input, the output of a decision list is the…
A Note on Lower Digits Extraction Polynomial for Bootstrapping
Mingjia Huo, Kewen Wu, Qi Ye
Bootstrapping is a crucial but computationally expensive step for realizing Fully Homomorphic Encryption (FHE). Recently, Chen and Han (Eurocrypt 2018) introduced a family of low-d…
Structured decomposition for reversible Boolean functions
Jiaqing Jiang, Xiaoming Sun, Yuan Sun +2
Reversible Boolean function is a one-to-one function which maps -bit input to -bit output. Reversible logic synthesis has been widely studied due to its relationship with low…