【一文尽览】22年计算机科学顶会“最佳论文”大盘点

---

  新智元报道 

来源：jeffhuang.com

编辑：三石

【新智元导读】本文作者Jeff Huang手动整理了自1996年至今，各大会议的“最佳论文”获奖情况。一定程度上反映了计算机各个子领域发展的趋势。

本文的数据大部分是由作者Jeff Huang手动输入的，通过联系过去的会议组织者，检索缓存的会议网站和搜索简历获得。

Jeff尝试从各个领域的顶级会议中获得最佳论文奖，但有些会议并没有这样的奖项(如SIGGRAPH, CAV)。“杰出论文奖”和“杰出论文奖”包括在内，但不包括“最佳学生论文”(如NIPS)或“最佳10年旧论文”(如POPL)。

本文整理了从1996年至今的“最佳论文”，所涉及的会议包括：

 AAAI   ACL   CHI   CIKM   CVPR   FOCS   FSE   ICCV   ICML   ICSE   IJCAI   INFOCOM   KDD   MOBICOM   NSDI   OSDI   PLDI   PODS   S&P   SIGCOMM   SIGIR   SIGMETRICS   SIGMOD   SODA   SOSP   STOC   UIST   VLDB   WWW

除了顶会“最佳论文”整理，Jeff等人还对学术机构进行了排名：

可以看出，微软研究院应当属于近22年来较为成功的学术机构；紧随其后的是华盛顿大学、卡耐基梅隆大学。值得注意的是，国内学术机构中，上榜名次较高的是清华大学，位居第24名。

由于篇幅过长，本文只显示上述会议中，前几个会议的最佳论文情况。读者若想阅读完整版本，可访问如下链接：

https://jeffhuang.com/best_paper_awards.html

AAAI (Artificial Intelligence)

2018	Memory-Augmented  Monte Carlo Tree Search	Chenjun  Xiao, University of Alberta; et al.
		Jincheng Mei, University of Alberta
		Martin Müller, University of Alberta
2017	Label-Free  Supervision of Neural Networks with Physics and Domain Knowledge	Russell  Stewart & Stefano Ermon, Stanford University
2016	Bidirectional  Search That Is Guaranteed to Meet in the Middle	Robert  C. Holte, University of Alberta; et al.
		Ariel Felner, Ben-Gurion University
		Guni Sharon, Ben-Gurion University
		Nathan R. Sturtevant, University of Denver
2015	From  Non-Negative to General Operator Cost Partitioning	Florian  Pommerening, University of Basel; et al.
		Malte Helmert, University of Basel
		Gabriele Röger, University of Basel
		Jendrik Seipp, University of Basel
2014	Recovering  from Selection Bias in Causal and Statistical Inference	Elias  Bareinboim, University of California Los Angeles; et al.
		Jin Tian, Iowa State University
		Judea Pearl, University of California Los Angeles
2013	HC-Search:  Learning Heuristics and Cost Functions for Structured Prediction	Janardhan  Rao Doppa, Oregon State University; et al.
		Alan Fern, Oregon State University
		Prasad Tadepalli, Oregon State University
	SMILe:  Shuffled Multiple-Instance Learning	Gary  Doran & Soumya Ray, Case Western Reserve University
2012	Learning  SVM Classifiers with Indefinite Kernels	Suicheng  Gu & Yuhong Guo, Temple University
	Document  Summarization Based on Data Reconstruction	Zhanying  He, Zhejiang University; et al.
		Chun Chen, Zhejiang University
		Jiajun Bu, Zhejiang University
		Can Wang, Zhejiang University
		Lijan Zhang, Zhejiang University
		Deng Cai, Zhejiang University
		Xiaofei He, Zhejiang University
