6 citations · 12 across the 9 of their papers we have counts for
5 papers · 1 filter
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…