IJTCS 2021 | 分论坛日程：青年博士论坛
编者按
第二届国际理论计算机联合大会（International Joint Conference on Theoretical Computer Science，IJTCS）将于2021年8月16日-20日在线上线下交互举行，由北京大学与中国工业与应用数学学会（CSIAM）、中国计算机学会（CCF）、国际计算机学会中国委员会（ACM China Council）联合主办，北京大学前沿计算研究中心承办，图灵奖获得者、中科院外籍院士、北京大学访问讲席教授John Hopcroft教授任大会主席。
本期带来“青年博士论坛”的精彩介绍。
“青年博士论坛”介绍
设立青年博士论坛的其中一个目标是给理论计算机及其相关领域优秀的青年学者们一个交流的平台，让青年学者们有一个集中的机会了解到理论计算机及其相关的不同方向上大家正在攻坚的科学难题，还能产生一些可能的合作。另一个目标是起到一个榜样作用，给刚进入或还未进入理论计算机及其相关领域的学生们树立一个好榜样，鼓励同学们向这些优秀的青年学者学习，努力奋斗，争取在不久的未来，因为自己的学术成果，被邀请作为青年博士论坛的报告人回来参与活动。
“青年博士论坛”主席
Xiang Yan
Huawei TCS Lab
“青年博士论坛”议程
时间：2021年8月16日
时间 | 讲者 | 报告题目 |
21:30- 21:55 | 窦泽皓 | Making Method of Moments Great Again? -- How can GANs learn distributions |
22:00- 22:25 | 王君弢 | Cursed yet Satisfied Agents |
22:30- 23:00 | 冯 哲 | Convergence Analysis of No-Regret Bidding Algorithms in Repeated Auctions |
时间：2021年8月17日
时间 | 讲者 | 报告题目 |
11:30- 11:55 | 杨 宽 | Counting solutions to random CNF formulas |
时间：2021年8月18日
时间 | 讲者 | 报告题目 |
11:30- 11:55 | 陈宗晨 | Optimal Mixing of Glauber Dynamics via Spectral Independence Approach |
时间：2021年8月19日
时间 | 讲者 | 报告题目 |
15:30- 15:55 | 张家衡 | Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation |
16:00- 16:25 | 王培新 | Proving Expected Sensitivity of Probabilistic Programs with Randomized Variable-Dependent Termination Time |
16:30- 16:55 | 陆馨杭 | Maximin Fairness with Mixed Divisible and Indivisible Goods |
16:30- 16:55 | 廖 超 | Almost Tight Approximation Hardness for k-DST |
“青年博士论坛”报告简介
Making Method of Moments Great Again? -- How can GANs learn distributions
Zehao Dou, Yale University
Abstract
Generative Adversarial Networks (GANs) are widely used models to learn complex real-world distributions. In GANs, the training of the generator usually stops when the discriminator can no longer distinguish the generator's output from the set of training examples. A central question of GANs is that when the training stops, whether the generated distribution is actually close to the target distribution, and how the training process reaches to such configurations efficiently? In this paper, we established a theoretical results towards understanding this generator-discriminator training process. We empirically observe that during the earlier stage of the GANs training, the discriminator is trying to force the generator to match the low degree moments between the generator's output and the target distribution. Moreover, only by matching these empirical moments over polynomially many training examples, we prove that the generator can already learn notable class of distributions, including those that can be generated by two-layer neural networks.
Biography
Zehao Dou is a first year PhD student from Department of Statistics and Data Science, Yale University. Previously, he obtained his bachelor degree from School of Mathematical Sciences, Peking University (2015.9-2019.7). He has wide research interests including statistics, optimization, game theory, machine learning theory and reinforcement learning theory. His goal is to design efficient and provable algorithms, to deepen the statistical understanding, and to provide new perspective for practical machine learning problems.
Cursed yet Satisfied Agents
Juntao Wang, Harvard University
Abstract
In real life auctions, a widely observed phenomenon is the winner's curse -- the winner's high bid implies that the winner often over-estimates the value of the good for sale, resulting in an incurred negative utility. The seminal work of Eyster and Rabin [Econometrica'05] introduced a behavioral model aimed to explain this observed anomaly. We term agents who display this bias "cursed agents". We adopt their model in the interdependent value setting and aim to devise mechanisms that prevent the cursed agents from obtaining negative utility. We design mechanisms that are cursed ex-post IC, that is, incentivize agents to bid their true signal even though they are cursed, while ensuring that the outcome is individually rational -- the price the agents pay is no more than the agents' true value.
Since the agents might over-estimate the good's value, such mechanisms might require the seller to make positive transfers to the agents to prevent agents from over-paying. For revenue maximization, we give the optimal deterministic and anonymous mechanism. For welfare maximization, we require ex-post budget balance (EPBB), as positive transfers might lead to negative revenue. We propose a masking operation that takes any deterministic mechanism and imposes that the seller would not make positive transfers, enforcing EPBB. We show that in typical settings, EPBB implies that the mechanism cannot make any positive transfers, implying that applying the masking operation on the fully efficient mechanism results in a socially optimal EPBB mechanism. This further implies that if the valuation function is the maximum of agents' signals, the optimal EPBB mechanism obtains zero welfare. In contrast, we show that for sum-concave valuations, which include weighted-sum valuations and l_p-norms, the welfare optimal EPBB mechanism obtains half of the optimal welfare as the number of agents grows large.
Biography
Juntao Wang is a PhD student at the School of Engineering and Applied Science at Harvard, and a member of EconCS group at Harvard.
Convergence Analysis of No-Regret Bidding Algorithms in Repeated Auctions
Zhe Feng, Google Research
Abstract
The connection between games and no-regret algorithms has been widely studied in the literature. A fundamental result is that when all players play no-regret strategies, this produces a sequence of actions whose time-average is a coarse-correlated equilibrium of the game. However, much less is known about equilibrium selection in the case that multiple equilibria exist. In this work, we study the convergence of no-regret bidding algorithms in auctions. Besides being of theoretical interest, bidding dynamics in auctions is an important question from a practical viewpoint as well. We study repeated game between bidders in which a single item is sold at each time step and the bidder's value is drawn from an unknown distribution. We show that if the bidders use any mean-based learning rule then the bidders converge with high probability to the truthful pure Nash Equilibrium in a second price auction, in VCG auction in the multi-slot setting and to the Bayesian Nash equilibrium in a first price auction. We note mean-based algorithms cover a wide variety of known no-regret algorithms such as Exp3, UCB, -Greedy etc. Also, we analyze the convergence of the individual iterates produced by such learning algorithms, as opposed to the time-average of the sequence. Our experiments corroborate our theoretical findings and also find a similar convergence when we use other strategies such as Deep Q-Learning.
Biography
Zhe Feng is a Research Scientist at Google Research, Mountain View. He got his PhD in Computer Science at Harvard University, where he was fortunately advised by David C. Parkes. He was a recipient of Google PhD Fellowship Award. His research broadly lies in the intersection between economics and computer science, and mainly focuses on understanding how to design better mechanisms through machine learning approaches.
Counting solutions to random CNF formulas
Kuan Yang, Shanghai Jiao Tong University
Abstract
We give the first efficient algorithm to approximately count the number of solutions in the random -SAT model when the density of the formula scales exponentially with . The best previous counting algorithm was due to Montanari and Shah and was based on the correlation decay method, which works up to densities , the Gibbs uniqueness threshold for the model. Instead, our algorithm harnesses a recent technique by Moitra to work for random formulas. The main challenge in our setting is to account for the presence of high-degree variables whose marginal distributions are hard to control and which cause significant correlations within the formula.
Biography
Kuan Yang is an assistant professor in the John Hopcroft Center for Computer Science at Shanghai Jiao Tong University. He was awarded the Ph.D. degree in Computer Science by the University of Oxford in 2020. Before joining Shanghai Jiao Tong University, he was a postdoctoral researcher at Universität Hamburg.
Kuan Yang is broadly interested in theoretical computer science. Currently his research focus on approximate counting and sampling algorithms.
Optimal Mixing of Glauber Dynamics via Spectral Independence Approach
Zongchen Chen, Georgia Institute of Technology
Abstract
We consider the Glauber dynamics (also called Gibbs sampling) for sampling from a high-dimensional discrete distribution; e.g., selecting a random proper coloring or independent set in a given graph, or sampling a "typical" state of a given statistical physics model like the Ising model. In each step, the Glauber dynamics chooses a variable uniformly at random and updates its value conditional on all other variables. We show an optimal mixing time bound for the Glauber dynamics in a variety of settings. As an application of our results, for the hardcore model on weighted independent sets, we establish O(nlogn) mixing time for the Glauber dynamics on any n-vertex graph of constant maximum degree when the parameter of the model lies in the tree uniqueness region. Our results apply more broadly to other models including antiferromagnetic 2-spin systems (e.g., Ising model), random colorings, weighted matchings, and weighted partial even subgraphs.
To establish our results, we present an improved version of the spectral independence approach of Anari, Liu and Oveis Gharan (2020) and shows O(nlogn) mixing time for graphical models/spin systems on any n-vertex graph of bounded degrees when the maximum eigenvalues of associated influence matrices are bounded. Our proof approach combines classic tools like entropy tensorization/factorization and recent developments of high-dimensional expanders.
Biography
Zongchen Chen will join Massachusetts Institute of Technology as an instructor (postdoc) in applied math in Fall 2021. He received the Ph.D. degree in the Algorithms, Combinatorics and Optimization (ACO) multidisciplinary program at Georgia Institute of Technology. He was fortunate to be advised by Eric Vigoda. Before that, he received the Bachelor's degree in Math & Applied Math from Zhiyuan College at Shanghai Jiao Tong University in 2016. He has broad interests in randomized algorithms, discrete probability, and machine learning. Currently, he works on Markov chain Monte Carlo (MCMC) methods for sampling from Gibbs distributions, and machine learning problems related to graphical models.
Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation
Jiaheng Zhang, UC Berkeley
Abstract
We present Libra, the first zero-knowledge proof system that has both optimal prover time and succinct proof size/verification time. In particular, if C is the size of the circuit being proved (i) the prover time is O(C) irrespective of the circuit type; (ii) the proof size and verification time are both O(d log C) for d-depth log-space uniform circuits (such as RAM programs). In addition Libra features an one-time trusted setup that depends only on the size of the input to the circuit and not on the circuit logic. Underlying Libra is a new linear-time algorithm for the prover of the interactive proof protocol by Goldwasser, Kalai and Rothblum (also known as GKR protocol), as well as an efficient approach to turn the GKR protocol to zero-knowledge using small masking polynomials. Not only does Libra have excellent asymptotics, but it is also efficient in practice. For example, our implementation shows that it takes 200 seconds to generate a proof for constructing a SHA2-based Merkle tree root on 256 leaves, outperforming all existing zero-knowledge proof systems. Proof size and verification time of Libra are also competitive.
Biography
Jiaheng Zhang is a third-year Ph.D. candidate in Computer Science at UC Berkeley, advised by Prof. Dawn Song. He is a member of RISE Lab, Initiative for Cryptocurrencies & Contracts Lab (IC3) and Berkeley AI Research (BAIR). His research interests lie in computer security and cryptography, especially zero-knowledge proofs and their applications on blockchain and machine learning models. Prior to coming to Berkeley, he received his Bachelor's degree in ACM Honors Class of Shanghai Jiao Tong University, under the supervision of Prof. Xiaotie Deng. During his undergraduate, his was also a research intern at Cornell, working with Prof. Elaine Shi. He received the Facebook Fellowship in 2021.
Proving Expected Sensitivity of Probabilistic Programs with Randomized Variable-Dependent Termination Time
Peixin Wang, University of Oxford
Abstract
Probabilistic programs are shown to be powerful models for a wide variety of real-world applications, such as analysis of stochastic network protocols, machine learning applications, cryptographic protocols, cyber-physical systems, etc. Recently, formal analysis of probabilistic programs has received a lot of attention in different research areas, e.g., probability theory and statistics, formal methods, artificial intelligence, and programming languages.
In this talk, I will introduce our previous work of proving expected sensitivity of probabilistic programs. The notion of program sensitivity (a.k.a. Lipschitz continuity) specifies that changes in the program input result in proportional changes to the program output. The motivation of this work arises from the fact that sensitivity properties are non-trivial to stability or robustness analysis of stochastic systems. Previous work mainly focuses on loops whose number of iterations is fixed and bounded, which seems restrictive in real-world applications. In our work, we present an automated martingale-based approach that can handle probabilistic while loops whose number of iterations is not fixed, but randomized and depends on the initial input values. Furthermore, our approach is compositional for sequential composition of while loops under a mild side condition.
Biography
Peixin Wang is now a research associate in the Department of Computer Science at the University of Oxford where he works with Professor Luke Ong. Before that, he obtained his Ph.D. degree at Shanghai Jiao Tong University and was supervised by Professor Yuxi Fu and Dr. Hongfei Fu. Currently, Peixin Wang's research interest includes but not limits to program verification, Bayesian inference, and probabilistic programming.
Maximin Fairness with Mixed Divisible and Indivisible Goods
Xinhang Lu, Nanyang Technological University
Abstract
We study fair resource allocation when the resources contain a mixture of divisible and indivisible goods, focusing on the well-studied fairness notion of maximin share (MMS) fairness. With only indivisible goods, an MMS allocation may not exist, but a constant multiplicative approximate allocation always does. We analyze how the MMS approximation guarantee would be affected when the resources to be allocated also contain divisible goods. In particular, we show that the worst-case MMS approximation guarantee with mixed goods is no worse than that with only indivisible goods. However, there exist problem instances to which adding some divisible resources would strictly decrease the MMS approximation ratios of the instances. On the algorithmic front, we propose a constructive algorithm that will always produce an -MMS allocation for any number of agents, where takes values between 1/2 and 1 and is a monotonically increasing function determined by how agents value the divisible goods relative to their maximin share.
Joint work with Xiaohui Bei, Shengxin Liu, and Hongao Wang.
Biography
Xinhang Lu is a PhD student in Mathematical Sciences under the supervision of Prof. Xiaohui Bei in the School of Physical and Mathematical Sciences at Nanyang Technological University. Prior to this, she graduated with a BEng in Computer Science and Technology from Southeast University. She is broadly interested in problems at the interface between computer science and economics. Recently, her work has focused on resource allocation.
Almost Tight Approximation Hardness for k-DST
Chao Liao, Shanghai Jiao Tong Univerisity
Abstract
In the k-edge-connected directed Steiner tree problem (k-DST), we are given an n-vertex directed graph G=(V, E) with edge-costs, a connectivity requirement k, a root r in V, and a set of terminals T of vertices. The goal is to find a minimum-cost subgraph H that has k internally disjoint paths from the root vertex r to every terminal t.
The problem is NP-hard, and inapproximability results are known in several parameters, e.g., on hardness in terms n, in terms of k, and in terms of |T|. In this talk, we show that for sufficiently large k, a trivial |T|-approximation algorithm is tight up to the lower order term. In particular, we show an approximation hardness of Ω(|T| / log |T|) for the problem, which holds under a standard assumption NP ≠ ZPP, and it can be tightened up to Ω(|T|) under the Strongish Planted Clique Hypothesis. This closes the long-standing open problem. It also rules out polylogarithmic approximation algorithms for those that runs in quasi-polynomial-time, thus separating the general case of k-DST from the case k=1,2, as the latter admits polylog(|T|)-approximation quasi-polynomial-time algorithms.
In addition, we show that unless NP=ZPP there exists no Ω((k/L)^(L/4))-approximation algorithm for k-DST on L-layered graphs for L ≤ O(log n), which admits an O(k^L * L * log |T|)-approximation algorithm that runs in O(n^L)-time due to Laekhanukit [ICALP '16]. As a corollary, it rules out Ω(2^(k/2) / log k)-approximation algorithms for k-DST, which is the first hardness result exponential in k for k-DST and any problem in the class of k-connectivity problems.
Biography
Chao Liao is a PhD candidate at Shanghai Jiao Tong University since 2016, advised by Prof. Yong Yu and Prof. Pinyan Lu. He is going to join the TCS Laboratory of Huawei. Prior to that, he received a bachelor's degree in Computer Science and Technology from the ACM Class in Zhiyuan College at Shanghai Jiao Tong University.
关于IJTCS
回顾 → 对话邓小铁：在首届IJTCS中，我看到了中国计算理论的成长
日程 → 分论坛：区块链技术
日程 → 分论坛：多智能体强化学习
日程 → 分论坛：量子计算
日程 → 分论坛：算法与复杂性
日程 → 分论坛：人工智能与形式化方法
日程 → 分论坛：机器学习理论
日程 → 特 色：有意识的图灵机
日程 → 特 色：本科生论坛
IJTCS注册信息
大会现已正式面向公众开放注册！
观看线上报告：免费
通过在线观看直播的方式参与大会，可通过直播平台提问。
线上会议注册：
（普通）$100 /￥700
（学生）$50 /￥350*
获得所有Zoom会议参会链接，作为参会人在线参加全部会议，直接在线提问讨论并参与特设互动环节。
线下会议注册：
（普通）$200 / ￥1400
（学生）$100 / ￥700*
作为参会人在线下（北京大学）参加会议，与知名学者们面对面交流；同时享受线上注册的所有权益。
*因防疫要求，仅开放10个校外线下参会名额。
点击 ↓↓↓二维码↓↓↓ 跳转注册页面
*学生注册：网站上注册后需将学生证含有个人信息和学校信息的页拍照发送至IJTCS@pku.edu.cn，邮件主题格式为＂Student Registration+姓名+线上/线下"。
大会主席
John Hopcroft
图灵奖获得者
中国科学院外籍院士
北京大学访问讲席教授
大会联合主席
邓小铁
北京大学讲席教授
欧洲科学院外籍院士
ACM/IEEE Fellow
顾问委员会主席
高 文
中国工程院院士
北京大学教授
梅 宏
中国科学院院士
CCF理事长
张平文
中国科学院院士
CSIAM理事长
北京大学教授
程序委员会主席
孙晓明
中科院计算所
研究员
邓小铁
北京大学
讲席教授
李闽溟
香港城市大学
副教授
陆品燕
上海财经大学
教授
李 建
清华大学
副教授
组织单位
合作媒体
大会赞助
联系人
大会赞助、合作等事宜
请联系
IJTCS@pku.edu.cn
010-62761029
大会网站
https://econcs.pku.edu.cn/ijtcs2021/index.htm
↑↑扫码直达大会官网↑↑
文字 | 郑炜强
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。
点“阅读原文”转大会注册页面