IJTCS 2021 | 大会特邀报告介绍

编者按

第二届国际理论计算机联合大会（International Joint Conference on Theoretical Computer Science，IJTCS）将于2021年8月16日-20日在线上线下交互举行，由北京大学与中国工业与应用数学学会（CSIAM）、中国计算机学会（CCF）、国际计算机学会中国委员会（ACM China Council）联合主办，北京大学前沿计算研究中心承办，图灵奖获得者、中科院外籍院士、北京大学访问讲席教授John Hopcroft教授任大会主席。

本期带来“大会特邀报告”精彩介绍。

大会特邀报告人

按报告人姓名拼音排序

 

Lenore Blum

卡内基梅隆大学杰出教授、北京大学访问讲席教授。她建立了实数域的计算和复杂性理论，为科学计算奠定了理论基础；发明了可在密码中安全使用的随机数生成算法，为密码学做出了杰出贡献。

 

Manuel Blum

卡内基梅隆大学讲席教授、北京大学访问讲席教授。他是密码系统和程序检验先驱，计算复杂性理论的主要奠基人之一，因奠定了计算复杂性理论的基础和在密码术及程序校验方面的贡献获得获图灵奖。

 

陈   婧

Algorand首席科学家、纽约州立大学石溪分校助理教授。主要研究领域是分布式账本、博弈论、机制设计和算法。

 

陈   卫

微软亚洲研究院首席研究员、清华大学兼职教授、中国科学院客座研究员，IEEE Fellow，近期入选斯坦福大学全球前2%顶尖科学家榜单。研究兴趣包括社交和信息网络，在线学习，算法博弈论，互联网经济学，分布式计算和容错能力。

 

陈   汐

哥伦比亚大学副教授。主要研究领域为算法博弈论与复杂性理论。

 

陈翌佳

上海交通大学教授。主要研究领域为逻辑与复杂性。

 

栗   师

纽约州立大学布法罗分校副教授。主要研究领域为设计关于调度、集群、设施定址和网络的有效算法。

 

尹一通

南京大学教授，2019年获得CCF-IEEE CS青年科学家奖。主要研究兴趣为具体复杂性的模型与下界和现代算法设计与分析。

特邀报告介绍

Insights from the Conscious Turing Machine

2021年8月18日9:00-9:55

Abstract

The quest to understand consciousness, once the purview of philosophers and theologians, is now actively pursued by scientists of many stripes.  In this talk, we discuss consciousness from the perspective of theoretical computer science (TCS), a branch of mathematics concerned with understanding the underlying principles of computation and complexity, especially the implications of resource limitations.  In the manner of TCS, we formalize the Global Workspace Theory (GWT) originated by cognitive neuroscientist Bernard Baars and further developed by him, Stanislas Dehaene, and others.  Our principal contribution lies in the precise formal definition of a Conscious Turing Machine (CTM).  We define the CTM in the spirit of Alan Turing's simple yet powerful definition of a computer, the Turing Machine (TM).  We are not looking for a complex model of the brain nor of cognition but for a simple model of (the admittedly complex concept of) consciousness.

After defining CTM, we give a formal definition of consciousness in CTM.  We then suggest why the CTM has the feeling of consciousness.  The perspective given here provides a simple formal framework to employ tools from computational complexity theory and machine learning to further the understanding of consciousness.

This is joint work of Manuel, Lenore and Avrim Blum. 

Biography

Manuel Blum is a Professor of CS Emeritus at U.C. Berkeley (30 years) and CMU (20 years), and Visiting Chair Professor of CS at Peking University (2 years).  His recent work on Conscious Turing Machines satisfies his long standing desire to learn how to think, which he tried and continues trying to do by understanding brains, machines, mathematics, cognition and consciousness.  He is proudest of his talented family and the many exceptional students who got PhDs under his wing.

Lenore Blum is an American computer scientist and mathematician, Founder and Professor Emeritus of the Math and Computer Science Department at Mills College (20 years),  Distinguished Career Professor of Computer Science at Carnegie Mellon University (20 years), and Visiting Chair Professor of CS at Peking University (2 years).  She is known for stunning mathematical discoveries in the Model Theory of Differential Fields, contributions to abstract models ofcomputation, a book with Cucker, Shub, and Smale entitled Complexity and Real Computation, Springer-Verlag, (1998), and current work on a model of consciousness called the Conscious Turing Machine (CTM), among many other contributions. In 2005, she received the Presidential Award for Excellence in Science, Mathematics, and Engineering Mentoring, given her by president George W. Bush, and in 2018, she received the Simmons University Distinguished Alumnae Lifetime Achievement Award.

Speculative Smart Contracts

2021年8月19日10:00-10:55

Abstract

