Yin (Hugh) Liu
Computer scientist & software engineer at Google · Personal homepage
My research focuses on computational complexity and algorithms, particularly counting problems and complexity dichotomies. My work also spans machine learning and computer vision, including multimodal model evaluation and 3D perception.
I received my Ph.D. in Computer Science from the University of Wisconsin–Madison in 2023, advised by Professor Jin-Yi Cai, and my B.Eng. in Automation from Tsinghua University in 2018.
Contact: hughliu AT google DOT com · yinl AT cs DOT wisc DOT edu
Publications
I publish as Yin Liu or Hugh Liu. Journal and conference versions of the same work are listed together.
Journal Articles
- Restricted Holant Dichotomy on Domain Sizes 3 and 4
Yin Liu, Austen Z. Fan, Jin-Yi Cai.
Theoretical Computer Science 1023:114931, 2025.
Invited to the COCOA 2023 special issue. Conference version: Restricted Holant Dichotomy on Domains 3 and 4, COCOA 2023, LNCS 14462, pp. 83–96. - Bipartite 3-Regular Counting Problems with Mixed Signs
Jin-Yi Cai, Austen Z. Fan, Yin Liu. (Alphabetical author order.)
Journal of Computer and System Sciences 135:15–31, 2023.
Invited to the FCT 2021 special issue. Conference version: FCT 2021, LNCS 12867, pp. 135–148. - DeepPrimitive: Image Decomposition by Layered Primitive Detection
Jiahui Huang, Jun Gao, Vignesh Ganapathi-Subramanian, Hao Su, Yin Liu, Chengcheng Tang, Leonidas J. Guibas.
Computational Visual Media 4(4):385–397, 2018.
Peer-Reviewed Conference Papers
- A Combinatorial View of Holant Problems on Higher Domains
Yin Liu. (Sole author.)
30th International Computing and Combinatorics Conference (COCOON 2024), LNCS 15162, pp. 368–380. - CODIS: A New Compression Scheme for Bitmap Indexes
Wenxun Zheng, Yin Liu, Zhen Chen, Junwei Cao.
ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS 2017).
Symposium Poster
- Adopting Linear Model to Accelerate Neural Network Training
Yin Liu, Junyi Wei, Zijun Ma, Hanying Jiang, Yihan Zhang.
Midwest Machine Learning Symposium (MMLS 2019), poster.
Preprints and Manuscripts Under Review
- A Dichotomy for Cubic Bipartite Holant Problems with Complex Algebraic Weights
Yin Liu. (Sole author.)
arXiv:2609.33473, 2026. Submitted to STOC 2027. - VEPHand: View-Efficient Photometric Hand Performance Capture at Scale
Zhengyang Shen, Kai-Hung Chang, Erroll Wood, Deying Kong, Bo Peng, Timo Bolkart, Jinlong Yang, Bowen Zhao, Danhang Tang, Sasa Petrovic, Emre Aksan, Jérémy Riviere, Vassilis Choutas, Delio Vicini, Jay Busch, Shichen Liu, Zhe Cao, Hugh Liu, JingJing Shen, Jonathan Taylor, Mingsong Dou.
arXiv:2606.15966, 2026. - Seeing vs. Counting: Complexity Twins Show Where Multimodal LLMs Fail on Diagrams
Yin Liu. (Sole author.)
Manuscript, 2026.
Dissertation
- A Journey Through Some Computational Problems
Yin Liu.
Ph.D. dissertation, University of Wisconsin–Madison, 2023.
Education
- University of Wisconsin–Madison · Sep 2018–Aug 2023
Ph.D. in Computer Science; Minor in Mathematics.
Advisor: Professor Jin-Yi Cai. - Tsinghua University · Aug 2014–Jul 2018
B.Eng. in Automation.
Previous Internships and Research Visits
- Google, Sunnyvale, CA, summer 2023.
- Google, Mountain View, CA, summer 2022.
- SiriusXM–Pandora, remote, summer 2021.
- Cornell University, Ithaca, NY, 2017.
Honors and Awards
- Summer RA-ship Award, University of Wisconsin–Madison, 2019.
- Special CS Scholarship, University of Wisconsin–Madison, 2018.
- Science & Technology Innovation Excellence Award (top 5%), Tsinghua University, 2017.
- Hage Scholarship for Excellent Performance, Department of Automation, Tsinghua University, 2016 and 2017.
- Ronghua Zhang Scholarship (top 5%), Tsinghua University, 2015.
- First Prize (provincial division), National High School Mathematics Competition, Chinese Mathematical Society, 2013.
- First Prize (provincial division), National High School Physics Competition, Chinese Physical Society, 2013.
Beyond Research
I'm good at soccer, Tabata core workouts, table tennis, running, sprinting, figure roller skating, billiards, and go-karting. I also play tennis and basketball, and I swim. I used to do decathlon training with professional athletes.
I previously served as chair of the Tsinghua Alumni Association in Wisconsin for one year.
Authored Publications
Sort By
Seeing vs. Counting: Complexity Twins Show Where Multimodal LLMs Fail on Diagrams
arXiv preprint (2026)
Preview abstract
When a multimodal LLM miscounts in a diagram, does it fail at seeing or at counting? Existing visual graph and puzzle benchmarks vary visual density and algorithmic hardness together, confounding the two. We pair counting questions about the same drawing that sit in different counting-complexity classes, such as its spanning trees (a determinant) and its simple paths (#P-complete), and use a transcription probe and a text-only control to separate reading from computing. We test Gemini, Gemma and Qwen3-VL models; for the Gemini models, the answer depends on how the model computes. In chain of thought, most of them read small drawings correctly and then fail at counting, at a rate set far more by the size of the answer than by its complexity class (for the primary model, the odds of an exact answer fall 2.38-fold per decade of the answer). Given code and an exact transcription, the primary model counts correctly even on 10×10 grids, and reading becomes the bottleneck: a single view misses horizontal edges, and a second reading of a rotated copy with crop checks reads 86/96 large grids exactly, against 57/96 when the upright reading is simply repeated.
View details
VEPHand: View-Efficient Photometric Hand Performance Capture at Scale
Danhang "Danny" Tang
Sasa Petrovic
Timo Bolkart
Emre Aksan
Shichen Liu
Jonathan Taylor
Jérémy Riviere
Erroll Wood
Kai-Hung Chang
Vassilis Choutas
Mingsong Dou
Delio Vicini
Bowen Zhao
Deying Kong
Zhe Cao
Jinlong Yang
Jingjing Shen
arXiv preprint arXiv:2606.15966 (2026)
Preview abstract
High-fidelity 3D hand capture is fundamental to digital human creation, but achieving robust results from practical multi-view systems—which balance rich photometry with inherent geometric underspecification—remains challenging. This paper introduces an end-to-end pipeline for dynamic hand performance capture and registration designed for such conditions, utilizing a 20-camera photometric setup. We address core difficulties through two primary innovations: first, a mask-free neural reconstruction method that leverages scene parameterization and scenario-specific density regularization to robustly extract detailed hand geometry and appearance from unmasked images despite limited view overlap and potential background clutter. Second, we propose a volumetric physics-inspired registration framework that aligns these reconstructions to a personalized hand model built on a consistent tetrahedral mesh, enabling the capture of fine intrinsic deformations and ensuring plausible results under severe articulation and self-contact. We demonstrate the scalability and robustness of our automated pipeline on an extensive dataset of over 8,000 sequences, showcasing its effectiveness for single hands, intricate two-hand interactions, and detailed hand-object manipulations, significantly advancing the state-of-the-art in practical, high-quality hand capture.
View details
A Dichotomy for Cubic Bipartite Holant Problems with Complex Algebraic Weights
arXiv preprint arXiv:2609.33473 (2026)
Preview abstract
We classify the exact evaluation of Holant(f | =_3) for every fixed complex algebraic symmetric Boolean ternary signature f. An input is a cubic bipartite multigraph: every vertex on one side carries f, every vertex on the other side carries ternary equality, and no auxiliary signatures are freely available. The tractable signatures are precisely rank-one tensors, generalized equalities, and equality-preserving cube-root diagonal transformations of six affine signatures, together with nonzero scalings and reversal. Every other signature gives a #P-hard problem under polynomial-time Turing reductions. We also identify the exact real intersection: it consists of the same tractable families as in the rational classification, with real algebraic parameters. The proof preserves degree exactly three on both sides of every oracle instance. A rank-one matrix extracted by interpolation supplies one unary signature only after its unused factor has been absorbed in triples. Over the complex numbers this absorption has three exceptional projective directions. We combine this constraint with projective matrix-group orbits, explicit ternary replacements, and an exhaustive treatment of finite projective orders. The cases of orders three and five include exact polynomial certificates; the certificate identities and a rational-arithmetic verifier are supplied as supplementary material.
View details
A combinatorial view of Holant problems on higher domains
30th International Computing and Combinatorics Conference (COCOON 2024), pp. 368-380
Preview abstract
On the Boolean domain, there is a class of symmetric signatures called “Fibonacci gates” for which a beautiful P-time combinatorial algorithm has been designed for the corresponding Holant problems.
In this work, I give a combinatorial view for Holant(F) problems on a domain of size 3 where F is a set of arity 3 functions with inputs taking values on the domain of size 3 and the functions share some common properties. The combinatorial view can also be extended to the domain
of size 4.
Specifically, I extend the definition of “Fibonacci gates” to the domain of size 3 and the domain of size 4. Moreover, I give the corresponding combinatorial algorithms.
View details
