 |
Yitong Yin 尹一通 Professor Ph.D., Yale University (2009) PO Box 603 |
I am Yitong Yin (尹一通), a professor in the Theory Group in the Department of Computer Science and Technology at Nanjing University.
I joined the faculty of Nanjing University in 2009.
I've been long-term visitors in:
Microsoft Research Asia (Spring 2011)
University of Wisconsin-Madison (2012)
Simons Institute for the Theory of Computing, UC Berkeley, the "Counting Complexity and Phase Transitions" program (Spring 2016), and the "Geometry of Polynomials" program (Spring 2019)
Bernoulli Center (CIB), École Polytechnique Fédérale de Lausanne (EPFL), the "Computational Aspects of Partition Functions" semester (Fall 2018)
PC co-chair: NCTCS (全国理论计算机科学学术年会) 2024, NCTCS 2020
Editorial board: 《软件学报》 (Journal of Software), 《计算机科学》 ("Computer Science" magazine)
Deputy director of the Technical Committee on Theoretical Computer Science of China Computer Federation (CCF) (CCF理论计算机科学专委会 副主任)
Research interests
Theoretical Computer Science:Randomized algorithms, algorithms for sampling and counting, Markov chain Monte Carlo (MCMC) theory
Data structures, complexity of data structures, unconditional lower bounds
Theory of parallel and distributed computing, algorithms and complexity theory for big data
Teaching
Probability Theory: Fall 2024 (at Suzhou campus), Spring 2024, Spring 2023
Advanced Algorithms: Fall 2024, Fall 2023, Fall 2022, Fall 2021, Fall 2020, Fall 2019, Fall 2018, Fall 2017, Fall 2016
Combinatorics: Spring 2024, Spring 2023, Fall 2019, Fall 2017, Fall 2016, Fall 2015, Spring 2014, Spring 2013, Fall 2011, Fall 2010
Randomized Algorithms: Fall 2015, Spring 2014, Spring 2013, Fall 2011, Spring 2010
Other teaching experiences:
Probability and Computing, Summer course for the ACM Honor Class at Shanghai Jiao Tong University, Summer 2013--2016
Communication Complexity, BASICS Summer School 2015
Seleted Topics in Theoretical Computer Science, Spring 2019
Approximation Algorithms seminar, Fall 2011
Students
Recruiting: 欢迎对理论计算机科学以及计算机科学中的数学感兴趣的同学与我联系。有数理背景、或算法相关的竞赛及科研经历者优先。
Current students:
Hongyi Chen (Master student)
Xiaoyu Chen (PhD student)
Tianxing Ding (PhD student)
Xinyu Fu (PhD student, co-advised with Chaodong Zheng)
Hongyang Liu (PhD student)
Chunyang Wang (PhD student)
Xudong Wu (PhD student, co-adivised with Penghui Yao)
Yixiao Yu (PhD student, co-advised with Jingcheng Liu)
Xinyuan Zhang (PhD student)
Can Zhou (Master student)
Zongrui Zou (PhD student, co-advised with Jingcheng Liu)
Former students and interns:
Haimin Chen (PhD student 2016-2021, co-advised with Chaodong Zheng; now a researcher at Huawei Technologies Co., Ltd.)
Weiming Feng (PhD student 2016-2021; recipient of CCF 优秀博士学位论文奖; Junior Fellow at the Institute for Theoretical Studies, ETH Zürich; joining the faculty of the School of Computing and Data Science at The University of Hong Kong in 2025)
Mingmou Liu (PhD student 2015-2020; recipient of the NSFC Overseas Outstanding Young Scholar Award (海外优青); currently a faculty member in the School of Intelligent Software and Engineering at Nanjing University, Suzhou campus)
Renjie Song (Master student; now a researcher at Megvii Research Nanjing 旷视南京研究院)
Yonggang Jiang (undergraduate research intern; now a PhD student in Max Planck Institute for Informatics)
Yuxin Sun (undergraduate research intern; PhD in Wisconsin-Madison)
Xin Huang (undergraduate research intern; PhD in CUHK; now an Assistant Professor in Kyushu University)
Publications
My [dblp], [Google Scholar] and [arxiv] profiles.
The co-authors of papers are listed in alphabetical order. (根据理论计算机科学惯例，论文作者按姓氏字母序)
Parallelize Single-Site Dynamics up to Dobrushin Criterion [doi]
with Hongyang Liu.
Accepted to Journal of the ACM (JACM).
Spectral Independence Beyond Total Influence on Trees and Related Graphs [arxiv]
with Xiaoyu Chen, Xiongxin Yang and Xinyuan Zhang.
In the 2025 ACM-SIAM Symposium on Discrete Algorithms (SODA 2025).
A Sampling Lovász Local Lemma for Large Domain Sizes [arxiv]
with Chunyang Wang.
In the 65th Annual Symposium on Foundations of Computer Science (FOCS 2024).
Locally-iterative (Δ+1)-Coloring in Sublinear (in Δ) Rounds [arxiv]
with Xinyu Fu and Chaodong Zheng.
In the 29th International Conference on Computing and Combinatorics (COCOON 2023).
Uniqueness and Rapid Mixing in the Bipartite Hardcore Model [arxiv]
with Xiaoyu Chen and Jingcheng Liu.
In the 64th Annual Symposium on Foundations of Computer Science (FOCS 2023).
Towards derandomising Markov chain Monte Carlo [arxiv]
with Weiming Feng, Heng Guo, Chunyang Wang and Jiaheng Wang.
In the 64th Annual Symposium on Foundations of Computer Science (FOCS 2023).
Deterministic counting Lovász local lemma beyond linear programming [arxiv] [doi]
with Kun He and Chunyang Wang.
In the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA 2023).
Sampling Lovász local lemma for general constraint satisfaction solutions in near-linear time [arxiv]
with Kun He and Chunyang Wang.
In the 63rd Annual Symposium on Foundations of Computer Science (FOCS 2022).
Optimal mixing for two-state anti-ferromagnetic spin systems [arxiv]
with Xiaoyu Chen, Weiming Feng and Xinyuan Zhang.
In the 63rd Annual Symposium on Foundations of Computer Science (FOCS 2022).
Polynomial-Time Approximation of Zero-Free Partition Functions [arxiv]
with Penghui Yao and Xinyuan Zhang.
In the 49th International Colloquium on Automata, Languages and Programming (ICALP 2022).
Perfect sampling from spatial mixing [arxiv] [doi]
with Weiming Feng and Heng Guo.
Random Structures & Algorithms 61(4): 678-709 (2022).
Simple Parallel Algorithms for Single-Site Dynamics [arxiv]
with Hongyang Liu.
In the 54th ACM Symposium on Theory of Computing (STOC 2022).
Rapid mixing of Glauber dynamics via spectral independence for all degrees [arxiv] [doi]
with Xiaoyu Chen, Weiming Feng and Xinyuan Zhang.
In the 62nd Annual Symposium on Foundations of Computer Science (FOCS 2021).
Invited to SIAM Journal on Computing (SICOMP).
Sampling Constraint Satisfaction Solutions in the Local Lemma Regime [arxiv]
with Weiming Feng and Kun He.
In the 53rd ACM Symposium on Theory of Computing (STOC 2021).
Dynamic inference in probabilistic graphical models [arxiv] [pdf]
with Weiming Feng, Kun He, and Xiaoming Sun.
In the 12th Innovations in Theoretical Computer Science (ITCS 2021).
Rapid mixing from spectral independence beyond the Boolean domain [arxiv] [doi]
with Weiming Feng, Heng Guo, and Chihao Zhang.
In the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2021).
ACM Trans. Algorithms (TALG) 18(3): 28:1-28:32 (2022)
Distributed Metropolis sampler with optimal parallelism [arxiv]
with Weiming Feng, Thomas P. Hayes.
In the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2021).
Succinct Filters for Sets of Unknown Sizes [arxiv]
with Mingmou Liu and Huacheng Yu.
In the 47th International Colloquium on Automata, Languages and Programming (ICALP 2020).
Fast Sampling and Counting k-SAT Solutions in the Local Lemma Regime [arxiv] [doi]
with Weiming Feng, Heng Guo, and Chihao Zhang.
In the 52nd ACM Symposium on Theory of Computing (STOC 2020).
Journal of the ACM (JACM) 68(6): 40:1-40:42 (2021).
Dynamic Sampling from Graphical Models [arxiv] [doi] [slides]
with Weiming Feng and Nisheeth Vishnoi.
In the 51st ACM Symposium on Theory of Computing (STOC 2019).
SIAM Journal on Computing (SICOMP) 50(2): 350-381 (2021).
On Local Distributed Sampling and Counting [arxiv] [slides]
with Weiming Feng.
In the 37th ACM Symposium on Principles of Distributed Computing (PODC 2018).
What can be sampled locally? [arxiv] [doi] [slides]
with Weiming Feng and Yuxin Sun.
In the 36th ACM Symposium on Principles of Distributed Computing (PODC 2017).
Invited to Distributed Computing 33(3): 227-253 (2020).
Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model [arxiv] [doi] [slides]
with Charilaos Efthymiou, Thomas Hayes, Daniel Štefankovič, and Eric Vigoda.
In the 57th Annual Symposium on Foundations of Computer Science (FOCS 2016).
Invited to SIAM Journal on Computing (SICOMP) 48(2): 581-643 (2019).
Randomized approximate nearest neighbor search with limited adaptivity [arxiv] [doi]
with Mingmou Liu and Xiaoyin Pan.
In the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2016). Outstanding paper (best paper finalists).
Invited to ACM Transactions on Parallel Computing (TOPC) 5(1): 3:1-3:26 (2018).
Counting hypergraph matchings up to uniqueness threshold [arxiv] [doi] [slides]
with Renjie Song and Jinman Zhao.
In the 20th International Workshop on Randomization and Computation (RANDOM 2016).
Information and Computation (IANDC) 266: 75-96 (2019).
Spatial mixing and approximate counting for Potts model on graphs with bounded average degree [arxiv]
with Chihao Zhang.
In the 20th International Workshop on Randomization and Computation (RANDOM 2016).
Simple average-case lower bounds for approximate near-neighbor from isoperimetric inequalities [arxiv] [slides]
In the 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016).
Spatial mixing and the connective constant: Optimal bounds [arxiv] [doi] [slides]
with Alistair Sinclair, Piyush Srivastava, and Daniel Štefankovič.
In the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA 2015).
Probability Theory and Related Fields (PTRF) 168: 153 (2017).
Spatial Mixing of Coloring Random Graphs [arxiv] [slides]
In the 41st International Colloquium on Automata, Languages and Programming (ICALP 2014).
Certificates in Data Structures [arxiv]
with Yaoyu Wang.
In the 41st International Colloquium on Automata, Languages and Programming (ICALP 2014).
Approximate Capacities of Two-Dimensional Codes by Spatial Mixing [arxiv]
with Yi-Kai Wang and Sheng Zhong.
In 2014 IEEE International Symposium on Information Theory (ISIT 2014).
Belief Propagation for Spatial Spectrum Access Games
with Yi-Kai Wang and Sheng Zhong.
In the 15th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2014).
Spatial mixing and approximation algorithms for graphs with bounded connective constant [arxiv]
with Alistair Sinclair and Piyush Srivastava.
In 54th Annual Symposium on Foundations of Computer Science (FOCS 2013).
Improved FPTAS for Multi-Spin Systems [slides] [preprint]
with Pinyan Lu.
In the 17th International Workshop on Randomization and Computation (RANDOM 2013).
Approximate Counting via Correlation Decay on Planar Graphs [arxiv] [slides]
with Chihao Zhang.
In the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA 2013).
Correlation Decay up to Uniqueness in Spin Systems [arxiv] [slides]
with Liang Li and Pinyan Lu.
In the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA 2013).
Approximate Counting via Correlation Decay in Spin Systems [arxiv] [slides]
with Liang Li and Pinyan Lu.
In the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA 2012).
Randomized Load Balancing by Joining and Splitting Bins [doi]
with James Aspnes.
Information Processing Letters (IPL) 112(8-9): 309-313 (2012).
Expander graph based overlapped chunked codes
with Sanglu Lu, Bin Tang, Shenghao Yang, and Baoliu Ye.
In 2012 IEEE International Symposium on Information Theory (ISIT 2012).
Low-Contention Data Structures [doi]
with James Aspnes and David Eisenstat.
In the 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2010).
Journal of Parallel and Distributed Computing (JPDC) 72(5): 705-715 (2012).
Assigning Tasks for Efficiency in Hadoop [preprint]
with Michael J. Fischer and Xueyuan Su.
In the 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2010).
Cell-Probe Proofs [preprint]
ACM Transactions on Computation Theory (ToCT) 2(1): 1:1-1:17 (2010).
Cell-probe proofs and nondeterministic cell-probe complexity [preprint]
In the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008).
Ranged hash functions and the price of churn [preprint]
with James Aspnes and Muli Safra.
In the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA 2008).
Path-independent load balancing with unreliable machines [arxiv]
with James Aspnes and Yang Richard Yang.
In the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007).
Fast construction of overlay networks [preprint]
with Dana Angluin, James Aspnes, Jiang Chen, and Yinghua Wu.
In the 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2005).
Invited talks
Theoretical Foundations for Computational Sampling [slides]
UESTC Algorithms and Logic Group Seminar, Sichuan, November 2023.
Central South University (CSU) 中南大学计算机学院第五届研究生学术年会, Keynote, Hunan, November 2023.
HUAWEI “Future Network Frontier” China-Russia Network Basic Theory Workshop, Moscow, September 2023.
The 1st International Conference on Machine Learning and Statistics, Keynote, Shanghai, August 2023.
National Conference of Theoretical Computer Science (NCTCS), Keynote, Guangdong, July 2023.
Sampling in High-Dimensional Space in Network Environment [slides]
Invited talk at Huawei Strategy & Technology Workshop (STW), Shenzhen, Semptember 2022.
Fast Sampling Constraint Satisfaction Solutions via the Lovász Local Lemma [slides]
The 2nd (Jinan) Workshop on Combinatorial Optimization and Algorithms, Jinan, May 2021.
The 15th Frontiers of Algorithmics Workshop (FAW), keynote, August 2021.
Fudan Science and Innovation Forum 2021, Data Science and Artificial Intelligence Sub-Forum, Fudan University, December 2021.
Dynamic and Distributed Algorithms for Sampling from Gibbs Distributions [slides] [video]
STOC 2020 workshop: New Frontiers in Approximate Counting, June 2020.
Distributed Algorithms for MCMC Sampling [slides]
Shonan Meeting (No. 162) on Distributed Graph Algorithms, Shonan Village Center, Japan, November 2019.
Sampling & Counting for Big Data [slides]
Panel talk at National Conference of Theoretical Computer Science (NCTCS), Lanzhou, August 2019.
Dynamic Sampling from Graphical Models [slides]
Applications of Partition Functions workshop, Bernoulli center, EPFL, November 2018.
Local Distributed Sampling from Locally-Defined Distribution [slides]
Laboratory for Foundations of Computer Science, University of Edinburgh, August 2018.
Introduction to the Correlation Decay Method [slides]
Introduction to Partition Functions workshop, Bernoulli center, EPFL, July 2018.
What can be sampled locally? [slides]
Dagstuhl Seminar on Computational Counting (17341), Schloss Dagstuhl, August 2017.
Counting Complexity and Phase Transitions Reunion workshop, Simons Institute for the Theory of Computing, UC Berkeley, June 2017.
Discrete Optimization Youth Forum, National Congress on Mathematical Programming of China, May 2017.
Sampling up to the Uniqueness Threshold [slides]
Computation and Algorithms workshop, Chinese Academy of Sciences, April 2017.
Rectangle Inequalities for Data Structure Lower Bounds [video] [slides]
Formal Methods Meets Theory workshop, Southwest University, December 2016.
Computation and Algorithms workshop, Zhejiang University, June 2016.
Nexus of Information and Computation Theories: Fundamental Inequalities and Lower Bounds, Institut Henri Poincaré, February 2016.
Counting with Bounded Treewidth [video] [slides]
The Classification Program of Counting Complexity workshop, Simons Institute for the Theory of Computing, UC Berkeley, April 2016.
Decay of Correlation in Spin Systems [video] [slides]
Counting Complexity and Phase Transitions Boot Camp workshop, Simons Institute for the Theory of Computing, UC Berkeley, January 2016.
Phase transition of hypergraph matchings [slides]
ARC seminar series, Algorithms and Randomness Center, Georgia Institute of Technology, September 2015.
KAIST theory day, KAIST, May 2015.
Correlation Decay up to Uniqueness in Spin Systems [slides]
Academia Sinica, Taipei, December 2014.
Workshop on Computation and Phase Transitions, Algorithms and Randomness Center, Georgia Institute of Technology, June 2012.
Department of Computer Science and Engineering, HKUST, December 2011.
Chinese Academy of Sciences, December 2011.
A tutorial on the The Beauty of the Theory of Computing (计算理论之美) for high schoolers.
A popular science lecture Quest for Artificial Intelligence (人工智能探秘) for elementary school students.
A popular science lecture The Magical Wild Animals (神奇的动物) for kindergarten kids.
Awards & Grants
Combinatorics was voted as "The Good Course in My Mind" (我心目中的好课程) by the 2024 graduating class, 2024
Advance Algorithms was voted as "The Good Course in My Mind" (我心目中的好课程) by the 2024 graduating class, 2024
New Cornerstone Investigator (新基石研究员), 2023
Advisor of Outstanding Doctoral Dissertation in Jiangsu Province (江苏省优秀博士学位论文导师) and in Nanjing University (南京大学优秀博士学位论文导师), 2022
Advisor of CCF Outstanding Doctoral Dissertation (CCF优秀博士学位论文导师), 2021
CCF-IEEE CS Young Scientist Award (CCF-IEEE CS青年科学家奖), 2019
Advance Algorithms was voted as "The Good Course in My Mind" (我心目中的好课程) by the 2019 graduating class, 2019
May 4th Youth Medal of Nanjing University (南京大学青年五四奖章), 2019
PI of National Key R&D Program of China 2018YFB1003200, "Theoretical Fundations of Data Science", (国家重点研发计划“数据科学的若干基础理论”项目负责人), 2018--2021
Du Xia Teaching Award of Nanjing University (南京大学杜厦奖教金), 2018
Combinatorics was voted as "The Good Course in My Mind" (我心目中的好课程) by the 2018 graduating class, 2018
NSF China Excellent Young Scholars (国家自然科学基金优秀青年科学基金), 2017
Teaching award in the Department of Computer Science and Technology of Nanjing University (南京大学计算机系奖教金), 2015
CVIC SE Software Prize (中创软件人才奖), 2014
StarTrack fellowship for young scholars from Microsoft Research Asia (微软亚洲研究院“铸星计划”学者), 2011
New Century Excellent Talents (NCET) in University (教育部新世纪优秀人才), 2009
Assorted other pages
TCS wiki, a wiki site run by the Theory Group for hosting webpages for courses, workshops and seminars
My wife Yang Zhang, who is a professor in Atmospheric Sciences at Nanjing University
Some MCMC, sampling and counting courses:
Probability and Computation by Constantinos Daskalakis
Eigenvalues and Polynomials by Lap Chi Lau
Counting and Sampling and Polynomial Paradigm in Algorithm Design by Shayan Oveis Gharan
Sampling Algorithms by Richard Peng
Rapidly Mixing Markov Chains by Dana Randall
Partition functions: algorithms & complexity by Alistair Sinclair
Analysis of Markov chains by Piyush Srivastava
Markov Chain Monte Carlo (MCMC) Algorithms by Eric Vigoda
and Mark Jerrum's book (search for "Counting, sampling and integrating" in the publication list)
Some theory toolkits and math tools courses:
Theorist's Toolkit: Sanjeev Arora's course and lecture notes, Ryan O'Donnell's course, Santosh Vempala's course
Mathematical Tools: Nati Linial's course
The Foundations of Data Science book of Avrim Blum, John Hopcroft, and Ravindran Kannan
Some very good leture notes on Randomized Algorithms, Theory of Distributed Computing, Computational Complexity, and Discrete Maths by my Ph.D. advisor James Aspnes