IJTCS 2021 | 分论坛日程：CFCS理论计算青年教师分论坛

编者按

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

本期带来“CFCS理论计算青年教师”分论坛精彩介绍。

“CFCS理论计算青年教师”分论坛介绍

本次论坛邀请到了北京大学前沿计算研究中心理论方向的青年教师们，方向横跨计算复杂性理论、密码学、量子信息、量子计算、随机计算、编码理论、计算经济学、人工智能理论等。这些青年教师将在论坛分享他们最新的研究成果，欢迎大家参与！

“CFCS理论计算青年教师”分论坛主席

 

Yuqing Kong

Peking University

“CFCS理论计算青年教师”分论坛议程

时间：2021年8月17日

时间	讲者	报告题目
14:30- 14:55	Xiao Yuan	Perturbative Quantum Simulation
15:00- 15:25	Tongyang Li	Quantum Algorithms for Semideifinite Programs with Applications to Machine Learning
16:00- 16:25	Yuqing Kong	Optimizing Multi-task Peer Prediction
16:30- 16:55	Kuan Cheng	Efficient Document Exchange and Error Correcting Codes with Asymmetric Information
17:00- 17:25	Shaofeng Jiang	Streaming Algorithms for Geometric Steiner Forest

“CFCS理论计算青年教师”分论坛报告简介

 

Perturbative Quantum Simulation

Xiao Yuan, Peking University

Abstract

Approximations based on perturbation theory are the basis for most of the quantitative predictions of quantum mechanics, whether in quantum field theory, many-body physics, chemistry or other domains. Quantum computing provides an alternative to the perturbation paradigm, but the tens of noisy qubits currently available in state-of-the-art quantum processors are of limited practical utility. In this talk, we introduce perturbative quantum simulation, which combines the complementary strengths of the two approaches, enabling the solution of large practical quantum problems using noisy intermediate-scale quantum hardware. The use of a quantum processor eliminates the need to identify a solvable unperturbed Hamiltonian, while the introduction of perturbative coupling permits the quantum processor to simulate systems larger than the available number of physical qubits. After introducing the general perturbative simulation framework, we present an explicit example algorithm that mimics the Dyson series expansion. We then numerically benchmark the method for interacting bosons, fermions, and quantum spins in different topologies, and study different physical phenomena on systems of up to qubits, such as information propagation, charge-spin separation and magnetism. In addition, we use 5 physical qubits on the IBMQ cloud to experimentally simulate the 8-qubit Ising model using our algorithm. The result verifies the noise robustness of our method and illustrates its potential for benchmarking large quantum processors with smaller ones. 

Biography

Xiao Yuan received his Bachelor in theoretical physics from Peking University in 2012 and got his PhD in physics from Tsinghua University in 2016. Then he worked as a postdoc at University of Science and Technology China in 2017, at Oxford University from 2017 to 2019, and at Stanford University from 2019 to 2020. He is now an assistant professor at Center on Frontiers of Computing Studies, Peking University. Dr. Xiao Yuan's current research interests focus on near-term and universal quantum computing, and their applications.

 

Quantum Algorithms for Semideifinite Programs with Applications to Machine Learning

Tongyang Li, Peking University

Abstract

Semidefinite programming has been a central topic in the study of mathematical optimization, theoretical computer science, and operations research in the last decades. In this talk, we introduce quantum algorithms for solving SDPs with polynomial speedup compared to the best known classical algorithms. We also introduce how the quantum algorithm can be applied to training linear and kernel-based classifiers, as well as solving general matrix games. The talk is based on three papers: https://arxiv.org/abs/1710.02581, https://arxiv.org/abs/1904.02276, and https://arxiv.org/abs/2012.06519.

Biography

Tongyang Li is currently an assistant professor at Center on Frontiers of Computing Studies, Peking University. Previously he was a postdoctoral associate at the Center for Theoretical Physics, Massachusetts Institute of Technology. He received Master and Ph.D. degrees from the Department of Computer Science, University of Maryland in 2018 and 2020, respectively. He received Bachelor of Engineering from Institute for Interdisciplinary Information Sciences, Tsinghua University and Bachelor of Science from Department of Mathematical Sciences, Tsinghua University, both in 2015. Tongyang was a recipient of the IBM Ph.D. Fellowship, the NSF QISE-NET Triplet Award, and the Lanczos Fellowship.

 

Optimizing Multi-task Peer Prediction

Yuqing Kong, Peking University

Abstract