2011	Dynamic  Resource Allocation in Conservation Planning	Daniel  Golovin, California Institute of Technology; et al.
		Andreas Krause, ETH Zurich
		Beth Gardner, North Carolina State University
		Sarah J. Converse, Patuxent Wildlife Research Center
		Steve Morey, U.S. Fish and Wildlife Service
	Complexity  of and Algorithms for Borda Manipulation	Jessica  Davies, University of Toronto; et al.
		George Katsirelos, Université Paris-Sud
		Nina Narodytska, University of New South Wales
		Toby Walsh, NICTA
2010	How  Incomplete Is Your Semantic Web Reasoner? Systematic Analysis of the  Completeness of Query Ans...	Giorgos  Stoilos, Oxford University; et al.
		Bernardo Cuenca Grau, Oxford University
		Ian Horrocks, Oxford University
	A  Novel Transition Based Encoding Scheme for Planning as Satisfiability	Ruoyun  Huang, Washington University in St. Louis; et al.
		Yixin Chen, Washington University in St. Louis
		Weixiong Zhang, Washington University in St. Louis
2008	How  Good is Almost Perfect?	Malte  Helmert & Gabriele Röger, Albert-Ludwigs-Universität Freiburg
	Optimal  False-Name-Proof Voting Rules with Costly Voting	Liad  Wagman & Vincent Conitzer, Duke University
2007	PLOW:  A Collaborative Task Learning Agent	James  Allen, Institute for Human and Machine Cognition; et al.
		Nathanael Chambers, Stanford University
		George Ferguson, University of Rochester
		Lucian Galescu, Institute for Human and Machine Cognition
		Hyuckchul Jung, Institute for Human and Machine Cognition
		Mary Swift, University of Rochester
		William Taysom, Institute for Human and Machine Cognition
	Thresholded  Rewards: Acting Optimally in Timed, Zero-Sum Games	Colin  McMillen & Manuela Veloso, Carnegie Mellon University
2006	Model  Counting: A New Strategy for Obtaining Good Bounds	Carla  P. Gomes, Cornell University; et al.
		Ashish Sabharwal, Cornell University
		Bart Selman, Cornell University
	Towards  an Axiom System for Default Logic	Gerhard  Lakemeyer, RWTH Aachen University
		Hector J. Levesque, University of Toronto
2005	The  Max K- Armed Bandit: A New Model of Exploration Applied to Search Heuristic  Selection	Vincent  A. Cicirello, Drexel University
		Stephen F. Smith, Carnegie Mellon University
2004	Learning  and Inferring Transportation Routines	Lin  Liao, University of Washington; et al.
		Dieter Fox, University of Washington
		Henry Kautz, University of Washington
2002	On  Computing All Abductive Explanations	Thomas  Eiter, Technische Universität Wien
		Kazuhisa Makino, Osaka University
2000	The  Game of Hex: An Automatic Theorem-Proving Approach to Game Programming	Vadim  V. Anshelevich, Vanshel Consulting
1999	PROVERB:  The Probabilistic Cruciverbalist	Greg  A. Keim, Duke University; et al.
		Noam M. Shazeer, Duke University
		Michael L. Littman, Duke University
		Sushant Agarwal, Duke University
		Catherine M. Cheves, Duke University
		Joseph Fitzgerald, Duke University
		Jason Grosland, Duke University
		Fan Jiang, Duke University
		Shannon Pollard, Duke University
		Karl Weinmeister, Duke University
1998	Learning  Evaluation Functions for Global Optimization and Boolean Satisfiability	Justin  A. Boyan & Andrew W. Moore, Carnegie Mellon University
	Acceleration  Methods for Numeric CSPs	Yahia  Lebbah & Olivier Lhomme, Ecole des Mines de Nantes
	The  Interactive Museum Tour-Guide Robot	Wolfram  Burgard, University of Bonn; et al.
		Armin B. Cremers, University of Bonn
		Dieter Fox, University of Bonn
		Dirk Hähnel, University of Bonn
		Gerhard Lakemeyer, Aachen University of Technology
		Dirk Schulz, University of Bonn
		Walter Steiner, University of Bonn
		Sebastian Thrun, Carnegie Mellon University
