This is the Theory Group in the Department of Computer Science and Technology at Nanjing University. Our research focuses on Theoretical Computer Science (TCS). Research interests of the members of the theory group include:
Algorithms: randomized algorithms, graph algorithms, parameterized algorithms, sampling and counting
Big data: theory of distributed computing, data structures, algorithms for large-scale graphs, data analysis, differential privacy
Complexity: hardness of approximation, fine-grained and parameterized complexity, computational phase transitions, unconditional lower bounds
Quantum: quantum algorithms, quantum complexity theory, quantum information theory, quantum cryptography
We are recruiting:
Prospective graduate students, postdocs, and undergraduate research interns are encouraged to contact individual faculty members.
For candidates who are interested in applying for our faculty positions, please contact Professor Yitong Yin.
Bingkai Lin (林冰凱), Professor Ph.D., University of Tokyo, 2016 Hardness of Approximation, Parameterized Complexity, Fine-grained Complexity Email: lin (AT) nju.edu.cn |
Jingcheng Liu (刘景铖), Associate Professor Ph.D., University of California, Berkeley, 2019 Counting and Sampling, Computational Phase Transitions, Differential Privacy Email: liuexp (AT) gmail.com |
Penghui Yao (姚鹏晖), Associate Professor Ph.D., National University of Singapore, 2014 Classic/Quantum Communication Complexity, Information Theory, Quantum Computing Email: pyao (AT) nju.edu.cn |
Yitong Yin (尹一通), Professor Ph.D., Yale University, 2009 Randomized Algorithms, Data Structures, Theory of Parallel and Distributed Computing Email: yinyt (AT) nju.edu.cn |
Chaodong Zheng (郑朝栋), Research Assistant Professor Ph.D., National University of Singapore, 2015 Distributed Algorithms, Theoretical Aspects of Wireless Computing, Network Algorithms Email: chaodong (AT) nju.edu.cn |
Haimin Chen (陈海敏), PhD student (2016- )
Minglong Qin (钦明珑), Master student (2018-2020), PhD student (2020- )
Tianxing Wang (王天行), Master student (2019- )
Xiaoyu Chen (陈小羽), PhD student (2020- )
Hongyang Liu (刘弘洋), PhD student (2020- )
Changsheng Wang (汪昌盛), Master student (2020- )
Chunyang Wang (王淳扬), PhD student (2020- )
Xudong Wu (吴旭东), PhD student (2020- )
Xinyuan Zhang (张昕渊), Master student (2020- )
Mingnan Zhao (赵铭南), PhD student (2020- )
Zongbo Bao (鲍宗博), Master student (2021- )
Huairui Chu (褚怀瑞), Master student (2021- )
Yangjing Dong (董杨静), PhD student (2021- )
Xinyu Fu (傅心语), Master student (2021- )
Shuangle Li (李双乐), Master student (2021- )
Haoqi Wang (王皞琪), PhD student (2021- )
Zekun Ye (叶泽坤), PhD student (2021- )
Past Students:
Weiming Feng (凤维明), Phd student (2016-2021), Postdoc at the University of Edinburgh.
Mingmou Liu (刘明谋), Phd student (2015-2020), Postdoc at Nanyang Technological University.
Renjie Song (宋仁杰), Master student (2015-2018), joined Megvii Research Nanjing (旷视南京研究院).
Yuxin Sun (孙宇鑫), Undergraduate student (2013-2017), now PhD student in Wisconsin-Madison.
Jinman Zhao (赵金满), Undergraduate student (2011-2015), now PhD student in Wisconsin-Madison.
Xin Huang (黄昕), Undergraduate student (2010-2014), now PhD candidate in CUHK.
Advanced Algorithms (高级算法)
Combinatorics (组合数学)
Computational Complexity (计算复杂性)
Data Structure and Algorithms (数据结构与算法) at School of Artificial Intelligence
Elements of Information Theory (信息论基础)
Quantum Computing (量子计算)
Past Courses:
Advanced Algorithms (高级算法): Fall 2019, Fall 2018, Fall 2017, Fall 2016.
Combinatorics (组合数学): Fall 2019, Fall 2017, Fall 2016, Fall 2015, Spring 2014, Spring 2013, Fall 2011, Fall 2010.
Quantum Computing (量子计算): Fall 2019.
Randomized Algorithms (随机算法): Fall 2015, Spring 2014, Spring 2013, Fall 2011, Spring 2010.
Approximation Algorithms Seminar (近似算法讨论班): Fall 2011.
Weakly seminars on the state-of-the-arts and basic knowledges in Theoretical Computer Science. Students and faculties from all areas are welcomed.
For more information, check out the seminar's homepage.
Time & Location | Title & Speaker | Further Information |
---|
Google Calendar contains upcoming events.
In Theoretical Computer Science, the authors are usually listed in alphabetical order. 根据理论计算机科学的国际惯例，论文作者按姓氏字母排序。
Weiming Feng, Heng Guo, Yitong Yin, Chihao Zhang. Fast Sampling and Counting k-SAT Solutions in the Local Lemma Regime. Journal of the ACM (JACM) 68(6): 40:1-40:42 (2021). (Conference version in STOC 2020.)
Xiaoyu Chen, Weiming Feng, Yitong Yin, Xinyuan Zhang. Rapid Mixing of Glauber Dynamics via Spectral Independence for All Degrees. Proceedings of the 62nd Annual Symposium on Foundations of Computer Science (FOCS), 2021.
Haimin Chen, Yonghang Jiang, Chaodong Zheng. Tight Trade-off in Contention Resolution without Collision Detection. Proceedings of the 40th ACM Symposium on Principles of Distributed Computing (PODC), 2021.
Weiming Feng, Kun He, Yitong Yin. Sampling Constraint Satisfaction Solutions in the Local Lemma Regime. Proceedings of the 53rd ACM Symposium on Theory of Computing (STOC), 2021.
Bingkai Lin. Constant Approximating k-Clique is W[1]-hard. Proceedings of the 53rd ACM Symposium on Theory of Computing (STOC), 2021.
Weiming Feng, Nisheeth Vishnoi, Yitong Yin. Dynamic Sampling from Graphical Models. SIAM Journal on Computing (SICOMP) 50(2): 350-381 (2021). (Conference version in STOC 2019.)
Weiming Feng, Kun He, Xiaoming Sun, Yitong Yin. Dynamic inference in probabilistic graphical models. Proceedings of the 12th Innovations in Theoretical Computer Science (ITCS), 2021.
Weiming Feng, Heng Guo, Yitong Yin, Chihao Zhang. Rapid mixing from spectral independence beyond the Boolean domain. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021.
Weiming Feng, Thomas P. Hayes, Yitong Yin. Distributed Metropolis sampler with optimal parallelism. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021.
Mingmou Liu, Yitong Yin, Huacheng Yu. Succinct Filters for Sets of Unknown Sizes. Proceedings of the 47th International Colloquium on Automata, Languages and Programming (ICALP), 2020.
Mingmou Liu, Huacheng Yu. Lower Bound for Succinct Range Minimum Query. Proceedings of the 52nd ACM Symposium on Theory of Computing (STOC), 2020.
Penghui Yao. A Doubly Exponential Upper Bound on Noisy EPR States for Binary Games. The 23rd Annual Conference on Quantum Information Processing (QIP), 2020.
Anurag Anshu, Penghui Yao. On the Compression of Messages in the Multi-Party Setting. IEEE Transaction on Information Theory (TIT) 66(4): 2091-2114 (2020).
Heng Guo, Jingcheng Liu, Pinyan Lu. Zeros of Ferromagnetic 2-spin Systems. Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020.
Ken-ichi Kawarabayashi, Bingkai Lin. A nearly 5/3-approximation FPT Algorithm for Min-k-Cut. Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020.
Jingcheng Liu, Alistair Sinclair, Piyush Srivastava. A Deterministic Algorithm for Counting Colorings with 2∆ Colors. Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures (FOCS), 2019.
Haimin Chen, Chaodong Zheng. Fast and Resource Competitive Broadcast in Multi-channel Radio Networks. Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science (SPAA), 2019.
Bingkai Lin. A Simple Gap-producing Reduction for the Parameterized Set Cover Problem. Proceedings of the 46th International Colloquium on Automata, Languages and Programming (ICALP), 2019. Best paper.
Jingcheng Liu, Kunal Talwar. Private Selection from Private Candidates. Proceedings of the 51st Annual ACM Symposium on the Theory of Computing (STOC), 2019.
Heng Guo, Mark Jerrum, Jingcheng Liu. Uniform Sampling Through the Lovász Local Lemma. Journal of the ACM (JACM) 66(3): 18:1-18:31 (2019). (Conference version in STOC 2017.)
Yijia Chen, Bingkai Lin. The Constant Inapproximability of the Parameterized Dominating Set Problem. SIAM Journal on Computing (SICOMP) 48(2): 513-533 (2019). (FOCS 2016 special issue.)
Charilaos Efthymiou, Thomas P. Hayes, Daniel Štefankovič, Eric Vigoda, Yitong Yin. Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model. SIAM Journal on Computing (SICOMP) 48(2): 581-643 (2019). (FOCS 2016 special issue.)
Renjie Song, Yitong Yin, Jinman Zhao. Counting Hypergraph Matchings up to Uniqueness Threshold. Information and Computation (IANDC) 266: 75-96 (2019). (Conference version in RANDOM 2016.)
Jingcheng Liu, Alistair Sinclair, Piyush Srivastava. Fisher zeros and correlation decay in the Ising model. J. Math. Phys. 60, 103304 (2019). (Conference version in ITCS 2019.)
Jingcheng Liu, Alistair Sinclair, Piyush Srivastava. The Ising Partition Function: Zeros and Deterministic Approximation . J. Stat. Phys. 174, 287–315 (2019). (Conference version in FOCS 2017.)
Debbie Leung, Ashwin Nayak, Ala Shayeghi, Dave Touchette, Penghui Yao, Nengkun Yu. Capacity Approaching Codes for Low Noise Interactive Quantum Communication. Proceedings of the 50th ACM Symposium on Theory of Computing (STOC), 2018. QIP 2018.
Weiming Feng, Yitong Yin. On Local Distributed Sampling and Counting. Proceedings of the 37th ACM Symposium on Principles of Distributed Computing (PODC), 2018.
Anurag Anshu, Ankit Garg, Aram Harrow, Penghui Yao. Expected communication cost of distributed quantum tasks. IEEE Transactions on Information Theory (TIT) 64(11): 7395-7423 (2018).
Mingmou Liu, Xiaoyin Pan, Yitong Yin. Randomized Approximate Nearest Neighbor Search with Limited Adaptivity. ACM Transactions on Parallel Computing (TOPC) 5(1): 3:1-3:26 (2018). (SPAA 2016 special issue. Best paper finalist.)
Anurag Anshu, Dave Touchette, Penghui Yao, Nengkun Yu. Exponential Separation of Quantum Communication and Classical Information. Proceedings of the 49th ACM Symposium on Theory of Computing (STOC), 2017. Plenary talk in QIP 2017.
Weiming Feng, Yuxin Sun, Yitong Yin. What Can be Sampled Locally? Proceedings of the 36th ACM Symposium on Principles of Distributed Computing (PODC), 2017.
Seth Gilbert, Fabian Kuhn, Chaodong Zheng. Communication Primitives in Cognitive Radio Networks. Proceedings of the 36th ACM Symposium on Principles of Distributed Computing (PODC), 2017.
Bingkai Lin, Yijia Chen. The Parameterized Complexity of k-Edge Induced Subgraphs. Information and Computation (IANDC) 252: 138-160 (2017). (Conference version in ICALP 2012.)
Rahul Jain, Zhaohui Wei, Penghui Yao, Shengyu Zhang. Multipartite Quantum Correlation and Communication Complexities. Computational Complexity 26(1): 199-228 (2017).
Alistair Sinclair, Piyush Srivastava, Daniel Štefankovič, Yitong Yin. Spatial Mixing and the Connective Constant: Optimal Bounds. Probability Theory and Related Fields (PTRF) 168: 153 (2017). (Conference version in SODA 2015.)
Seth Gilbert, Calvin Newport, Chaodong Zheng. Who Are You? Secure Identities in Ad Hoc Networks. Distributed Computing (DC) 30(2): 103-125 (2017). (Conference version in DISC 2014.)
Yitong Yin. Simple Average-case Lower Bounds for Approximate Near-neighbor from Isoperimetric Inequalities. Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP), 2016.
Anurag Anshu, Ankit Garg, Aram Wettroth Harrow, Penghui Yao. Lower Bound on Expected Communication Cost of Quantum Huffman Coding. Proceedings of the 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC), 2016.
Anurag Anshu, Rahul Jain, Priyanka Mukhopadhyay, Ala Shayeghi, Penghui Yao. New one shot quantum protocols with application to communication complexity. IEEE Transactions on Information Theory (TIT) 62(12): 7566-7577 (2016).
Rahul Jain, Attila Pereszlényi, Penghui Yao. A Direct Product Theorem for Bounded-round Public-coin Randomized Communication Complexity. Algorithmica 76(3): 720-748 (2016). (FOCS 2012 special issue.)
Jingcheng Liu, Pinyan Lu. FPTAS for #BIS with Degree Bounds on One Side. Proceedings of the 47th ACM Symposium on Theory of Computing (STOC), 2015.
Seth Gilbert, Fabian Kuhn, Calvin Newport, Chaodong Zheng. Efficient Communication in Cognitive Radio Networks. Proceedings of the 34th ACM Symposium on Principles of Distributed Computing (PODC), 2015.
Jingcheng Liu, Pinyan Lu. FPTAS for Counting Monotone CNF. Proceedings of the 2015 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015.
Seth Gilbert, Chaodong Zheng. SybilCast: Broadcast on the Open Airwaves. ACM Transactions on Parallel Computing (TOPC) 2(3): 16:1-16:20 (2015). (SPAA 2013 special issue.)
Rahul Jain, Attila Pereszlenyi, Penghui Yao. A Parallel Repetition Theorem for Entangled Two-Player One-Round Games under Product Distributions. Proceedings of the 29th IEEE Conference on Computational Complexity (CCC), 2014.
Yaoyu Wang, Yitong Yin. Certificates in Data Structures. Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP), 2014.
Yitong Yin. Spatial Mixing of Coloring Random Graphs. Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP), 2014.
Liang Li, Pinyan Lu, Yitong Yin. Correlation Decay up to Uniqueness in Spin Systems. Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013.
Yitong Yin, Chihao Zhang. Approximate Counting via Correlation Decay on Planar Graphs. Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013.
Liang Li, Pinyan Lu, Yitong Yin. Approximate Counting via Correlation Decay in Spin Systems. Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA), 2012.
Rahul Jain, Penghui Yao. A Parallel Approximation Algorithm for Positive Semidefinite Programming. Proceedings of the 52nd IEEE Symposium on Foundations of Computer Science (FOCS), 2011.
Michael J. Fischer, Xueyuan Su, Yitong Yin. Assigning Tasks for Efficiency in Hadoop. Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2010.
Pascal Koiran, Jürgen Landes, Natacha Portier, Penghui Yao. Adversary lower bounds for nonadaptive quantum algorithms. Journal of Computer and System Sciences (JCSS) 76(5): 347-355 (2010).
Yitong Yin. Cell-Probe Proofs. ACM Transactions on Computation Theory (TOCT) 2(1): 1:1-1:17 (2010).
We gratefully acknowledge financial support for our research activities from the National Nature Science Foundation of China (NSFC), the Ministry of Science and Technology, the Ministry of Education, etc.
PI: National Key R&D Program of China 2018YFB1003200, Theoretical Foundations of Data Science.
PI: National Nature Science Foundation of China (NSFC) for Excellent Young Scholars, Grant No. 61722207: "Theoretical Computer Science".
PI: National Nature Science Foundation of China (NSFC) Grants No. 61972191: "A Study of Quantum Communication Complexity from Information-Theoretic Perspective"; No. 61672275: "Algorithms and Complexity of Local Sampling"; No. 61702255: "Algorithmic Primitives for Distributed Computing when Multiple Wireless Networks Coexist"; No. 61272081: "Algorithms and Complexity of Approximate Counting"; No. 61003023: "Certificate Complexity for Data Structures".
PI: Fundamental Research Funds for the Central Universities: "Theory and Implementation of New Quantum Algorithms Based on Photonic Systems".
PI: Program for New Century Excellent Talents in University (NCET) of Ministry of Education of China, Grant: "Data Structure Complexity Theory".
Participant: National Nature Science Foundation of China (NSFC) Grant No. 61321491, Program for Innovative Research Team in University: "Research on the Internet-Oriented Software Methodologies and Technologies".