IJTCS | 特别推荐：本科生科研论坛

编者按

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

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

本期带来“本科生科研论坛”精彩介绍。

“本科生科研论坛”介绍

本科生一直是科研中的特殊群体：他们有较重的课业压力，参与科研往往处于起步阶段，然而依旧有许多优秀的学生在本科期间就做出了极好的学术成果。本次大会的本科生科研论坛邀请了国内理论计算机研究方向最杰出的一批本科生，报告的内容包括多篇发表在理论计算机领域顶级会议上的文章（包括2020年STOC的最佳论文），涵盖了复杂性理论、算法博弈论、区块链和机器学习理论等方向，证明本科生也可以在理论计算机方向做出卓越贡献，也鼓励更多的优秀本科生参与理论计算机方向的科研工作。

“本科生科研论坛”主席

孔雨晴

北京大学

陈宏崟

北京大学

“本科生科研论坛”议程

时间：2020年8月17、18、21日

“本科生科研论坛”报告简介

 

金  策

Sharp Threshold Results for Computational Complexity

Abstract

We establish several "sharp threshold" results for computational complexity. For certain tasks, we can prove a resource lower bound of n^c for c>=1 (or obtain an efficient circuit-analysis algorithm for n^c size), there is strong intuition that a similar result can be proved for larger functions of n, yet we can also prove that replacing "n^c" with "n^{c+eps}" in our results, for any eps>0, would imply a breakthrough n^{omega(1)} lower bound. Appeared in STOC 2020. Joint work with Lijie Chen and Ryan Williams from MIT.

 

周子寒

Towards Large Scale Multi-agent Reinforcement Learning

Abstract

There has been many successful algorithms in the field of multi-agent reinforcement learning (MARL). However, most of them focus on limited scale environments with no more than a dozen agents. In fact, their performence can drop siginificantly with the number of agents goes up. This incapability of scailing makes these algorithms infeasible for many real-life scenarios as they often involve dozens if not hundreds of agents. In this talk, I am going to present a novel learning paradigm that builds on existing MARL algorithms, which in a way extending them to solve for large scale MARL problems. I'll first introduce the main obstacles of large scale MARL, then talk about how we solve them in our work: Evolutionary Population Curriculum for Scaling Multi-Agent Reinforcement Learning.

 

资  威

Cake Cutting on Graphs: A Discrete and Bounded Proportional Protocol

Abstract

The classical cake cutting problem studies how to find fair allocations of a heterogeneous and divisible resource among multiple agents. Two of the most commonly studied fairness concepts in cake cutting are proportionality and envy-freeness. It is well known that a proportional allocation among n agents can be found efficiently via simple protocols. For envy-freeness, in a recent breakthrough, Aziz and Mackenzie proposed a discrete and bounded envy-free protocol for any number of players. However, the protocol suffers from high multiple-exponential query complexity and it remains open to find simpler and more efficient envy-free protocols.

In this paper we consider a variation of the cake cutting problem by assuming an underlying graph over the agents whose edges describe their acquaintance relationships, and agents evaluate their shares relatively to those of their neighbors. An allocation is called locally proportional if each agent thinks she receives at least the average value over her neighbors. Local proportionality generalizes proportionality and is in an interesting middle ground between proportionality and envy-freeness: its existence is guaranteed by that of an envy-free allocation, but no simple protocol is known to produce such a locally proportional allocation for general graphs. Previous works showed locally proportional protocols for special classes of graphs, and it is left as an open question to design simple locally proportional protocols for more general classes of graphs. In this paper we completely resolved this open question by presenting a discrete and bounded locally proportional protocol for any given graphs. Our protocol has a query complexity of only single exponential, which is significantly smaller than the six towers of n query complexity of the envy-free protocol given in Aziz and Mackenzie's work in FOCS 2016.

 

姜志豪

Stability in Committee Selection

Abstract

We talk about fairness in the committee selection problem. We consider a general notion of fairness via stability: A committee is stable if no coalition of voters can deviate and choose a committee of proportional size, so that all these voters strictly prefer the new committee to the existing one. We extend this definition to stability of a distribution (or lottery) over committees. We show that stable lotteries always exist for two canonical voter preference models: the Approval Set setting and the Ranking setting. We also show that a c-approximately stable committee always exists where c is O(1), only assuming preferences are monotone: if committee S is a subset of committee S', then any voter weakly prefers S' to S. This talk is a summary of my work appeared in EC 2019 and STOC 2020.

 

吴克文

Improved Bounds for the Sunflower Lemma

Abstract