In this talk, I'll introduce Algorand's layer-2 speculative smart contract architecture and discuss the design principles behind it.

Biography

Jing Chen is Chief Scientist and Head of Theory Research at Algorand Inc. She is an Assistant Professor in the Computer Science Department at Stony Brook University, and an affiliated assistant professor at the Economics Department. 

Her main research interests are distributed ledgers, smart contracts, game theory, and algorithms. Jing received her bachelor's and master's degrees in computer science from Tsinghua University, and her PhD in computer science from MIT. Jing received the NSF CAREER Award in 2016.

Data-driven optimization --- Integrating data sampling, learning, and optimization

2021年8月19日9:00-9:55

Abstract

Traditionally machine learning and optimization are two different branches in computer science. They need to accomplish two different types of tasks, and they are studied by two different sets of domain experts. Machine learning is the task of extracting a model from the data, while optimization is to find the optimal solutions from the learned model. In the current era of big data and AI, however, such separation may hurt the end-to-end performance from data to optimization in unexpected ways. In this talk, I will introduce the paradigm of data-driven optimization that tightly integrates data sampling, machine learning, and optimization tasks. I will mainly explain two approaches in this paradigm, one is optimization from structured samples, which carefully utilizes the structural information from the sample data to adjust the learning and optimization algorithms; the other is combinatorial online learning, which adds feedback loop from the optimization result to data sampling and learning to improve the sample efficiency and optimization efficacy. I will illustrate these two approaches through my recent research studies in these areas.

Biography

Wei Chen is a Principal Researcher at Microsoft Research Asia, an Adjunct Professor at Tsinghua University, and an Adjunct Researcher at Chinese Academy of Sciences. He is a standing committee member of the Technical Committee on Theoretical Computer Science, Chinese Computer Federation, and a member of the CCF Technical Committee on Big Data. He is a Fellow of Institute of Electrical and Electronic Engineers (IEEE).  He is selected as one of the world's top 2% scientists by a Stanford University ranking.

Wei Chen's main research interests include online learning and optimization, social and information networks, network game theory and economics, distributed computing, and fault tolerance. He has done influential research on the algorithmic study of social influence propagation and maximization and combinatorial online learning, with 10000+ collective citations on these topics. He has one coauthored monograph in English in 2013 and one sole authored monograph in Chinese in 2020, both on information and influence propagation in social networks. He has served as editors, academic conference chairs and program committee members for many academic conferences and journals. Wei Chen has Bachelor and Master degrees from Tsinghua University and a Ph.D. degree in computer science from Cornell University.

Recent developments in property testing of Boolean functions

2021年8月16日9:30-10:25

Abstract

Over the past few decades, property testing has emerged as an important line of research in sublinear computation. At a high level, testers are ultra-fast randomized algorithms which determine whether a "massive object" satisfies a particular property while only inspecting a tiny portion of the object. In this talk, we will review some of the recent developments in property testing of Boolean functions.

Biography

Xi Chen is an associate professor in the Computer Science Department at Columbia University. He obtained his PhD from Tsinghua University in 2007. Before joining Columbia, he was a postdoctoral researcher at the Institute for Advanced Study, Princeton University and University of Southern California. His research interests lie in algorithmic game theory and complexity theory.

AC⁰ circuits, first-order logic, and well-structured graphs

2021年8月16日11:00-11:55

Abstract

In this talk, I will explain some recent results on evaluating queries on well-structured graphs using AC⁰ circuits (i.e., circuits of constant depth and polynomial size). We study those queries definable in monadic second-order logic (MSO), including NP-hard problems like 3-colorability and SAT. We exploit the well-known connection between AC⁰ and first-order logic (FO) to design our circuits by developing some machinery to describe those well-structured graphs in FO. These results yield fast parallel algorithms on certain dense graphs.

Biography

Yijia Chen is a professor of Computer Science at Shanghai Jiao Tong University. He received his PhD degree in computer science from Shanghai Jiao Tong University and PhD degree in mathematics from University of Freiburg. He mainly works in logic in computer science, computational complexity, and algorithmic graph theory. He serves on the editorial board of Logic Methods in Computer Science and of Theory of Computing Systems.

Tight Online Algorithmsfor Unrelated Machine Load Balancing with Predictions

2021年8月18日20:00-20:55

Abstract

The success of modern machine learning techniques has led to a surge of interest in using machine learned predictions to design better online algorithms for combinatorial optimization problems. This is called learning augmented online algorithms. One seeks to design a prediction about the online instance and an online algorithm which is given the prediction upfront. They should satisfy: a) usefulness, which means the prediction allows the online algorithm to achieve a better competitive ratio, b) robustness, which means the performance of the algorithm deteriorates smoothly as the noise of prediction increases, and c) learnability, which means the predicted information can be learned efficiently from past instances.

