IJTCS 2021 | 分论坛日程：本科生论坛
编者按
第二届国际理论计算机联合大会（International Joint Conference on Theoretical Computer Science，IJTCS）将于2021年8月16日-20日在线上线下交互举行，由北京大学与中国工业与应用数学学会（CSIAM）、中国计算机学会（CCF）、国际计算机学会中国委员会（ACM China Council）联合主办，北京大学前沿计算研究中心承办，图灵奖获得者、中科院外籍院士、北京大学访问讲席教授John Hopcroft教授任大会主席。
本期带来“本科生论坛”的精彩介绍。
“本科生论坛”介绍
本科生是科研中的特殊群体：他们有较重的课业压力，往往处于科研的起步阶段。然而，我们欣喜地看到：依然有许多优秀的学生在本科期间就做出了很多的学术成果。IJTCS 2021 的本科生科研论坛邀请了国内理论计算机研究方向最杰出的一批本科生，报告的内容包括多篇发表在理论计算机领域顶级会议上的文章（包括 AAAI、NeurIPS、ICML、STOC、SODA、IJCAI等），涵盖了机器学习理论、复杂性理论和算法博弈论等方向。他们向我们证明了，本科生也可以在理论计算机方向做出卓越贡献；他们的优异表现也可以鼓励更多的本科生参与理论计算机方向的科研工作。
“本科生论坛”主席
Zhaohua Chen
Peking University
“本科生论坛”议程
时间：2021年8月18日
时间 | 讲者 | 报告题目 |
13:30- | 郑炜强 | The Smoothed Complexity of Computing Kemeny and Slater Rankings |
14:00- | 周子鑫 | Explainable Voting |
15:00- | 于宸锴 | Timely Information from Prediction Markets |
15:30- | 吴瑾昭 | Random Order Vertex Arrival Contention Resolution Schemes For Matching, With Applications |
16:00- | 黄致焕 | Maximizing Surprise with a Bonus |
16:30- | 杨家齐 | Recent Progress on Bandits and RL with Nonlinear Function Approximation |
17:00- | 吕 欣 | Inverse-Exponential Correlation Bounds and Extremely Rigid Matrices from a New Derandomized XOR Lemma |
17:30- | 任瀚林 | Faster algorithms for distance sensitivity oracles |
“本科生论坛”报告简介
The Smoothed Complexity of Computing Kemeny and Slater Rankings
Weiqiang Zheng, Peking University
Abstract
The computational complexity of winner determination under common voting rules is a classical and fundamental topic in the field of computational social choice.
Previous work has established the NP-hardness of winner determination under some commonly-studied voting rules, such as the Kemeny rule and the Slater rule. In a recent position paper, Baumeister et al questioned the relevance of the worst-case nature of NP-hardness in social choice and proposed to conduct smoothed complexity analysis, which successfully explains why the simplex method usually runs fast by Spielman and Teng.
In this paper, we develop the first smoothed complexity results for winner determination in voting. We prove the smoothed hardness of Kemeny and Slater using the classical smoothed runtime analysis, and prove a parameterized typical-case smoothed easiness result for Kemeny. Overall, our results show that smoothed complexity analysis in computational social choice is a challenging and fruitful topic.
This is a joint work wtih Lirong Xia.
Biography
Weiqiang Zheng is an undergraduate student at Turing class, Peking University, and is going to pursue his Ph.D. in Yale University. His research interests are in economics and computation, especially mechanism design and computational social choice.
Explainable Voting
Zixin Zhou, Peking University
Abstract
The design of voting rules is traditionally guided by desirable axioms. Recent work shows that, surprisingly, the axiomatic approach can also support the generation of explanations for voting outcomes. However, no bounds on the size of these explanations is given; for all we know, they may be unbearably tedious. We prove, however, that outcomes of the important Borda rule can be explained using O(m) steps, where m is the number of alternatives. Our main technical result is a general lower bound that, in particular, implies that the foregoing bound is asymptotically tight. We discuss the significance of our results for AI and machine learning, including their potential to bolster an emerging paradigm of automated decision making called virtual democracy.
Biography
Zixin (Jack) Zhou is an incoming CS PhD at Stanford University, and he recently got Bachelor's degree from Peking University. He has a broad interest in theoretical computer science especially in algorithmic game theory and complexity theory.
Timely Information from Prediction Markets
Chenkai Yu, Tsinghua University
Abstract
Prediction markets are powerful tools to elicit and aggregate beliefs from strategic agents. However, in current prediction markets, agents may exhaust the social welfare by competing to be the first to update the market. We initiate the study of the trade-off between how quickly information is aggregated by the market, and how much this information costs. We design markets to aggregate timely information from strategic agents to maximize social welfare. To this end, the market must incentivize agents to invest the correct amount of effort to acquire information: quickly enough to be useful, but not faster (and more expensively) than necessary. The market also must ensure that agents report their information truthfully and on time. We consider two settings: in the first, information is only valuable before a deadline; in the second, the value of information decreases as time passes. We use both theorems and simulations to demonstrate the mechanisms.
Appeared in AAMAS 2021.
Biography
Chenkai Yu is a fourth-year undergraduate student at Institute for Interdisciplinary Information Sciences (IIIS), Tsinghua University. He was a visiting student at Caltech where he was advised by Adam Wierman and at University of Michigan where he was advised by Grant Schoenebeck. His research interest is mainly in the intersection of computer science and economics.
Random Order Vertex Arrival Contention Resolution Schemes For Matching, With Applications
Jinzhao Wu, Peking University
Abstract
With a wide range of applications, stochastic matching problems have been studied in different models, including prophet inequality, Query-Commit, and Price-of-Information. While there have been recent breakthroughs in all these settings for bipartite graphs, few non-trivial results are known for general graphs. Motivated by this, we study the random order vertex arrival contention resolution scheme for matching in general graphs. We design an 8/15-selectable batched RCRS for matching and apply it to achieve 8/15-competitive/approximate algorithms for all the three models. Our results are the first non-trivial results for random order prophet matching and Price-of-Information matching in general graphs. For the Query-Commit model, our result substantially improves upon the 0.501 approximation ratio.
This work was jointly done with Hu Fu, Zhihao Tang, Hongxun Wu and Qianfan Zhang.
Biography
Jinzhao Wu is a third-year undergraduate in Turing Class, Peking University. He is broadly interested in theoretical computer science and algorithmic game theory. He is visiting SUFE under the supervision of Zhihao Tang.
Maximizing Surprise with a Bonus
Zhihuan Huang, Peking University
Abstract
Multi-round games usually double or triple the points awarded in the final round, calling it a bonus, to maximize spectators' excitement. in contrast, the quidditch matches in the Harry Potter books, are typically dull as the main game play is almost entirely overshaddowed by the competition to find the golden snitch which is worth 15 times a normal goal.
In a two-player competition with rounds, we aim to derive the optimal bonus size to maximize the audience's overall expected surprise. We model audience's prior belief over the two players' ability level as a beta distribution. Using a novel analysis which clarifies and simplifies the computation, we find that the optimal bonus highly depends on the prior belief.
Biography
Zhihuan Huang is a Ph.D. freshman at Peking University, advised by Professor Yuqing Kong. He graduated from the Turing Class of Peking University before studying for Ph.D. ,majoring in Computer Science and Technology. His research interests lie in the game theory, mechanism design and EconCS. His recent research topic is how to design better rules so that players and audiences can obtain more surprise from the game. He also has researched on the CFR algorithm for calculating approximate Nash equilibrium. Besides, he also likes to participate in algorithm competitions and has won the ICPC regional competitions in Nanning and Macau.
Recent Progress on Bandits and RL with Nonlinear Function Approximation
Jiaqi Yang, Tsinghua University
Abstract
Classical theories on bandits and RL usually focused on the case where reward and transition are discrete or approximated by near-linear functions. However, these results might be far away from practice, where nonlinear function approximation are used.
In this talk, I will discuss about our recent research on nonlinear function approximation in bandits and RL, with a particular focus on low-rank generalized linear functions and neural nets with polynomial activationn. For the low-rank generalized linear bandits, we came up with a novel minimax-optimal algorithm. For the polynomial bandits, we gave an algorithm with sample complexity only depends on the intrinsic algebraic dimension of the function class. For both cases, we showed that standard optimism-based algorithms are sub-optimal. We also studied under what assumptions could we extend the results to RL. This talk is based on joint work with Baihe Huang, Kaixuan Huang, Sham M. Kakade, Jason D. Lee, Qi Lei, and Runzhe Wang.
Biography
Jiaqi Yang is an incoming PhD student in Computer Science in the Department of Electrical Engineering and Computer Sciences at the University of California, Berkeley. Previously, he received his B.E. in Computer Science and Technology (Yao Class) from the Institute for Interdisciplinary Information Sciences, Tsinghua University. His research interests are broadly in statistical machine learning.
Inverse-Exponential Correlation Bounds and Extremely Rigid Matrices from a New Derandomized XOR Lemma
Xin Lyu, Tsinghua University
Abstract
In this work we prove that there is a function such that, for every sufficiently large n and , (f restricted to -bit inputs) cannot be ( )-approximated by -polynomials of degree . We also observe that a minor improvement (e.g., improving to for any ) over our result would imply cannot be computed by depth-3 -circuits of size, which is a notoriously hard open question in complexity theory. Using the same proof techniques, we are also able to construct extremely rigid matrices over in .
The key ingredient in the proof of our new results is a new derandomized XOR lemma based on approximate linear sums, which roughly says that given an -input function which cannot be 0.99-approximated by certain linear sum of many functions in a class C within -distance, one can construct a new function with input bits, which cannot be ( )-approximated by C-functions. Taking C to be a function collection containing low-degree -polynomials or low-rank -matrices, our results are then obtained by first using the algorithmic method to construct a function which is weakly hard against linear sums of C in the above sense, and then applying the derandomized XOR lemma to .
We obtain our new derandomized XOR lemma by giving a generalization of the famous hardcore lemma by Impagliazzo. Our generalization in some sense constructs a non-Boolean hardcore of a weakly hard function with respect to C-functions, from the weak inapproximability of by any linear sum of C with bounded -norm. This generalization recovers the original hardcore lemma by considering the -norm. Surprisingly, when we switch to the -norm, we immediately rediscover Levin's proof of Yao's XOR Lemma. That is, these first two proofs of Yao's XOR Lemma can be unified with our new perspective. For proving the correlation bounds, our new derandomized XOR lemma indeed works with the -norm.
This is a joint work with Lijie Chen from MIT.
Biography
Xin Lyu is a senior undergraduate at IIIS, Tsinghua University. His research interests lie in theoretical computer science, with a particular focus on computational complexity, theory, and Boolean function analysis.
Faster algorithms for distance sensitivity oracles
Hanlin Ren, Tsinghua University
Abstract
We study distance sensitivity oracles (DSOs). Given a directed graph G = (V, E) with n vertices and edge weights in {1, 2, ..., M}, we want to build a data structure such that given any source vertex u, any target vertex v, and any failure f (which is either a vertex or an edge), it outputs the length of the shortest path from u to v not going through f. In this talk, we show how to build a DSO using fast matrix multiplication; in particular, our DSO has preprocessing time and query time O(1).
Our DSO uses the following techniques: (1) a bootstrapping argument that decreases the query time of any DSO to constant (Bernstein-Karger, STOC'09); (2) bridging sets (or hitting sets) (Zwick, JACM'02; Ren, ESA'20); (3) an algorithm for inverting a polynomial matrix modulo (Gu-Ren, ICALP'21), and how it relates to distances in graphs (Sankowski, ESA'05; Brand-Saranurak, FOCS'19).
Based on joint work with Yong Gu.
Biography
Hanlin Ren is becoming a PhD student at University of Oxford this September, under the supervision of Prof. Rahul Santhanam. He is interested in computational complexity, and in particular circuit complexity, meta-complexity, and average-case complexity. Prior to that, he received his bachelor degree in IIIS, Tsinghua University, during which he worked on graph algorithms under the supervision of Prof. Ran Duan.
关于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
↑↑扫码直达大会官网↑↑
文字 | 李佳蔚
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。
点“阅读原文”转大会注册页面