Chihao Zhang’s Research Papers

---

• Improved sampling algorithms and Poincaré inequalities for non-log-concave distributions
  with Yuchen He, Zhehan Lei and Jianan Shao
  

  Manuscript, 2025

• Tight regret bounds for fixed-price bilateral trade
  with Houshuang Chen, Yaonan Jin and Pinyan Lu

  Manuscript, 2025

• On the query complexity of sampling from non-log-concave distributions
  with Yuchen He

  The 38th Annual Conference on Learning Theory (COLT 2025)

• Decay of correlation for edge colorings when q>3Δ
  with Zejia Chen, Yulin Wang and Zihan Zhang

  The 52nd EATCS International Colloquium on Automata, Languages, and Programming (ICALP 2025)

• Tight gap-dependent memory-regret trade-off for single-pass streaming stochastic multi-armed bandits
  with Zichun Ye and Jiahao Zhao

  The 31st International Computing and Combinatorics Conference (COCOON 2025)

• FPTAS for Holant problems with log-concave signatures
  with Kun He, Zhidan Li and Guoliang Qiu

  The 36th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025)

• Understanding memory-regret trade-off for streaming stochastic multi-armed bandits
  with Yuchen He and Zichun Ye

  The 36th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025)

• On the problem of best arm retention
  with Houshuang Chen and Yuchen He

  Theoretical Computer Science 1041 (2025): 115213

  Conference version appeared in the 5th International Joint Conference on Theoretical Computer Science – 18th Frontier of Algorithmic Wisdom (IJTCS-FAW 2024)

• On interpolating experts and multi-armed bandits
  with Houshuang Chen and Yuchen He

  The 41st International Conference on Machine Learning (ICML 2024)

• Sampling proper colorings on line graphs using (1+o(1))Δ colors
  with Yulin Wang and Zihan Zhang

  The 56th Annual ACM Symposium on Theory of Computing (STOC 2024)

• Improved algorithms for bandit with graph feedback via regret decomposition
  with Yuchen He

  Theoretical Computer Science 979 (2023): 114200

• Approximability of the complementarily symmetric Holant problems on cubic graphs
  with Yuqiao He and Guoliang Qiu

  Theoretical Computer Science 975 (2023): 114140

• A perfect sampler for hypergraph independent sets
  with Guoliang Qiu and Yanheng Wang

  The 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

• Rapid mixing from spectral independence beyond the Boolean domain
  with Weiming Feng, Heng Guo, and Yitong Yin

  ACM Transactions on Algorithms 18(3), 28:1-28:32, 2022

  Conference version appeared in the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021)

• Understanding bandits with graph feedback
  with Houshuang Chen, Zengfeng Huang, and Shuai Li

  The 35th Conference on Neural Information Processing Systems (NeurIPS 2021)

• Fast sampling and counting k-SAT solutions in the local lemma regime
  with Weiming Feng, Heng Guo, and Yitong Yin

  Journal of the ACM 68(6), 1-42, 2021

  Conference version appeared in the 52nd Annual ACM SIGACT Symposium on the Theory of Computing (STOC 2020)

• Zeros of Holant problems: locations and algorithms
  with Heng Guo, Chao Liao and Pinyan Lu

  ACM Transactions on Algorithms 17(1):4:1-4:25 (2021)

  Conference version appeared in the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)

• Counting hypergraph colorings in the local lemma regime
  with Heng Guo, Chao Liao and Pinyan Lu

  SIAM Journal on Computing 48(4), 1397-1424, 2019

  Conference version appeared in the 50th Annual ACM SIGACT Symposium on the Theory of Computing (STOC 2018)

Prior to 2018 (Before joining SJTU as a faculty member)

• FPTAS for counting proper colorings on cubic graphs
  with Pinyan Lu, Kuan Yang and Minshen Zhu

  The 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)

• Sampling in Potts model on sparse random graphs
  with Yitong Yin

  The 20th International Workshop on Randomization and Computation (RANDOM 2016)

• FPTAS for hardcore and Ising models on hypergraphs
  with Pinyan Lu and Kuan Yang

  The 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

• [Assignment and pricing in roommate market]
  with Pak Hay Chan, Xin Huang, Zhengyang Liu and Shengyu Zhang

  The 30th AAAI Conference on Artificial Intelligence (AAAI 2016)

• Canonical paths for MCMC: from art to science
  with Lingxiao Huang and Pinyan Lu

  The 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016)

• Counting problems in parameterized complexity
  with Yijia Chen

  Tsinghua Science and Technology, 19(04), 410-420, 2014

• FPTAS for counting weighted edge covers
  with Jingcheng Liu and Pinyan Lu

  The 22nd European Symposium on Algorithms (ESA 2014)

• The complexity of ferromagnetic two-spin systems with external fields
  with Jingcheng Liu and Pinyan Lu

  The 18th International Workshop on Randomization and Computation (RANDOM 2014)

• FPTAS for weighted Fibonacci gates and its applications
  with Pinyan Lu and Menghui Wang

  The 41st International Colloquium on Automata, Languages and Programming (ICALP 2014)

• Multi-multiway cut problem on graphs of bounded branch width
  with Xiaojie Deng and Bingkai Lin

  The 6th International Frontiers of Algorithmics Workshop and the 8th International Conference on Algorithmic Aspects of Information and Management (FAW-AAIM 2013)

• Approximate counting via correlation decay on planar graphs
  with Yitong Yin

  The 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013)

• Radiation hybrid map construction problem parameterized
  with Binhai Zhu and Haitao Jiang

  Journal of Combinatorial Optimization, 27(1), 3-13, 2014

  Conference version appeared in the 6th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2012)

• Fixed-parameter tractability of almost CSP problem with decisive relations
  with Hongyang Zhang

  The 6th International Frontiers of Algorithmics Workshop and the 8th International Conference on Algorithmic Aspects of Information and Management (FAW-AAIM 2012)