6 citations · 12 across the 9 of their papers we have counts for
13 papers
Fourier Growth of Communication Protocols for XOR Functions
Uma Girish, Makrand Sinha, Avishay Tal +1
The level- -Fourier weight of a Boolean function refers to the sum of absolute values of its level- Fourier coefficients. Fourier growth refers to the growth of these…
On Differentially Private Counting on Trees
Badih Ghazi, Pritish Kamath, Ravi Kumar +2
We study the problem of performing counting queries at different levels in hierarchical structures while preserving individuals' privacy. Motivated by applications, we propose a ne…
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…
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 \…
An Improved Sketching Algorithm for Edit Distance
Ce Jin, Jelani Nelson, Kewen Wu
We provide improved upper bounds for the simultaneous sketching complexity of edit distance. Consider two parties, Alice with input and Bob with input , that sha…
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…
Improved bounds for the sunflower lemma
Ryan Alweiss, Shachar Lovett, Kewen Wu +1
A sunflower with petals is a collection of sets so that the intersection of each pair is equal to the intersection of all of them. Erdős and Rado proved the sunflower lemma…
Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis
Jiaqing Jiang, Xiaoming Sun, Shang-Hua Teng +3
Decoherence -- in the current physical implementations of quantum computers -- makes depth reduction a vital task in quantum-circuit design. Moore and Nilsson (SIAM Journal of Comp…
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…
On the Relationship between Energy Complexity and other Boolean Function Measures
Xiaoming Sun, Yuan Sun, Kewen Wu +1
In this work we investigate into energy complexity, a Boolean function measure related to circuit complexity. Given a circuit over the standard basis $\{\vee_2,\wedge…