Chihao Zhang's Research Papers

Sampling proper colorings on line graphs using (1+o(1))Δ colors

with Yulin Wang and Zihan Zhang.

To appear in STOC'24

On interpolating experts and multi-armed bandits

with Houshuang Chen and Yuchen He.

Manuscript.

Improved algorithms for bandit with graph feedback via regret decomposition

with Yuchen He.

Theoretical Computer Science, 2023.

Approximability of the complementarily symmetric Holant problems on cubic graphs

with Yuqiao He, and Guoliang Qiu.

Theoretical Computer Science, 2023.

A perfect sampler for hypergraph independent sets

with Guoliang Qiu, and Yanheng Wang.

In Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP'22), 103:1-103:16, 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 Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'21), 1558-1577, 2021.

Understanding bandits with graph feedback

with Houshuang Chen, Zengfeng Huang, and Shuai Li.

In Proceedings of the 35th Conference on Neural Information Processing Systems (NeurIPS'21), 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 Proceedings of the 52nd Annual ACM SIGACT Symposium on the Theory of Computing (STOC'20), pp.854-867, 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 Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'19), pp.2262-2278, 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 Proceedings of the 50th Annual ACM SIGACT Symposium on the Theory of Computing (STOC'18), pp.926-938, 2018.

FPTAS for counting proper colorings on cubic graphs

with Pinyan Lu, Kuan Yang and Minshen Zhu.

In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'17), pp.1798-1817, 2017.

Sampling in Potts model on sparse random graphs

with Yitong Yin.

In Proceedings of the 20th International Workshop on Randomization and Computation (RANDOM'16), 47:1-47:22, 2016.

FPTAS for hardcore and Ising models on hypergraphs

with Pinyan Lu and Kuan Yang.

In Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS'16), 51:1-51:14, 2016.

Assignment and pricing in roommate market

with Pak Hay Chan, Xin Huang, Zhengyang Liu and Shengyu Zhang.

In Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI'16), pp.446-452, 2016.

Canonical paths for MCMC: from art to science

with Lingxiao Huang and Pinyan Lu.

In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'16), pp.514-527, 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.

In Proceedings of the 22nd European Symposium on Algorithms (ESA'14), pp.654-665, 2014.

The complexity of ferromagnetic two-spin systems with external fields

with Jingcheng Liu and Pinyan Lu.

A slightly older version can be found on arxiv.

In Proceedings of the 18th International Workshop on Randomization and Computation (RANDOM'14), pp.843-856, 2014.

FPTAS for weighted Fibonacci gates and its applications

with Pinyan Lu and Menghui Wang.

In Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP'14), pp.787-799, 2014.

Multi-multiway cut problem on graphs of bounded branch width

with Xiaojie Deng and Bingkai Lin.

In Proceedings of the 6th International Frontiers of Algorithmics Workshop and the 8th International Conference on Algorithmic Aspects of Information and Management (FAW-AAIM'13), pp. 315-324, 2013.

Approximate counting via correlation decay on planar graphs

with Yitong Yin.

In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'13), pp.47-66, 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 Proceedings of the 6th Annual International Conference on Combinatorial Optimization and Applications (COCOA'12), pp.127-137, 2012.

Fixed-parameter tractability of almost CSP problem with decisive relations

with Hongyang Zhang.

In Proceedings of the 6th International Frontiers of Algorithmics Workshop and the 8th International Conference on Algorithmic Aspects of Information and Management (FAW-AAIM'12), pp. 224-234, 2012.