Ruizhe Zhang

Ph.D.
Computer Science

Email: rzzhang berkeley dot edu

© 2024. All rights reserved.

About Me

I am a Simons Quantum Postdoctoral Fellow at Simons Institute for the Theory of Computing at UC Berkeley, hosted by Umesh Vazirani. I got my Ph.D. from UT Austin in 2023, where I was very fortunate to be advised by Dana Moshkovitz.

My research interests mainly lie in theoretical computer science. Currently I’m working on quantum algorithms, optimization, meta-complexity, and deep learning theory. I am always open to new topics.

I was visiting the Institute for Pure and Applied Mathematics (IPAM), UCLA for the long program Mathematical and Computational Challenges in Quantum Computing in 2023.

Publications

  • A General Algorithm for Solving Rank-one Matrix Sensing
    • Lianke Qin, Zhao Song, Ruizhe Zhang
    • To appear in the 27th International Conference on Artificial Intelligence and Statistics (AISTATS'2024)
    • [arXiv]
  • Fast Dynamic Sampling for Determinantal Point Processes
    • Zhao Song, Junze Yin, Lichen Zhang, Ruizhe Zhang
    • To appear in the 27th International Conference on Artificial Intelligence and Statistics (AISTATS'2024)
  • Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time
    • Zhao Song, Lichen Zhang, Ruizhe Zhang
    • In Proceedings of the 15th Innovations in Theoretical Computer Science Conference (ITCS'2024)
    • [arXiv] [Conference]
  • Bypass exponential time preprocessing: Fast neural network training via weight-data correlation preprocessing
    • Josh Alman, Jiehao Liang, Zhao Song, Ruizhe Zhang, Danyang Zhuo
    • To appear in the 37-th Conference on Neural Information Processing Systems (NeurIPS'2023)
    • [arXiv]
  • Quartic Samples Suffice for Fourier Interpolation
    • Zhao Song, Baocheng Sun, Omri Weinstein, Ruizhe Zhang
    • In Proceedings of the 64th IEEE Symposium on the Foundations of Computer Science (FOCS'2023)
    • [arXiv] [Conference]
  • Hyperbolic Extension of Kadison-Singer Type Results
    • Ruizhe Zhang, Xinzhi Zhang
    • In Proceedings of the 50th EATCS International Colloquium on Automata, Languages, and Programming (ICALP'2023)
    • [arXiv] [Conference]
  • Quantum algorithm for ground state energy estimation using circuit depth with exponentially improved dependence on precision
    • Guoming Wang, Daniel Stilck França, Ruizhe Zhang, Shuchen Zhu, Peter D. Johnson
    • Contributed talk at the third Quantum Computing Theory in Practice (QCTIP'2023)
    • In Quantum, Volume 7, Number 1167 (2023)
    • [arXiv] [Journal]
  • Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits
    • Tongyang Li, Ruizhe Zhang
    • In Proceedings of the Advances in Neural Information Processing Systems 35 (NeurIPS'2022)
    • [arXiv] [Conference]
  • Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants
    • Andrew Childs, Tongyang Li, Jin-Peng Liu, Chunhao Wang, Ruizhe Zhang
    • In Proceedings of the Advances in Neural Information Processing Systems 35 (NeurIPS'2022)
    • Contributed talk at the 26-th Conference on Quantum Information Processing (QIP'2023)
    • [arXiv] [Conference]
  • Fast Distance Oracles for Any Symmetric Norm
    • Yichuan Deng, Zhao Song, Omri Weinstein, Ruizhe Zhang
    • In Proceedings of the Advances in Neural Information Processing Systems 35 (NeurIPS'2022)
    • [arXiv] [Conference]
  • Solving SDP Faster: A Robust IPM Framework and Efficient Implementation
    • Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao, Ruizhe Zhang
    • In Proceedings of the 63rd IEEE Symposium on Foundations of Computer Science (FOCS 2022)
    • [arXiv] [Conference]
  • Eigenstripping, Spectral Decay, and Edge-Expansion on Posets
    • Jason Gaitonde, Max Hopkins, Tali Kaufman, Shachar Lovett, Ruizhe Zhang
    • In Proceedings of the 26th International Conference on Randomization and Computation (RANDOM'2022)
    • [arXiv] [Conference]
  • Hyperbolic Concentration, Anti-concentration, and Discrepancy
    • Zhao Song, Ruizhe Zhang
    • In Proceedings of the 26th International Conference on Randomization and Computation (RANDOM'2022)
    • [arXiv] [Conference]
  • Computing Ground State Properties with Early Fault-Tolerant Quantum Computers
  • Quantum Meets Minimum Circuit Size Problem
    • Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, Ruizhe Zhang
    • In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS'2022)
    • [arXiv] [eccc] [Conference]
  • Symmetric Sparse Boolean Matrix Factorization and Applications
    • Sitan Chen, Zhao Song, Runzhou Tao, Ruizhe Zhang
    • In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS'2022)
    • [arXiv] [Conference]
  • Does Preprocessing Help Training Over-parameterized Neural Networks?
    • Zhao Song, Shuo Yang, Ruizhe Zhang
    • In Proceedings of the Advances in Neural Information Processing Systems 34 (NeurIPS'2021)
    • [arXiv] [Conference]
  • New Approaches for Quantum Copy-Protection
    • Scott Aaronson, Jiahui Liu, Qipeng Liu, Mark Zhandry, Ruizhe Zhang
    • In Proceedings of the 41st Annual International Cryptology Conference (Crypto'2021)
    • Contributed talk at the 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC'2021)
    • [arXiv] [Conference]
  • QED driven QAOA for network-flow optimization
    • Yuxuan Zhang, Ruizhe Zhang, Andrew C. Potter
    • In Quantum, Volume 5, Number 510 (2021)
    • [arXiv] [Journal]
  • On the Quantum Complexity of Closest Pair and Related Problems
    • Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, Ruizhe Zhang
    • In Proceedings of the 35th Computational Complexity Conference (CCC'2020)
    • Contributed talk at the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC'2020)
    • [arXiv] [Conference]

Manuscripts

  • The ESPRIT algorithm under high noise: Optimal error scaling and noisy super-resolution
    • Zhiyan Ding, Ethan N. Epperly, Lin Lin, Ruizhe Zhang
    • [arXiv]
  • Quantum Multiple Eigenvalue Gaussian filtered Search: an efficient and versatile quantum phase estimation method
    • Zhiyan Ding, Haoya Li, Lin Lin, HongKang Ni, Lexing Ying, Ruizhe Zhang
    • [arXiv]
  • Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameters
    • Zhao Song, Junze Yin, Ruizhe Zhang
    • [arXiv]
  • Convergence and Generalization of Wide Neural Networks with Large Bias
    • Hongru Yang, Ziyu Jiang, Ruizhe Zhang, Zhangyang Wang, Yingbin Liang
    • [arXiv]
  • Sparse Fourier Transform over Lattices: A Unified Approach to Signal Reconstruction
    • Zhao Song, Baocheng Sun, Omri Weinstein, Ruizhe Zhang
    • [arXiv]
  • A Dynamic Fast Gaussian Transform
    • Baihe Huang, Zhao Song, Omri Weinstein, Hengjie Zhang, Ruizhe Zhang
    • [arXiv]
  • InstaHide's Sample Complexity When Mixing Two Private Images
    • Baihe Huang, Zhao Song, Runzhou Tao, Ruizhe Zhang, Danyang Zhuo
    • [arXiv]