Kewen Wu

According to our database, Kewen Wu authored at least 25 papers between 2019 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals.

Daniel Grier, Daniel M. Kane, Jackson Morris, Anthony Ostuni, Kewen Wu

CoRR, October, 2025

PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs.

Venkatesan Guruswami, Xuandi Ren, Kewen Wu

CoRR, July, 2025

Sunflowers and Ramsey problems for restricted intersections.

Barnabás Janzer, Zhihan Jin, Benny Sudakov, Kewen Wu

CoRR, April, 2025

(Sub)Exponential Quantum Speedup for Optimization.

Jiaqi Leng, Kewen Wu, Xiaodi Wu, Yufan Zheng

CoRR, April, 2025

Locally Sampleable Uniform Symmetric Distributions.

Daniel M. Kane, Anthony Ostuni, Kewen Wu

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH.

Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

2024

Locality Bounds for Sampling Hamming Slices.

Daniel M. Kane, Anthony Ostuni, Kewen Wu

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis.

Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

The Power of Adaptivity in Quantum Query Algorithms.

Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Tight Characterizations for Preprocessing Against Cryptographic Salting.

Fangqi Dong, Qipeng Liu, Kewen Wu

Proceedings of the Advances in Cryptology - CRYPTO 2024, 2024

2023

Parameterized Inapproximability Hypothesis under ETH.

Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu

Electron. Colloquium Comput. Complex., 2023

Improved Bounds for Sampling Solutions of Random CNF Formulas.

Kun He, Kewen Wu, Kuan Yang

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

On Differentially Private Counting on Trees.

Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Kewen Wu

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Fourier Growth of Communication Protocols for XOR Functions.

Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2021

Perfect Sampling for (Atomic) Lovász Local Lemma.

Kun He, Xiaoming Sun, Kewen Wu

CoRR, 2021

An Improved Sketching Algorithm for Edit Distance.

Ce Jin, Jelani Nelson, Kewen Wu

Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

Fourier Growth of Parity Decision Trees.

Uma Girish, Avishay Tal, Kewen Wu

Proceedings of the 36th Computational Complexity Conference, 2021

2020

Structured Decomposition for Reversible Boolean Functions.

Jiaqing Jiang, Xiaoming Sun, Yuan Sun, Kewen Wu, Zhiyu Xia

IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2020

An Improved Sketching Bound for Edit Distance.

Ce Jin, Jelani Nelson, Kewen Wu

CoRR, 2020

Decision list compression by mild random restrictions.

Shachar Lovett, Kewen Wu, Jiapeng Zhang

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Improved bounds for the sunflower lemma.

Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

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

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

On the Degree of Boolean Functions as Polynomials over ℤ_m.

Xiaoming Sun, Yuan Sun, Jiaheng Wang, Kewen Wu, Zhiyu Xia, Yufan Zheng

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2019

A Note on Lower Digits Extraction Polynomial for Bootstrapping.

Mingjia Huo, Kewen Wu, Qi Ye

IACR Cryptol. ePrint Arch., 2019

On the Relationship Between Energy Complexity and Other Boolean Function Measures.

Xiaoming Sun, Yuan Sun, Kewen Wu, Zhiyu Xia

Proceedings of the Computing and Combinatorics - 25th International Conference, 2019