IJTCS | 特别推荐：青年博士论坛

编者按

首届国际理论计算机联合大会（International Joint Conference on Theoretical Computer Science，IJTCS）将于2020年8月17日-21日在线上举行，由北京大学与中国工业与应用数学学会（CSIAM）、中国计算机学会（CCF）、国际计算机学会中国委员会（ACM China Council）联合主办，北京大学前沿计算研究中心承办。  

本次大会的主题为“理论计算机科学领域的最新进展与焦点问题”。大会共设7个分论坛，分别对算法博弈论、区块链技术、多智能体强化学习、机器学习理论、量子计算、机器学习与形式化方法和算法与复杂性等领域进行深入探讨。同时，大会特别开设了青年博士论坛、女性学者论坛与本科生科研论坛，荟集海内外知名专家学者，聚焦理论计算机前沿问题。有关信息将持续更新，敬请关注！

本期带来“青年博士论坛”精彩介绍。

“青年博士论坛”介绍

设立青年博士论坛的其中一个目标是给理论计算机及其相关领域优秀的青年学者们一个交流的平台，让青年学者们有一个集中的机会了解到理论计算机及其相关的不同方向上大家正在攻坚的科学难题，还能产生一些可能的合作。另一个目标是起到一个榜样作用，给刚进入或还未进入理论计算机及其相关领域的学生们树立一个好榜样，鼓励同学们向这些优秀的青年学者学习，努力奋斗，争取在不久的未来，因为自己的学术成果，被邀请作为青年博士论坛的报告人回来参与活动。

“青年博士论坛”主席

肖  涛

华为计算理论实验室

“青年博士论坛”议程

“青年博士论坛”报告简介

 

王若松

Reinforcement Learning with Function Approximation: Provably Efficient Algorithms and Hardness Results

Abstract

Modern reinforcement learning problems are often challenging due to the huge state space. To tackle this challenge, function approximation schemes are often employed to provide a compact representation. In this talk, I will present provably efficient algorithms and hardness results for reinforcement learning with function approximation. In the first part of this talk, I will present exponential lower bounds for value-based and policy-based learning with function approximation. These results emphasize that more structural assumptions are necessary to enable efficient reinforcement learning. In the second part of this talk, I will present an algorithm with polynomial regret bound when the value functions admit an approximation with a function class with bounded eluder dimension. Our algorithm generalizes recent progress on RL with linear value function approximation and does not make explicit assumptions on the model of the environment. Moreover, our algorithm is model-free and provides a framework to justify the effectiveness of algorithms used in practice.

 

李志远

Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets?

Abstract

Convolutional neural networks often dominate fully-connected counterparts in generalization performance, especially on image classification tasks. This is often explained in terms of "better inductive bias." However, this has not been made mathematically rigorous, and the hurdle is that the fully connected net can always simulate the convolutional net (for a fixed task). Thus the training algorithm plays a role. The current work describes a natural task on which a provable sample complexity gap can be shown, for standard training algorithms. We construct a single natural distribution on R^d×{±1} on which any permutation-invariant algorithm (i.e. fully-connected networks trained with most gradient based methods from i.i.d. initialization) requires Ω(d)samples to generalize while O(1) samples suffices for convolutional architectures. Furthermore, we demonstrate a class of tasks with an O(1) vs Ω(d^2) gap. The proof idea is to take into account the symmetry by the algorithm on learnt networks.

 

凤维明

Fast Sampling and Counting K-SAT Solutions in the Local Lemma Regime

Abstract

We give new algorithms based on Markov chains to sample and approximately count satisfying assignments to k-uniform CNF formulas where each variable appears at most d times. For any k and d satisfying kd < n^o(1) and k ≥ 20 log k + 20 log d + 60, the new sampling algorithm runs in close to linear time, and the counting algorithm runs in close to quadratic time. Our approach is inspired by Moitra (JACM, 2019) which remarkably utilizes the Lovász local lemma in approximate counting. Our main technical contribution is to use the local lemma to bypass the connectivity barrier in traditional Markov chain approaches, which makes the well developed MCMC method applicable on disconnected state spaces such as SAT solutions. The benefit of our approach is to avoid the enumeration of local structures and obtain fixed polynomial running times, even if k=ω(1) or d=ω(1). Joint work with Heng Guo (University of Edinburgh), Yitong Yin (Nanjing University) and Chihao Zhang (Shanghai Jiao Tong University).

 

何  昆

Lovasz Local Lemma: Variable and Quantum

Abstract

Lovasz local lemma (LLL) is a very powerful tool in combinatorics and probability theory to show the possibility of avoiding all "bad" events under some "weakly dependent" condition. Over the last decades, the algorithmic aspect of LLL, especially under the variable setting, has also attracted lots of attention in theoretical computer science. A tight criterion under which the abstract version LLL holds was given by Shearer. Recently, Ambainis et al. introduced a quantum version LLL (QLLL), which was then shown to be powerful for the quantum satisfiability problem.

In this talk, we prove that the tight bound of variable version LLL (VLLL) goes beyond Shearer's bound. We also prove that Shearer's bound is tight for QLLL, affirming a conjecture proposed by Sattath et al. For the commuting version LLL (CLLL), the LLL between the variable version and quantum version, we prove that the tight regions of CLLL and QLLL are different in general.

 

黄棱潇

Coreset Construction for Clustering

Abstract