A sunflower with r petals is a collection of r sets so that the intersection of each pair is equal to the intersection of all of them. Erdös and Rado proved the sunflower lemma: for any fixed r, any family of sets of size w, with at least about w^w sets, must contain a sunflower. The famous sunflower conjecture is that the bound on the number of sets can be improved to c^w for some constant c. In this paper, we improve the bound to about (log w)^w. In fact, we prove the result for a robust notion of sunflowers, for which the bound we obtain is sharp up to lower order terms. STOC 2020 Best Paper.

 

林  涛

Private Data Manipulation in Sponsored Search Auctions

Abstract

In repeated sponsored search auctions where the seller tries to learn buyers' private value distributions from history, buyers may benefit from misreporting their distributions by bidding strategically. We model such a game between the seller and the buyers by a Private Data Manipulation (PDM) game: the seller first announces an auction whose allocation and payment rules are based on the value distributions submitted by buyers; then buyers submit distributions. The outcome of the PDM game thus depends on the design of the auction and the game played among buyers in their choices of distributions. Under the PDM game, we re-evaluate the theory, methodology, and techniques in the sponsored search auctions that have been intensively studied in Internet economics. We show that Myerson's auction and the generalized first-price auction are equivalent in general and in the symmetric case they are further equivalent to the generalized second-price auction and the VCG auction. Appeared in WWW 2020.

 

李毓浩

Recent Development for the Incentive Ratio in BitTorrent Resource Sharing Networks

Abstract

The booming sharing economy has a common challenge in motivating agents, by truthful actions, to follow the economic design of the market maker. For the well known BitTorrent network, there has been an array of theoretical research in the study of the truthfulness of the proportional response protocol formulated to model its tit-for-tat strategy. Some works confirm the truthfulness for deviations against weight cheating and edge deleting. But others reveal it not truthful against Sybil attack where an agent may split its resource among its different copies. Though truthfulness cannot be guaranteed, the incentives are shown to generate a limited gain for agents pursuing the Sybil attack in several special networks, such as trees, cliques, and cycles. The concept of incentive ratio is used to characterize the utility gain from a Sybil attack and some tight results have been proved on trees and cliques.

For the resource sharing on cycles, previous works proved the incentive ratio is lower bounded by two and upper bounded by four, and later the upper bound is improved to three. It has been listed in \cite{CCQY} and \cite{CZ} as an open problem to tighten them. In this work, we completely resolve this open problem, furthermore, we establish the first such results for general networks, proving a $\theta(1)$ incentive ratio for any agent playing such an attack. Appeared in AAMAS2020 and IPDPS2020.

 

蔡天乐

Towards Understanding Optimization of Deep Learning

Abstract

Optimization is one of the central problems of deep learning. However, since the optimization of deep neural networks is a highly non-convex problem, there is only a limited understanding of the empirical success of some simple algorithms, e.g., gradient descent, for deep learning optimization. Without deeper understanding, we cannot develop principled new algorithms, either.

Basing on the recent theoretical framework of the neural tangent kernel, we take a first step towards understanding the optimization of deep learning by investigating sufficiently wide neural networks. We give the first convergence guarantee of a typical min-max optimization problem, i.e., adversarial training, and provide evidence of the benefit of using wide neural networks for adversarial training. Then we go back to the classic deep learning optimization problem of training a neural network and ask whether we can design an algorithm that both enjoys a better convergence rate than previous works and has great practical potential. We give a positive answer by proposing a Gram-Gauss-Newton method that provably enjoys second-order convergence rate on wide neural networks and practically has little overhead compared to classic first-order methods such as stochastic gradient descent. Appeared in NeurIPS.

 

周铭洵

Attack Discovery on Blockchain Incentive Mechanisms with Reinforcement Learning

Abstract

Incentive mechanisms are fundamental components of blockchain systems: they incentivize participants to secure the underlying consensus protocol. However, designing incentive-compatible mechanisms is notoriously challenging. Many exsiting blockchain protocols provide strong theoretical security guarantees for the traditional setting, where participants are honest either Byzantine, but they leave out the analysis of rational users who may exploit incentive to deviate from honest behavior. We propose SquirRL, a framework for using reinforcement learning to identify attack strategies on blockchain incentive mechanisms. With minimal setup, SquirRL replicates known theoretical results on the Bitcoin protocol. We also apply SquirRL to some other prominent blockchain protocols and SquirRL identifies attack strategies superior to those known in the literature. Finally, utilizing multi-agent reinforcement learning technique, SquirRL yields results suggesting that classical selfish mining attacks against Bitcoin lose effectiveness in the presence of multiple attackers. These results shed light on why selfish mining, which is unobserved to date in the wild, may be a poor attack strategy.

关于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]

—   版权声明  —

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

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