In this talk, I will present our results for the online load balancing problem in this model.  That is, we allow some prediction about the instance to be given to the online algorithm. First, we design deterministic and randomized online rounding algorithms for the problem in the unrelated machine setting, with  - and  -competitive ratios. They respectively improve upon the previous ratios of  and  of Lattanzi et al., and match their lower bounds. Second, we extend their prediction scheme from the restricted assignment setting to the unrelated machine setting. Finally, we consider the learning model introduced by Lavastida et al., and show that under the model, the prediction can be learned efficiently with a few samples of instances.

The talk is based on my joint work with Jiayi Xian.

Biography

Shi Li is an associate professor at the department of computer science and engineering at University at Buffalo. Before joining University at Buffalo in 2015, he was a research assistant professor at Toyota Technological Institute at Chicago. He received his Ph.D. in 2013 from the Department of Computer Science at Princeton University.  He received his Bachelor's degree in 2008 from the Department of Computer Science and Technology at Tsinghua University, where he was also a student of Andrew Chih-Chi Yao's special pilot class.  Professor Li's main research is the design of efficient algorithms for scheduling, clustering, facility location and network design problems under different models. 

Fast sampling constraint satisfaction solutions via the Lovász local lemma

2021年8月18日19:00-19:55

Abstract

This talk will cover some recent advances in sampling solutions of constraint satisfaction problems (CSPs) through the Lovász local lemma. We will talk about Markov chain based algorithms for sampling almost uniform CSP solutions, inspired by an LP based approach for approximately counting the number of CSP solutions due to Ankur Moitra. Assuming "local lemma" - like conditions, these Markov chain based sampling algorithms are accurate and can run in a nearly linear time in the number of variables for a broad class of CSPs.

Biography

Yitong Yin is a Professor in Computer Science in the Department of Computer Science and Technology at Nanjing University. He received his PhD in Computer Science from Yale University in 2009, and has been in the faculty of Nanjing University since then. His research interest is theoretical computing science, with focuses on randomized algorithms and data structure complexity.

关于IJTCS

回顾 → 对话邓小铁：在首届IJTCS中，我看到了中国计算理论的成长

日程 → 分论坛：算法博弈论

日程 → 分论坛：区块链技术

日程 → 分论坛：多智能体强化学习

日程 → 分论坛：机器学习理论

日程 → 分论坛：量子计算

日程 → 分论坛：人工智能与形式化方法

日程 → 分论坛：算法与复杂性

日程 → 分论坛：计算经济学

日程 → 分论坛：有意识的图灵机

日程 → 特   色：本科生论坛

日程 → 特   色：女性论坛

日程 → 特   色：青年博士论坛

日程 → 特   色：CFCS理论计算青年教师论坛

IJTCS注册信息

大会现已正式面向公众开放注册！

观看线上报告：免费

通过在线观看直播的方式参与大会，可通过直播平台提问。

线上会议注册：

（普通）$100 /￥700

（学生）$50 /￥350*

获得所有Zoom会议参会链接，作为参会人在线参加全部会议，直接在线提问讨论并参与特设互动环节。

线下会议注册：

（普通）$200 / ￥1400

（学生）$100 / ￥700*

作为参会人在线下（北京大学）参加会议，与知名学者们面对面交流；同时享受线上注册的所有权益。

*因防疫要求，仅开放10个校外线下参会名额。

点击 ↓↓↓二维码↓↓↓ 跳转注册页面

*学生注册：网站上注册后需将学生证含有个人信息和学校信息的页拍照发送至[e-mail]，邮件主题格式为＂Student Registration+姓名+线上/线下"。

大会主席 

 

John Hopcroft

图灵奖获得者

中国科学院外籍院士

北京大学访问讲席教授

大会联合主席 

 

邓小铁

北京大学讲席教授

欧洲科学院外籍院士

ACM/IEEE Fellow

顾问委员会主席 

高  文

中国工程院院士

北京大学教授

梅  宏

中国科学院院士

CCF理事长

张平文

中国科学院院士

CSIAM理事长

北京大学教授

程序委员会主席 

孙晓明

中科院计算所

研究员

邓小铁

北京大学

讲席教授

李闽溟

香港城市大学

副教授

陆品燕

上海财经大学

教授

李  建

清华大学

副教授

组织单位 

合作媒体

大会赞助

联系人

大会赞助、合作等事宜

请联系

[e-mail]

010-62761029

大会网站

https://econcs.pku.edu.cn/ijtcs2021/index.htm

↑↑扫码直达大会官网↑↑

文字 | 李东晨

—   版权声明  —

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。

点“阅读原文”转大会注册页面