Follow
Xin Lyu
Title
Cited by
Cited by
Year
Almost-everywhere circuit lower bounds from non-trivial derandomization
L Chen, X Lyu, RR Williams
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), 1-12, 2020
352020
On the robustness of countsketch to adaptive inputs
E Cohen, X Lyu, J Nelson, T Sarlós, M Shechner, U Stemmer
International Conference on Machine Learning, 4112-4140, 2022
152022
Composition theorems for interactive differential privacy
X Lyu
Advances in Neural Information Processing Systems 35, 9700-9712, 2022
122022
Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma
L Chen, X Lyu
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing …, 2021
102021
Optimal differentially private learning of thresholds and quasi-concave optimization
E Cohen, X Lyu, J Nelson, T Sarlós, U Stemmer
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 472-482, 2023
72023
Range Avoidance for Low-Depth Circuits and Connections to Pseudorandomness
V Guruswami, X Lyu, X Wang
Approximation, Randomization, and Combinatorial Optimization. Algorithms and …, 2022
72022
Majority vs. approximate linear sum and average-case complexity below NC1
L Chen, Z Lu, X Lyu, IC Oliveira
48th International Colloquium on Automata, Languages, and Programming (ICALP …, 2021
52021
New PRGs for Unbounded-Width/Adaptive-Order Read-Once Branching Programs
L Chen, X Lyu, A Tal, H Wu
50th International Colloquium on Automata, Languages, and Programming (ICALP …, 2023
42023
Generalized private selection and testing with high confidence
E Cohen, X Lyu, J Nelson, T Sarlós, U Stemmer
arXiv preprint arXiv:2211.12063, 2022
42022
Improved Pseudorandom Generators for AC⁰ Circuits
X Lyu
37th Computational Complexity Conference (CCC 2022), 2022
42022
Time-Space Tradeoffs for Element Distinctness and Set Intersection via Pseudorandomness
X Lyu, W Zhu
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms …, 2023
32023
Weighted pseudorandom generators via inverse analysis of random walks and shortcutting
L Chen, WM Hoza, X Lyu, A Tal, H Wu
2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS …, 2023
22023
The Target-Charging Technique for Privacy Accounting across Interactive Computations
E Cohen, X Lyu
arXiv preprint arXiv:2302.11044, 2023
22023
The Target-Charging Technique for Privacy Analysis across Interactive Computations
E Cohen, X Lyu
Advances in Neural Information Processing Systems 36, 2024
2024
The Cost of Parallelizing Boosting
X Lyu, H Wu, J Yang
Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms …, 2024
2024
Tight Time-Space Lower Bounds for Constant-Pass Learning
X Lyu, A Tal, H Wu, J Yang
2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS …, 2023
2023
Hot PATE: Private Aggregation of Distributions for Diverse Tasks
E Cohen, X Lyu, J Nelson, T Sarlos, U Stemmer
2023
The system can't perform the operation now. Try again later.
Articles 1–17