1997	Statistical  Parsing with a Context-Free Grammar and Word Statistics	Eugene  Charniak, Brown University
	A  Practical Algorithm for Finding Optimal Triangulations	Krill  Shoikhet & Dan Geiger, Technion
	Fast  Context Switching in Real-Time Propositional Reasoning	P.  Pandurang Nayak & Brian C. Williams, NASA Ames Research Center
	Building  Concept Representations from Reusable Components	Peter  Clark, Boeing
		Bruce Porter, University of Texas at Austin
1996	Verification  of Knowledge Bases Based on Containment Checking	Alon  Y. Levy, AT&T Laboratories
		Marie-Christine Rousset, Université Paris-Sud
	A  Novel Application of Theory Refinement to Student Modeling	Paul  T. Baffes, SciComp
		Raymond J. Mooney, University of Texas at Austin
	Pushing  the Envelope: Planning, Propositional Logic, and Stochastic Search	Henry  Kautz & Bart Selman, AT&T Laboratories

ACL (Natural Language Processing)

2018	Finding  syntax in human encephalography with beam search	John  Hale, Cornell University; et al.
		Chris Dyer, DeepMind
		Adhiguna Kuncoro, University of Oxford
		Jonathan R. Brennan, University of Michigan
2017	Probabilistic  Typology: Deep Generative Models of Vowel Inventories	Ryan  Cotterell & Jason Eisner, Johns Hopkins University
2016	Finding  Non-Arbitrary Form-Meaning Systematicity Using String-Metric Learning for  Kernel Regression	E.  Darío Gutiérrez, University of California Berkeley; et al.
		Roger Levy, Massachusetts Institute of Technology
		Benjamin K. Bergen, University of California San Diego
2015	Improving  Evaluation of Machine Translation Quality Estimation	Yvette  Graham, Trinity College Dublin
	Learning  Dynamic Feature Selection for Fast Sequential Prediction	Emma  Strubell, University of Massachusetts Amherst; et al.
		Luke Vilnis, University of Massachusetts Amherst
		Kate Silverstein, University of Massachusetts Amherst
		Andrew McCallum, University of Massachusetts Amherst
2014	Fast  and Robust Neural Network Joint Models for Statistical Machine Translation	Jacob  Devlin, Raytheon BBN Technologies; et al.
		Rabih Zbib, Raytheon BBN Technologies
		Zhongqiang Huang, Raytheon BBN Technologies
		Thomas Lamar, Raytheon BBN Technologies
		Richard Schwartz, Raytheon BBN Technologies
		John Makhoul, Raytheon BBN Technologies
2013	Grounded  Language Learning from Video Described with Sentences	Haonan  Yu & Jeffrey Mark Siskind, Purdue University
2012	String  Re-writing Kernel	Fan  Bu, Tsinghua University; et al.
		Hang Li, Microsoft Research
		Xiaoyan Zhu, Tsinghua University
	Bayesian  Symbol-Refined Tree Substitution Grammars for Syntactic Parsing	Hiroyuki  Shindo, NTT Communication Science Laboratories; et al.
		Yusuke Miyao, National Institute of Informatics
		Akinori Fujino, NTT Communication Science Laboratories
		Masaaki Nagata, NTT Communication Science Laboratories
2011	Unsupervised  Part-of-Speech Tagging with Bilingual Graph-Based Projections	Dipanjan  Das, Carnegie Mellon University
		Slav Petrov, Google
2010	Beyond  NomBank: A Study of Implicit Arguments for Nominal Predicates	Matthew  Gerber & Joyce Y. Chai, Michigan State University
2009	Reinforcement  Learning for Mapping Instructions to Actions	S.R.K.  Branavan, Massachusetts Institute of Technology; et al.
		Harr Chen, Massachusetts Institute of Technology
		Luke S. Zettlemoyer, Massachusetts Institute of Technology
		Regina Barzilay, Massachusetts Institute of Technology
	K-Best  A* Parsing	Adam  Pauls & Dan Klein, University of California Berkeley
	Concise  Integer Linear Programming Formulations for Dependency Parsing	André  F.T. Martins, Instituto de Telecomunicações; et al.
		Noah A. Smith, Carnegie Mellon University
		Eric P. Xing, Carnegie Mellon University
