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: graph algorithms, parameterized algorithms, randomized algorithms, algorithms for sampling and counting
Big data: communication and data strcuture lower bounds, theory of distributed computing, network algorithms, algorithms for large-scale graphs
Complexity: hardness of approximation, communication complexity, fine-grained complexity, parameterized complexity
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 |
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 Sampling/Counting Algorithms, Concrete Complexity, 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 |
Mingmou Liu (刘明谋), Master student (2015-2017), PhD student (2017- )
Haimin Chen (陈海敏), PhD student (2016- )
Weiming Feng (凤维明), 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 (赵铭楠), Master student (2020- )
Past Students:
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. 根据理论计算机科学的国际惯例，论文作者按姓氏字母排序。
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.
Weiming Feng, Heng Guo, Yitong Yin, Chihao Zhang. Fast Sampling and Counting k-SAT Solutions in the Local Lemma Regime. Proceedings of the 52st ACM Symposium on Theory of Computing (STOC), 2020.
Mingmou Liu, Huacheng Yu. Lower Bound for Succinct Range Minimum Query. Proceedings of the 52st 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).
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.
Weiming Feng, Nisheeth Vishnoi, Yitong Yin. Dynamic Sampling from Graphical Models. Proceedings of the 51st ACM Symposium on Theory of Computing (STOC), 2019.
Haimin Chen, Chaodong Zheng. Fast and Resource Competitive Broadcast in Multi-channel Radio Networks. Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2019.
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.)
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.
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.
James Aspnes, David Eisenstat, Yitong Yin. Low-Contention Data Structures. Journal of Parallel and Distributed Computing (JPDC) 72(5): 705-715 (2012). (Conference version in SPAA 2010.)
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. 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".