In the setting where we ask participants multiple similar possibly subjective multi-choice questions (e.g. Do you like Bulbasaur? Y/N; do you like Squirtle? Y/N), peer prediction aims to design mechanisms that encourage honest feedback without verification. A series of works have successfully designed multi-task peer prediction mechanisms where reporting truthfully is better than any other strategy (dominantly truthful), while they require an infinite number of tasks. A recent work proposes the first multi-task peer prediction mechanism, Determinant Mutual Information (DMI)-Mechanism, where not only is dominantly truthful but also works for a finite number of tasks (practical). However, few works consider how to optimize the multi-task peer prediction mechanisms. In addition to the definition of optimization goal, the biggest challenge is we do not have space for optimization since there is only a single practical and dominantly truthful mechanism. This work addresses this problem by proposing a tractable effort incentive optimization goal and generalizing DMI-Mechanism to a new family of practical, dominantly truthful mechanisms, Volume Mutual Information (VMI)-Mechanisms. We show that DMI-Mechanism may not be optimal. But we can construct a sequence of VMI-Mechanisms that are approximately optimal. The main technical tool is a novel family of mutual information measures, Volume Mutual Information, which generalizes Determinant Mutual Information. We construct VMI by a simple geometric idea: we measure how informative a distribution is by measuring the volume of distributions that is less informative than it (inappropriately, it's similar to measuring how clever a person is by counting the number of people that are less clever than he/she).

Biography

Yuqing Kong is currently an assistant professor at The Center of Frontier Computing Science (CFCS), Peking University. She obtained her Ph.D. degree from the Computer Science and Engineering Department at University of Michigan in 2018 and her bachelor degree in mathematics from University of Science and Technology of China in 2013.

Her research interests lie in the intersection of theoretical computer science and the areas of economics: information elicitation, prediction markets, mechanism design, and the future applications of these areas to crowdsourcing and machine learning. Her papers were published in several conferences include WINE, ITCS, EC, SODA, AAAI, NeurIPS, ICLR, ECCV, IJCAI.

 

Efficient Document Exchange and Error Correcting Codes with Asymmetric Information

Kuan Cheng, Peking University

Abstract

The talk is about our studies on Document Exchange Protocol (DEP). The problem is considering that two parties hold two strings, and one party tries to learn the other party's string through communication. DEP has been studied extensively during the past decades. We first focus on whether asymmetric partial information can help under Hamming distance. The asymmetric partial information is modeled by one party having a vector of disjoint subsets  of indices and a vector of integers  , such that in each   the Hamming distance/errors is at most  . We establish both lower bounds and upper bounds in this model, and provide efficient randomized constructions with near optimal communication complexity.

We then exposit the connection to the corresponding problems under edit distance, giving an efficient DEP with optimal communication complexity and exponentially small error. This improves the previous result by Haeupler [Hae19] (FOCS'19) and that by Belazzougui and Zhang [BZ16] (FOCS'16).

We will also talk about constructions for Error Correcting Codes with asymmetric information, as simple variations of our methods. Our techniques are based on a generalization of the celebrated expander codes by Sipser and Spielman [SS96], which may be of independent interests.

Biography

Kuan Cheng is currently an asistant professor at Center on Frontiers of Computing Studies, Peking University. Previously He was a Postdoc at University of Texas at Austin. Before that he achieved a PhD degree from Johns Hopkins University. His research interests mainly include coding theory and randomness in computation, and their applications. He is also interested in Machine Learning, Quantum Computing and other topics in Computer Science.

 

Streaming Algorithms for Geometric Steiner Forest

Shaofeng Jiang, Peking University

Abstract

We consider a natural generalization of the Steiner tree problem, the Steiner forest problem, in the Euclidean plane: the input is a multiset  , partitioned into  color classes  . The goal is to find a minimum-cost Euclidean graph  such that every color class  is connected in  . We study this Steiner forest problem in the streaming setting, where the stream consists of insertions and deletions of points to  . Each input point  arrives with its color  , and as usual for dynamic geometric streams, the input points are restricted to the discrete grid  .

We design a single-pass streaming algorithm that uses  space and time, and estimates the cost of an optimal Steiner forest solution within ratio arbitrarily close to the famous Euclidean Steiner ratio  (currently  ). Our approach relies on a novel combination of streaming techniques, like sampling and linear sketching, with the classical dynamic-programming framework for geometric optimization problems, which usually requires large memory and has so far not been applied in the streaming setting.

Biography

Shaofeng Jiang is an assistant professor at Center on Frontiers of Computing Studies, Peking University. He obtained his Ph.D. from the University of Hong Kong, and he worked as a postdoctoral researcher at the Weizmann Institute of Science. He was an assistant professor at Aalto University before moving to Peking University. His research interest is generally theoretical computer science, with a focus on algorithms for massive datasets and approximation algorithms.

关于IJTCS

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

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

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

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

日程 → 分论坛：量子计算

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

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

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

日程 → 特   色：有意识的图灵机

日程 → 特   色：本科生论坛

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

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

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

文字 | 周子鑫

—   版权声明  —

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

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