2008	Forest  Reranking: Discriminative Parsing with Non-Local Features	Liang  Huang, University of Pennsylvania
	A  New String-to-Dependency Machine Translation Algorithm with a Target  Dependency Language Model	Libin  Shen, BBN Technologies; et al.
		Jinxi Xu, BBN Technologies
		Ralph Weischedel, BBN Technologies
2007	Learning  synchronous grammars for semantic parsing with lambda calculus	Yuk  Wah Wong & Raymond J. Mooney, University of Texas at Austin
2006	Semantic  taxonomy induction from heterogenous evidence	Rion  Snow, Stanford University; et al.
		Daniel Jurafsky, Stanford University
		Andrew Y. Ng, Stanford University
2005	A  Hierarchical Phrase-Based Model for Statistical Machine Translation	David  Chiang, University of Maryland
2004	Finding  Predominant Word Senses in Untagged Text	Diana  McCarthy, University of Sussex; et al.
		Rob Koeling, University of Sussex
		Julie Weeds, University of Sussex
		John Carroll, University of Sussex
2003	Accurate  Unlexicalized Parsing	Dan  Klein & Christopher D. Manning, Stanford University
	Towards  a Model of Face-to-Face Grounding	Yukiko  I. Nakano, RISTEX; et al.
		Gabe Reinstein, Massachusetts Institute of Technology
		Tom Stocky, Massachusetts Institute of Technology
		Justine Cassell, Massachusetts Institute of Technology
2002	Discriminative  Training and Maximum Entropy Models for Statistical Machine Translation	Franz  Josef Och & Hermann Ney, RWTH Aachen University
2001	Immediate-Head  Parsing for Language Models	Eugene  Charniak, Brown University
	Fast  Decoding and Optimal Decoding for Machine Translation	Ulrich  Germann, University of Southern California; et al.
		Michael Jahr, Stanford University
		Kevin Knight, University of Southern California
		Daniel Marcu, University of Southern California
		Kenji Yamada, University of Southern California

FOCS (Theory)

2018	Classical  Verification of Quantum Computation	Urmila Mahadev,  University of California Berkeley
	Approximating  Edit Distance Within Constant Factor in Truly Sub-Quadratic Time	Diptarka  Chakraborty, Computer Science Institute of Charles University; et al.
		Debarati Das, Computer Science Institute of Charles University
		Elazar Goldenberg, The Academic College Of Tel Aviv-Yaffo
		Michal Koucký, Computer Science Institute of Charles University
		Michael Saks, Rutgers University
	Pseudorandom  Sets in Grassmann Graph have Near-Perfect Expansion	Subhash  Khot, New York University; et al.
		Dor Minzer, Tel-Aviv University
		Muli Safra, Tel-Aviv University
2017	A  dichotomy theorem for nonuniform CSPs	Andrei  A. Bulatov, Simon Fraser University
	The  Matching Problem in General Graphs is in Quasi-NC	Ola  Svensson & Jakub Tarnawski, École polytechnique fédérale de Lausanne
	The  Proof of CSP Dichotomy Conjecture	Dmitriy  Zhuk, Lomonosov Moscow State University
2016	Settling  the Complexity of Computing Approximate Two-Player Nash Equilibria	Aviad  Rubinstein, University of California Berkeley
	Fast  Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning	Ran  Raz, Weizmann Institute of Science
2015	An  average-case depth hierarchy theorem for Boolean circuits	Benjamin  Rossman, National Institute of Informatics; et al.
		Rocco A. Servedio, Columbia University
		Li-Yang Tan, University of California Berkeley
