Publications and Manuscripts

All in alphabetic order and sorted by first publication date.

Locally Sampleable Uniform Symmetric Distributions
Daniel Kane, Anthony Ostuni, Kewen Wu
Submitted.
arXiv      ECCC     

Quantum State Preparation with Optimal T-Count
David Gosset, Robin Kothari, Kewen Wu
Submitted.
arXiv     

Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu
Submitted.
arXiv      ECCC

Tight Characterizations for Preprocessing against Cryptographic Salting
Fangqi Dong, Qipeng Liu, Kewen Wu
Annual International Cryptology Conference (CRYPTO), 2024.
arXiv      ePrint      CRYPTO

Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis
Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu
Symposium on Theory of Computing (STOC), 2024. Best paper award
arXiv      ECCC      STOC

Locality Bounds for Sampling Hamming Slices
Daniel Kane, Anthony Ostuni, Kewen Wu
Symposium on Theory of Computing (STOC), 2024.
arXiv      ECCC      STOC

The Power of Adaptivity in Quantum Query Algorithms
Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu
Quantum Information Processing (QIP), 2024.
Symposium on Theory of Computing (STOC), 2024.
arXiv      STOC

Fourier Growth of Communication Protocols for XOR Functions
Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu
Symposium on Foundations of Computer Science (FOCS), 2023.
arXiv      FOCS

On Differentially Private Counting on Trees
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Kewen Wu
International Colloquium on Automata, Languages, and Programming (ICALP), 2023.
arXiv      ICALP

Improved Bounds for Sampling Solutions of Random CNF Formulas
Kun He, Kewen Wu, Kuan Yang
Symposium on Discrete Algorithms (SODA), 2023.
arXiv      SODA

On the Generalized Shuffle-Exchange Problem
Xiaoming Sun, Yuan Sun, Kewen Wu, Zhiyu Xia
Pure and Applied Mathematics Quarterly (PAMQ), 2022. Special issue in honor of Fan Chung
PAMQ

Perfect Sampling for (Atomic) Lovász Local Lemma
Kun He, Xiaoming Sun, Kewen Wu
arXiv

Fourier Growth of Parity Decision Trees
Uma Girish, Avishay Tal, Kewen Wu
Computational Complexity Conference (CCC), 2021.
arXiv      ECCC      CCC

An Improved Sketching Algorithm for Edit Distance
Ce Jin, Jelani Nelson, Kewen Wu
Symposium on Theoretical Aspects of Computer Science (STACS), 2021.
arXiv      STACS

On the Degree of Boolean Functions as Polynomials over $\mathbb Z_m$
Xiaoming Sun, Yuan Sun, Jiaheng Wang, Kewen Wu, Zhiyu Xia, Yufan Zheng
International Colloquium on Automata, Languages, and Programming (ICALP), 2020.
arXiv      ICALP

Decision list compression by mild random restrictions
Shachar Lovett, Kewen Wu, Jiapeng Zhang
Symposium on Theory of Computing (STOC), 2020.
Journal of the ACM (JACM), Vol. 68, No. 6, 2021.
arXiv      ECCC      STOC      JACM

Improved bounds for the sunflower lemma
Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang
Symposium on Theory of Computing (STOC), 2020. Best paper award
Annals of Mathematics, Vol. 194, No. 3, 2021.
Frontiers of Science Award at the International Congress of Basic Science, 2023.
arXiv      ECCC      STOC      Annals

Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis
Jiaqing Jiang, Xiaoming Sun, Shang-Hua Teng, Bujiao Wu, Kewen Wu, Jialin Zhang
Symposium on Discrete Algorithms (SODA), 2020.
arXiv      SODA

A Note on Lower Digits Extraction Polynomial for Bootstrapping
Mingjia Huo, Kewen Wu, Qi Ye
arXiv      ePrint

Structured decomposition for reversible Boolean functions
Jiaqing Jiang, Xiaoming Sun, Yuan Sun, Kewen Wu, Zhiyu Xia
Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), 2019.
arXiv      TCAD

On the Relationship between Energy Complexity and other Boolean Function Measures
Xiaoming Sun, Yuan Sun, Kewen Wu, Zhiyu Xia
International Computing and Combinatorics Conference (COCOON), 2019.
Journal of Combinatorial Optimization (JOCO), 2021.
arXiv      COCOON      JOCO