Xin Lyu

According to our database, Xin Lyu authored at least 17 papers between 2020 and 2024.

Collaborative distances:

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

2024

Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries.

Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer

IACR Cryptol. ePrint Arch., 2024

The Cost of Parallelizing Boosting.

Xin Lyu, Hongxun Wu, Junzhao Yang

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

2023

Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting.

Lijie Chen, William Hoza, Xin Lyu, Avishay Tal, Hongxun Wu

Electron. Colloquium Comput. Complex., 2023

Hot PATE: Private Aggregation of Distributions for Diverse Task.

Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer

CoRR, 2023

The Target-Charging Technique for Privacy Accounting across Interactive Computations.

Edith Cohen, Xin Lyu

CoRR, 2023

Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization.

Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

The Target-Charging Technique for Privacy Analysis across Interactive Computations.

Edith Cohen, Xin Lyu

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Generalized Private Selection and Testing with High Confidence.

Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

New PRGs for Unbounded-Width/Adaptive-Order Read-Once Branching Programs.

Lijie Chen, Xin Lyu, Avishay Tal, Hongxun Wu

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

Tight Time-Space Lower Bounds for Constant-Pass Learning.

Xin Lyu, Avishay Tal, Hongxun Wu, Junzhao Yang

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

2022

Improved Pseudorandom Generators for AC⁰ Circuits.

Xin Lyu

Electron. Colloquium Comput. Complex., 2022

On the Robustness of CountSketch to Adaptive Inputs.

Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Moshe Shechner, Uri Stemmer

Proceedings of the International Conference on Machine Learning, 2022

Improved Pseudorandom Generators for AC⁰ Circuits.

Xin Lyu

Proceedings of the 37th Computational Complexity Conference, 2022

2021

Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC1.

Lijie Chen, Zhenjian Lu, Xin Lyu, Igor Carboni Oliveira

Electron. Colloquium Comput. Complex., 2021

Inverse-Exponential Correlation Bounds and Extremely Rigid Matrices from a New Derandomized XOR Lemma.

Lijie Chen, Xin Lyu

Electron. Colloquium Comput. Complex., 2021

Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC¹.

Lijie Chen, Zhenjian Lu, Xin Lyu, Igor C. Oliveira

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020

Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization.

Lijie Chen, Xin Lyu, Ryan Williams

Electron. Colloquium Comput. Complex., 2020