Sihan Liu


Sihan Liu

Sihan Liu's Personal Page

I am a first-year PhD student in UC San Diego's theoretical computer science group, where I am extremely fortuate to be advised by Daniel Kane.

I did my undergraduate BS in Computer Science at University of Wisconsin Madison and was lucky enough to be work with Ilias Diakonikolas and Christos Tzamos.

I am interested in algorithmic and statistical problems related to the foundations of machine learning.

- In theory, there is no difference between theory and practice. But in practice, there is.

My music collection


Sampling Equilibria: Fast No-Regret Learning in Structured Games (Daniel Beaglehole, Max Hopkins, Daniel Kane, Shachar Lovett)
  • Develop a general framework of sampling equilibria from games of large state space.
  • Fast algorithm for computing approximate equilibria for Colonel Blotto Game.
  • In submission. Link to Manuscript
Nearly-Tight Bounds for Testing Histogram Distributions (C. Cannone, I. Diakonikolas, D. Kane)
  • Accept to NeurIPS 2022. Link
  • Obtain nearly optimal algorithm for histogram testing. Story behind
  • Derive nearly matching sample complexity lower bound.
Computational-Statistical Gaps in Reinforcement Learning (D. Kane, S. Lovett, G. Mahajan)
2021.10 - 2022.2
  • Accept to COLT 2022. Link
  • Present the first computational lower bound for RL with linear function approximation.
Convergence and Sample Complexity of SGD in GANs (C. Tzamos, V. Kontonis)
2020.1 - 2020.10
  • Propose a theoretical framework for analyzing the performance of stochastic gradient ascent descent in non-convex general sum game.
  • Obtain theoretical guarantees on nearly optimal sample complexity and convergence rate of Generative Adversarial Networks in learning one-layer non-linear neural nets.
  • Selected to present at CS Student Research Symposium. Link to Manuscript

Other Experience

Competitive Programming
2018 - Present
Dieter van Melkebeek
Achievements: 2019 ICPC North Central NA Regional Contest #3 over 183 teams (Team NP-Easiness), Codejam Round 2 Top 3% (leo990629), Hackercup Round 2 Top 10% (sihan.liu.3139).
Software Enginner Intern in DataChat
2019.6 - Present
DataChat Inc.
  • Constrained Natural Language (CNL) parsing: intention inference and entity retrieval from structured natural language.
  • Autocomplete Engine: provide data-sensitive suggestions in the middle of typing.
  • Linter: semantic highlighting in user input.
  • Skills used: React.js + Redux + Saga, Golang, Python, RedisStore, spaCy.


Bachelor degrees in Computer Science and Mathematics (4.0/4.0)
GPA: 4.0/4.0
Dewitt Undergraduate Scholarship
Coursework: Learning Theory, Advanced Algorithm, Algorithmic Game Theory, Mechanism Design, Quantum Computing
University of Wisconsin Madison
2017 - 2021

Class Projects