About Me

I am a fourth year Ph.D student studying Computer Science at University of Texas at Austin, advised by Prof. Dana Moshkovitz. My research is mainly focused on complexity theory, especially in hardness of approximation and circuit lower bounds.

I am also interested in topics such as quantum complexity, coding theory and deep learning theory.

Publications / Manuscripts

• Fast Distance Oracles for Any Symmetric Norm
  • Yichuan Deng, Zhao Song, Omri Weinstein, Ruizhe Zhang
  • [arxiv]

• Sparse Fourier Transform over Lattices: A Unified Approach to Signal Reconstruction
  • Zhao Song, Baocheng Sun, Omri Weinstein, Ruizhe Zhang
  • [arxiv]

• Eigenstripping, Spectral Decay, and Edge-Expansion on Posets
  • Jason Gaitonde, Max Hopkins, Tali Kaufman, Shachar Lovett, Ruizhe Zhang
  • To appear in the 26th International Conference on Randomization and Computation (RANDOM'2022)
  • [arxiv]

• A Dynamic Fast Gaussian Transform
  • Baihe Huang, Zhao Song, Omri Weinstein, Hengjie Zhang, Ruizhe Zhang
  • [arxiv]

• Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time
  • Zhao Song, Lichen Zhang, Ruizhe Zhang
  • [arxiv]

• Solving SDP Faster: A Robust IPM Framework and Efficient Implementation
  • Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao, Ruizhe Zhang
  • To appear in the 63rd Annual Symposium on Foundations of Computer Science (FOCS 2022)
  • [arxiv]

• Computing Ground State Properties with Early Fault-Tolerant Quantum Computers
  • Ruizhe Zhang, Guoming Wang, Peter Johnson
  • In Quantum, Volume 6, Number 761 (2022)
  • [arxiv] [Journal]

• 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]

• Does Preprocessing Help Training Over-parameterized Neural Networks?
  • Zhao Song, Shuo Yang, Ruizhe Zhang
  • In Proceedings of the 35-th Conference on Neural Information Processing Systems (NeurIPS'2021)
  • [arxiv] [Conference]

• Symmetric Boolean Factor Analysis with Applications to InstaHide
  • Sitan Chen, Zhao Song, Runzhou Tao, Ruizhe Zhang
  • In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS'2022)
  • [arxiv] [Conference]

• InstaHide's Sample Complexity When Mixing Two Private Images
  • Baihe Huang, Zhao Song, Runzhou Tao, Ruizhe Zhang, Danyang Zhuo
  • [arxiv]

• Hyperbolic Concentration, Anti-concentration, and Discrepancy
  • Zhao Song, Ruizhe Zhang
  • To appear in the 26th International Conference on Randomization and Computation (RANDOM'2022)
  • [arxiv]

• 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]