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 & Complexity Theory:
Algorithms for Sampling and Approximate Counting
Communication Complexity and Data Structure Lower Bounds
Algorithms & Complexity Theory for Big Data
Quantum Computing:
Quantum Information Theory
Quantum Communication Complexity
Quantum Cryptography
Theory of Distributed Computing:
Algorithms for Wireless Networks
Distributed Graph Algorithms
Complexity of Distributed Computing
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.
Penghui Yao (姚鹏晖), Associate Professor Ph.D., National University of Singapore, 2014 Thousand Talent Program for Young Outstanding Scientists (青年千人计划) Classic/Quantum Communication Complexity, Information Theory, Quantum Computing Email: phyao1985 (AT) gmail (DOT) com |
Yitong Yin (尹一通), Professor Ph.D., Yale University, 2009 NSFC Excellent Young Scholars (优秀青年科学基金) Sampling/Counting Algorithms, Concrete Complexity, Theory of Parallel and Distributed Computing Email: yitong.yin (AT) gmail (DOT) com |
Chaodong Zheng (郑朝栋), Research Assistant Professor Ph.D., National University of Singapore, 2015 Distributed Algorithms, Theoretical Aspects of Wireless Computing, Network Algorithms Email: chaodong.gm (AT) gmail (DOT) com |
Mingmou Liu (刘明谋) PhD student, 2015-
Renjie Song (宋仁杰) Master’s student, 2015-2018, Joined Megvii Research Nanjing (旷视南京研究院)
Haimin Chen (陈海敏) PhD student, 2016-
Weiming Feng (凤维明) PhD student, 2016-
Yilin Fan (樊一麟) Master’s student, 2017-
Xiaoyin Pan (潘笑吟) Master’s student, 2017-
Yahui Liu (刘雅辉) Master’s student, 2018-
计算复杂性 Computational Complexity
Past Courses:
组合数学 Combinatorics: Fall 2016, Fall 2015, Spring 2014, Spring 2013, Fall 2011, Fall 2010.
高级算法 Advanced Algorithms: Fall 2016.
随机算法 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, Yitong Yin.
On Local Distributed Sampling and Counting.
In Proceedings of the 37th ACM Symposium on Principles of Distributed Computing (PODC), 2018.
Debbie Leung, Ashwin Nayak, Ala Shayeghi, Dave Touchette, Penghui Yao, Nengkun Yu.
Capacity Approaching Codes for Low Noise Interactive Quantum Communication.
In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2018.
Seth Gilbert, Fabian Kuhn, Chaodong Zheng.
Communication Primitives in Cognitive Radio Networks.
In Proceedings of the 36th ACM Symposium on Principles of Distributed Computing (PODC), 2017.
Weiming Feng, Yuxin Sun, Yitong Yin.
In Proceedings of the 36th ACM Symposium on Principles of Distributed Computing (PODC), 2017.
Anurag Anshu, Dave Touchette, Penghui Yao, Nengkun Yu.
Exponential Separation of Quantum Communication and Classical Information.
In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2017.
Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model.
In Proceedings of the 57th IEEE Symposium on Foundations of Computer Science (FOCS), 2016.
Counting Hypergraph Matchings up to Uniqueness Threshold.
In Proceedings of the 20th International Workshop on Randomization and Computation (RANDOM), 2016.
Mingmou Liu, Xiaoyin Pan, Yitong Yin.
Randomized Approximate Nearest Neighbor Search with Limited Adaptivity.
In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016.
Outstanding paper (best paper finalists).
Yitong Yin.
Simple Average-case Lower Bounds for Approximate Near-neighbor from Isoperimetric Inequalities.
In 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.
In Proceedings of the 11th Conference on the Theory of Quantum Computation, Communication and Cryptography. (TQC), 2016.
Seth Gilbert, Fabian Kuhn, Calvin Newport, Chaodong Zheng.
Efficient Communication in Cognitive Radio Networks.
In Proceedings of the 34th ACM Symposium on Principles of Distributed Computing (PODC), 2015.
Alistair Sinclair, Piyush Srivastava, Daniel Štefankovič, Yitong Yin.
Spatial Mixing and the Connective Constant: Optimal Bounds.
In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015.
Rahul Jain, Attila Pereszlenyi, Penghui Yao.
A Parallel Repetition Theorem for Entangled Two-Player One-Round Games under Product Distributions.
In Proceedings of the 29th Annual IEEE Conference on Computational Complexity (CCC), 2014.
Seth Gilbert, Calvin Newport, Chaodong Zheng.
Who Are You? Secure Identities in Ad Hoc Networks.
In Proceedings of the 28th International Symposium on Distributed Computing (DISC), 2014.
Yaoyu Wang, Yitong Yin.
Certificates in Data Structures.
In Proceedings of the 41rd International Colloquium on Automata, Languages and Programming (ICALP), 2014.
Yitong Yin.
Spatial Mixing of Coloring Random Graphs.
In Proceedings of the 41rd International Colloquium on Automata, Languages and Programming (ICALP), 2014.
Spatial mixing and approximation algorithms for graphs with bounded connective constant.
In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2013.
Seth Gilbert, Chaodong Zheng.
SybilCast: Broadcast on the Open Airwaves (Extended Abstract).
In Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2013.
Liang Li, Pinyan Lu, Yitong Yin.
Correlation Decay up to Uniqueness in Spin Systems.
In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013.
Yitong Yin, Chihao Zhang.
Approximate Counting via Correlation Decay on Planar Graphs.
In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013.
Rahul Jain, Attila Pereszlényi, Penghui Yao.
A Direct Product Theorem for Bounded-round Public-coin Randomized Communication Complexity.
In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2012.
Liang Li, Pinyan Lu, Yitong Yin.
Approximate Counting via Correlation Decay in Spin Systems.
In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2012.
Rahul Jain, Penghui Yao.
A Parallel Approximation Algorithm for Positive Semidefinite Programming.
In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2011.
Michael J. Fischer, Xueyuan Su, Yitong Yin.
Assigning Tasks for Efficiency in Hadoop.
In Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2010.
James Aspnes, David Eisenstat, Yitong Yin.
Low-Contention Data Structures.
In Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 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 Fundamentions 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. 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: 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".