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
362020
Composition theorems for interactive differential privacy
X Lyu
Advances in Neural Information Processing Systems 35, 9700-9712, 2022
202022
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
202022
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
182023
Range avoidance for low-depth circuits and connections to pseudorandomness
V Guruswami, X Lyu, X Wang
Approximation, Randomization, and Combinatorial Optimization. Algorithms and …, 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
122021
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
92021
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
82022
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
72023
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
62023
Improved pseudorandom generators for AC⁰ circuits
X Lyu
37th Computational Complexity Conference (CCC 2022), 2022
52022
Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries
E Cohen, X Lyu, J Nelson, T Sarlós, U Stemmer
arXiv preprint arXiv:2403.00028, 2024
42024
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
42023
Hot PATE: Private Aggregation of Distributions for Diverse Tasks
E Cohen, X Lyu, J Nelson, T Sarlos, U Stemmer
32023
The target-charging technique for privacy accounting across interactive computations
E Cohen, X Lyu
arXiv preprint arXiv:2302.11044, 2023
32023
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
22023
The target-charging technique for privacy analysis across interactive computations
E Cohen, X Lyu
Advances in Neural Information Processing Systems 36, 2024
12024
The Cost of Parallelizing Boosting
X Lyu, H Wu, J Yang
Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms …, 2024
12024
Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis
X Lyu, K Talwar
arXiv preprint arXiv:2412.14396, 2024
2024
The system can't perform the operation now. Try again later.
Articles 1–19