research
∙
07/26/2023
Fourier Growth of Communication Protocols for XOR Functions
The level-k ℓ_1-Fourier weight of a Boolean function refers to the sum o...
share
research
∙
10/05/2022
On the Learning Mechanisms in Physical Reasoning
Is dynamics prediction indispensable for physical reasoning? If so, what...
research
∙
07/25/2022
Improved Bounds for Sampling Solutions of Random CNF Formulas
Let Φ be a random k-CNF formula on n variables and m clauses, where each...
research
∙
07/08/2021
Perfect Sampling for (Atomic) Lovász Local Lemma
We give a Markov chain based perfect sampler for uniform sampling soluti...
research
∙
03/22/2021
Fourier Growth of Parity Decision Trees
We prove that for every parity decision tree of depth d on n variables, ...
research
∙
10/25/2020
An Improved Sketching Bound for Edit Distance
We provide improved upper bounds for the simultaneous sketching complexi...
research
∙
10/28/2019
On the Degree of Boolean Functions as Polynomials over Z_m
Polynomial representations of Boolean functions over various rings such ...
research
∙
09/24/2019
Decision list compression by mild random restrictions
A decision list is an ordered list of rules. Each rule is specified by a...
research
∙
08/22/2019
Improved bounds for the sunflower lemma
A sunflower with r petals is a collection of r sets so that the intersec...
research
∙
07/11/2019
Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis
Due to the decoherence of the state-of-the-art physical implementations ...
research
∙
06/07/2019
A Note on Lower Digits Extraction Polynomial for Bootstrapping
Bootstrapping is a crucial but computationally expensive step for realiz...
research
∙
10/09/2018