2014	Path  Finding Methods for Linear Programming: Solving Linear Programs in  O(sqrt(rank)) Iterations a...	Yin  Tat Lee & Aaron Sidford, Massachusetts Institute of Technology
2013	Navigating  Central Path with Electrical Flows: from Flows to Matchings, and Back	Aleksander  Mądry, École Polytechnique Fédérale de Lausanne
2012	A  multi-prover interactive proof for NEXP sound against entangled provers	Tsuyoshi  Ito, NEC Labs America
		Thomas Vidick, Massachusetts Institute of Technology
	A  Polylogarithimic Approximation Algorithm for Edge-Disjoint Paths with  Congestion 2	Julia  Chuzhoy, Toyota Technological Institute at Chicago
		Shi Li, Princeton University
2011	A  Randomized Rounding Approach to the Traveling Salesman Problem	Shayan  Oveis Gharan, Stanford University; et al.
		Amin Saberi, Stanford University
		Mohit Singh, McGill University
	A  Polylogarithmic-Competitive Algorithm for the k-Server Problem	Nikhil  Bansal, IBM Research; et al.
		Niv Buchbinder, Open University
		Aleksander Mądry, Massachusetts Institute of Technology
		Joseph Naor, Technion
	Approximating  Graphic TSP by Matchings	Tobia  M¨o;mke & Ola Svensson, Royal Institute of Technology
2010	Approximation  Algorithms for the Edge-Disjoint Paths Problem via Raecke Decompositions	Matthew  Andrews, Bell Labs
	Subexponential  Algorithms for Unique Games and Related Problems	Sanjeev  Arora, Princeton University; et al.
		Boaz Barak, Princeton University
		David Steurer, Princeton University
	Computational  Transition at the Uniqueness Threshold	Allan  Sly, Microsoft Research
2008	Two  Query PCP with Sub-Constant Error	Dana  Moshkovitz & Ran Raz, Weizmann Institute of Science
2007	Space-Efficient  Identity Based Encryption Without Pairings	Dan  Boneh, Stanford University; et al.
		Craig Gentry, Stanford University
		Michael Hamburg, Stanford University
2006	Settling  the Complexity of 2-Player Nash Equilibrium	Xi  Chen, Tsinghua University
		Xiaotie Deng, City University of Hong Kong
2005	The  Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability  of Negative Type M...	Subhash  A. Khot, Georgia Institute of Technology
		Nisheeth K. Vishnoi, IBM Research
	Correcting  Errors Beyond the Guruswami-Sudan Radius in Polynomial Time	Farzad  Parvaresh & Alexander Vardy, University of California San Diego
2004	Cryptography  in NC0	Benny  Applebaum, Technion; et al.
		Yuval Ishai, Technion
		Eyal Kushilevitz, Technion
	Hardness  of Approximating the Shortest Vector Problem in Lattices	Subhash  Khot, Georgia Institute of Technology
2003	On  the Impossibility of Dimension Reduction in L1	Bo  Brinkman & Moses Charikar, Princeton University
2002	A  Dichotomy Theorem for Constraints on a Three-Element Set	Andrei  A. Bulatov, University of Oxford
	Minimizing  Congestion in General Networks	Harald  Räcke, Paderborn University
	Constant-Round  Coin-Tossing with a Man in the Middle or Realizing the Shared Random String  Model	Boaz  Barak, Weizmann Institute of Science

原文链接：

https://jeffhuang.com/best_paper_awards.html

更多阅读：

• 突发！中国法院初步裁决禁售多款iPhone，高通告赢了苹果？

• 孟晚舟终获保释！抱律师哭泣，现场掌声雷动

• 禁售iPhone再升级！高通寻求美国禁止进口苹果，5G大战英特尔躺枪

---

【加入社群】

新智元AI技术+产业社群招募中，欢迎对AI技术+产业落地感兴趣的同学，加小助手微信号：aiera2015_2   入群;通过审核后我们将邀请进群，加入社群后务必修改群备注（姓名 - 公司 - 职位;专业群审核较严，敬请谅解）。