我院ITCS陆品燕老师、 Nick Gravin老师三篇论文被SODA 2018接收!

2017-10-01   

640 (2)

国际算法顶级会议SODA 2018日前发榜,上海财经大学理论计算机科学中心(ITCS)共有三篇论文被接收。三篇论文及其作者分别是(按照理论计算机国际惯例,论文作者以字母排序,不代表贡献大小

1.Jin-Yi Cai, Pinyan Lu and Mingji Xia: Dichotomy for Real Holant^c Problems


2.Nick Gravin and Pinyan Lu: Separation in Correlation-Robust Monopolist Problem with Budget


3.Hu Fu, Chris Liaw, Pinyan Lu and Zhihao Gavin Tang: The Value of Information Concealment

作者中除了陆品燕(Pinyan Lu)和Nick Gravin 是ITCS的全职教师,蔡进一(Jin-Yi Cai)、夏盟佶(Mingji Xia)是ITCS的长期访问教授(每年至少访问一个月),唐志皓(Zhihao Gavin Tang)是中心的访问学生(香港大学的博士生,2017年3月到8月在中心访问了半年),伏虎(Hu Fu)是中心的短期访问教授。 这些论文是中心全职教授与中心访问教授、访问学生,短期访问教授密切学术合作取得的显著成果。除了这三篇,还有一篇SODA 2018论文是中心的长期访问学生与访问教授直接合作促成的,ITCS作为一个国际一流的理论计算机科学研究中心的群体态势已初步形成。

论文内容

ITCS研究领域既涵盖理论计算机的核心领域包括算法与复杂性等,也包括很多理论计算机与其他领域的交叉,比如经济学、人工智能、复杂网络、统计物理等。这次SODA 2018接收的三篇论文也很好的体现了中心研究的这些领域和特色,下面分别介绍一下:

Jin-Yi Cai, Pinyan Lu and Mingji Xia: Dichotomy for Real Holant^c Problems

理论计算机的核心是把问题根据计算的困难性分类,二分定理(Dichotomy)是把一个框架下能描述的所有问题分成了容易计算的和困难的,从而解决所有这类问题的复杂性。Holant框架是本文的三位作者在FOCS 2008的一篇论文中提出的一个比传统的约束可满足性(CSP)框架表达能力更强很多的框架,包含很多组合计数问题与统计物理的模型。之前的大多数Holant框架下的二分定理只是针对对称的约束函数,这篇论文推广到非对称的情况。对于这个问题,三位作者从2010年就开始做,7年多来中间也走了不少弯路,因为一开始的猜想就不完全准确,所以一直未证出来。最近新发现了一类有趣的容易计算的函数类,从而真正把拼图的所有碎片找全放对完全解决了这个问题。

Nick Gravin and Pinyan Lu: Separation in Correlation-Robust Monopolist Problem with Budget

斯坦福的经济学家 Gabriel Carroll 最近在经济学的顶级期刊《Econometrica》发表了一篇论文“Robustness and separation in multidimensional screening”。他认为买家对于不同物品的估值是完全独立的,这个假设在很多情况下是不符合实际的,但要完全确定不同物品之间相关性的联合分布往往也是很困难或者做不到的。 基于这个原因,他在论文中提出了一种新的衡量一个多物品拍卖机制的好坏的标准:基于最坏的相关性可能来衡量一个机制的好坏。 Gabriel在论文证明了一个很让人惊讶的结果,在这个新的标准下,最好的多物品拍卖机制就是把这些物品完全分开来卖。这个描述起来很简单的结论证明起来是很困难的,他的《Econometrica》论文有50页,其中主定理的数学证明部分就有15页。 在这个SODA论文中,作者用线性规划对偶性技巧给出了该问题的一个全新的数学刻画,并很大程度的简化了原证明。更重要的是,新的论文把Gabriel的结论推广到了买家带预算的情况,证明了一个更加令人惊讶的结果:即使买家有一个总的预算,最好的机制中卖家依然是把物品完全分开卖,并且可以认为预算也以一个事先确定的方式分配到了每个物品。 

Hu Fu, Chris Liaw, Pinyan Lu and Zhihao Gavin Tang: The Value of Information Concealment

本文考虑这样一个市场场景:卖家可以通过一些信号获得买家对一个物品的估值的局部信息。 论文证明,当卖家不把获得的信号公开的时候,他能获得的期望收益有可能比公开的情况多出任意多倍;但是如果不允许卖家在有些情况下给买家钱,而且估值和信号之间的联合分布满足某个正则性条件的话,两者的期望收益相差最多不超过三倍。 这个结论的一个重要的应用是单物品多人拍卖的场景。如果多个人对于该物品的估值是完全独立的,根据诺贝尔奖得主Myerson的最优拍卖理论,最优的DSIC拍卖机制和最优的BIC拍卖机制收益是完全一致的。但是当大家的估值不是独立的时候,卖家可以把其他人的报价看成对这个人估值的一个信号,适用上面的场景。论文分析得到,在估值不独立的时候,最优的BIC拍卖机制可能比最优的DSIC拍卖机制多出任意多倍的期望收益;但是如果不允许卖家在有些情况下给买家钱,而且不同买家估值的联合分布满足某个正则性条件的话,两者的期望收益相差最多不超过五倍。

关于SODA

SODA(ACM-SIAM Symposium of Discrete Algorithms)是算法方向顶级的国际会议,理论计算机科学三大会议(STOC/FOCS/SODA)之一,由ACM和SIAM两大国际学术组织联合主办。


算法是理论计算机科学最核心的方向,同时也是包括人工智能在内的所有计算机应用最根本的基础。 中国学者在这些基础研究方向的总体实力还比较薄弱。大陆学者每年在SODA上发表的论文一般不超过五篇,小编统计了一下2011年开始,每年接收的中国大陆学者的论文(以论文发表时署名单位为准,小编手动统计,不排除有个别遗漏)。 大陆学者的名字用中文显示,并在其第一次出现时做简单介绍。  

SODA 2011

640 (3)

1

Ning Chen, Nick Gravin, 陆品燕: On the Approximability of Budget Feasible Mechanisms.

Nick Gravin当时是南洋理工大学的博士生,陆品燕老师在微软亚洲研究院(MSRA)的实习生。

2

Jin-Yi Cai, 陆品燕, 夏盟佶: Dichotomy for Holant* Problems of Boolean Domain.

3

Elad Verbin, 俞玮: The Streaming Complexity of Cycle Counting, Sorting by Reversals, and Other Problems.

俞玮当时是清华大学交叉信息科学研究院的博士生,Elad Verbin是博士后。

4

贝小辉, Zhiyi Huang: Bayesian Incentive Compatibility via Fractional Assignments. 

贝小辉当时是清华大学交叉信息科学研究院的博士生,现在是南洋理工大学的助理教授,ITCS的访问教授。

5

Sungjin Im, 王亚军: Secretary Problems: Laminar Matroid and Interval Scheduling. 

王亚军当时是MSRA的副研究员。

SODA 2012

640 (4)

1

李梁, 陆品燕, 尹一通: Approximate counting via correlation decay in spin systems. 

李梁当时是北大的博士,陆品燕老师在MSRA的实习生; 尹一通是南京大学的教授,当时MSRA理论组铸星计划青年访问学者。

2

Henry Lam, Zhenming Liu, Michael Mitzenmacher, 孙晓锐, 王亚军: Information dissemination via random walks in d-dimensional space.  

孙晓锐当时是上海交通大学硕士生,MSRA实习生。

SODA 2013

640 (5)

1

Jin-Yi Cai, 陆品燕, 夏盟佶: Dichotomy for Holant* Problems with Domain Size 3

2

李梁, 陆品燕, 尹一通: Correlation Decay up to Uniqueness in Spin Systems.

3

尹一通, 张驰豪: Approximate Counting via Correlation Decay on Planar Graphs.  

张驰豪是陆品燕老师在上海交大的博士生。

4

Xiaocheng Hu, Cheng Sheng, Yufei Tao, 杨溢, 周水庚: Output-sensitive Skyline Algorithms in External Memory.  

周水庚是复旦大学教授,杨溢当时是其学生。

5

Dominik Scheder, 唐邦晟, 陈世腾, Navid Talebanfard: Exponential Lower Bounds for the PPSZ k-SAT Algorithm. 

唐邦晟,陈世腾当时是清华大学交叉信息科学研究院的博士生。

SODA 2014

640 (6)

1

林承宇, 刘景铖, 陆品燕: A Simple FPTAS for Counting Edge Covers. 

林承宇,刘景铖当时是上海交大ACM班学生,陆品燕老师当时执教该班的算法课。现在林承宇,刘景铖分别在哥伦比亚大学与加州大学伯克利分校攻读理论计算机博士学位。

2

MohammadTaghi Hajiaghayi, Wei Hu, 李建, Shi Li, Barna Saha: A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median.  

李建是清华大学交叉信息科学研究院的助理教授。

3

陈林, Klaus Jansen, 张国川: On the optimality of approximation schemes for the classical scheduling problem. 

张国川是浙江大学教授,陈林是其博士生。

4

Pravesh Kothari, Amir Nayyeri, Ryan O'Donnell, 吴成钢: Testing Surface Area. 

吴成钢当时是清华大学交叉信息科学研究院的博士生。

SODA 2015

640 (7)

1

刘景铖, 陆品燕: FPTAS for Counting Monotone CNF.

  刘景铖当时是陆品燕老师在MSRA的实习生。

2

姚期智: An n-to-1 Bidder Reduction for Multi-item Auctions and its Applications. 

姚期智先生是图灵奖得主,中科院院士,清华大学交叉信息科学研究院院长。

3

Alistair Sinclair, Piyush Srivastava, Daniel Stefankovic, 尹一通: Spatial mixing and the connective constant: Optimal bounds. 

SODA 2016

640 (8)

1

黄棱潇, 陆品燕, 张驰豪: Canonical Paths for MCMC: from Art to Science.  

黄棱潇当时是清华大学交叉信息科学研究院的博士生,陆品燕老师在MSRA的实习生。

2

段然, Jugal Garg, Kurt Mehlhorn: An Improved Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market. 

段然是清华大学交叉信息科学研究院的助理教授。

SODA 2017

640 (9)

1

陆品燕, 杨宽, 张驰豪, 朱旻申: An FPTAS for Counting Proper Four-Colorings on Cubic Graphs. 

杨宽,朱旻申都是陆品燕老师带的上交ACM班学生,现在分别在牛津大学,普渡大学读书。

2

黄棱潇, 李建: Stochastic k-Center and j-Flat-Center Problems

3

段然, Seth Pettie: Connectivity Oracles for Graphs Subject to Vertex Failures. 

4

段然, Seth Pettie and Hsin-Hao Su: Scaling Algorithms for Weighted Matching in General Graphs 

关于ITCS

上海财经大学理论计算机科学研究中心(ITCS)于2016年6月18日正式揭牌成立,成立一年多来,已初具规模,取得一定学术成果,产生一定学术声誉和影响力。现在已有5位全职的研究人员(其中一名即将入职),研究领域既涵盖理论计算机的核心领域包括算法与复杂性等,也包括很多理论计算机与其他领域的交叉,比如经济学,人工智能,复杂网络,统计物理等。这些年轻的研究员们已共计发表理论计算机及计算经济学的顶级会议与期刊STOC 11篇,FOCS 6篇,SODA 22篇,EC 9篇,SIAM Journal on Computing 8篇等,另外还在很多其他领域的重要会议及期刊发表论文,比如NIPS,WWW,IJCAI,AAAI,Mathematics of Operations Research,Games and Economic Behavior,Physical Review E,Scientific Reports等。 中心还拥有了一个由10余名海内外知名学者组成的讲席教授组,每人每年至少会在ITCS访问一个月,这个讲席教授组囊括了全球华人青年理论计算机科学家的半壁江山。一年多来,我们共接待来自全球各地的研究人员50余人次,组织学术讲座50余场,举办5次研讨会,4次暑期课程,学术活动非常丰富。