Clustering is an essential tool in data analysis and is used in many application domains. Given a collection of points in a metric space, the goal of the (k,z)-clustering problem is to find a subset of k "centers" that minimizes the sum of the z-th powers of the distance of each point to the closest center. An arising problem of clustering algorithms is the large cost of storage space and computational time for massive datasets. One approach to the problem is called coreset, which is a small subset of the data allowing for fast approximate inference. In this talk, I will present recent progress on coreset construction for clustering in several metric spaces, including Euclidean metrics, doubling metrics and graph metrics.

 

张驰豪

Rapid Mixing from Spectral Independence beyond the Boolean Domain

Abstract

In this talk, I will talk about our recent extension of the notion of spectral independence (introduced by Anari, Liu, and Oveis Gharan) from the Boolean domain to general discrete domains. This property characterises distributions with limited correlations, and implies that the corresponding Glauber dynamics is rapidly mixing.

As a concrete application, we show that Glauber dynamics for sampling proper q-colourings mixes in polynomial-time for the family of triangle-free graphs with maximum degree Δ provided q≥(α+δ)Δ where α≈1.763 is the unique solution to α=exp(1/α) and δ>0 is any constant. This is the first efficient algorithm for sampling proper q-colourings in this regime with possibly unbounded Δ. Our main tool of establishing spectral independence is the recursive coupling by Goldberg, Martin, and Paterson. Joint work with Weiming Feng, Heng Guo and Yitong Yin.

 

刘明谋

Lower Bound for Succinct Range Minimum Query

Abstract

The Range Minimum Query problem (RMQ) is a classical data structure problem in computer science. Given an integer array A[1..n], the RMQ asks to preprocess A into a data structure, supporting RMQ queries: given a,b∈[1,n], return the index i∈[a,b] that minimizes A[i]. The best known data structure uses 2n+n/(log n/ t)^t bits and answers queries in O(t) time, assuming the word-size is w=Θ(log n). In this work, we prove the first lower bound for RMQ. Our lower bound shows that the state-of-the-art data structure is optimal in the regime of constant time. In general, we show that if the data structure has query time O(t), then it must use at least 2n+n/(log n)^{Õ(t^2)} bits, in the cell-probe model with word-size w=Θ(log n).

 

李  博

Fair Resource Sharing and Dorm Assignment

Abstract

In this work, we study the fair resource sharing problem, where a set of resources needs to be shared by a set of agents. Each agent is unit-demand and each resource can serve up to a limited number of agents. The agents have (heterogeneous) preferences for the resources, and preferences for other agents with whom they share the resources. Our definition of fairness is mainly captured by envy-freeness. Due to the fact that an envy-free assignment may not exist even in simple settings, we propose a way to relax the definition: Pareto envy-freeness, where an assignment is Pareto envy-free if for any two agents i and j, agent i does not envy agent j for her received resource or the set of agents she shares the resource with. We study to what extent Pareto envy-free assignments exist. Particularly, we are interested in a typical model, dorm assignment problem, where a number of students need to be accommodated to the dorms with the same capacity and the students' preferences for dorm-mates are binary. We show that when the capacities of the dorms are 2, a Pareto envy-free assignment always exists and can be found in polynomial time; however, if the capacities increase to 3, Pareto envy-freeness cannot be guaranteed any more.

 

阎  翔

Incentive Analysis on Peer-to-Peer Resource Sharing Networks

Abstract

We consider a sharing economy over a network where each vertex player contributes resource to its neighbors, in return for their shares. Each vertex's utility is the total shared resource with all its neighbors. General equilibrium theory applies here to solve this group decision problem of resource allocation and pricing. While it was known that a proportional response sharing protocol achieves the market equilibrium solution (unique to everyone's utility value), we are particularly interested in the mechanism design issue whether a player may manipulate its private information in order to gain more resource allocated in the market equilibrium solution. We provide mathematical proofs for the truthfulness against three types of manipulative strategies (feasible weight cheating, edge deleting, and false name strategies), and the tight bound for the incentive ratio of another manipulative strategy (Sybil attack). This work establishes the first robustness result for a practical distributed network resource sharing protocol. This is a crucial property to free Internet resource sharing protocols against an agent's manipulative strategies.

关于IJTCS

简介 → 国际理论计算机联合大会重磅登场

推荐 → 大会特邀报告（一）

推荐 → 大会特邀报告（二）

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

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

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

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

日程 → 分论坛：量子计算

日程 → 分论坛：机器学习与形式化方法

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

推荐 → 本科生科研论坛

IJTCS注册信息

本次大会已经正式面向公众开放注册！每位参与者可以选择免费注册以观看线上报告，或是支付一定费用以进一步和讲者就报告内容进行交流，深度参与大会的更多环节。

• 观看线上报告：免费

• 完全注册：
  

• （普通）$100 /￥700
  （学生）$50 /￥350*
  作为参会人参加全部会议，直接在线提问讨论并参与特设互动环节

注册截止：2020年8月15日23:59

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

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

大会主席

John Hopcroft

中国科学院外籍院士、北京大学访问讲席教授

林惠民

中国科学院院士、中国科学院软件研究所专家

大会联合主席

邓小铁

北京大学教授

顾问委员会主席

高  文

中国工程院院士、北京大学教授

梅  宏

中国科学院院士、CCF理事长

张平文

中国科学院院士、CSIAM理事长、北京大学教授

组织单位

媒体合作

欢迎注册

大会网站：

https://econcs.pku.edu.cn/ijtcs2020/IJTCS2020.html

注册链接：

https://econcs.pku.edu.cn/ijtcs2020/Registration.htm

联系人

大会赞助、合作等信息，请联系：[e-mail]

—   版权声明  —

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

点“阅读原文”转免费注册页面