Award Winners
Best Paper Award
-
Lower bounds for maximal matchings and maximal independent sets
Authors: Alkida Balliu (Aalto University); Sebastian Brandt (ETH Zurich); Juho Hirvonen, Dennis Olivetti (Aalto University); Mikaël Rabie (Aalto University and University Paris Sorbonne); Jukka Suomela (Aalto University) -
NEEXP ⊆ MIP*
Authors: Anand Natarajan (California Institute of Technology); John Wright (Massachusetts Institute of Technology) -
Automating Resolution is NP-Hard
Authors: Albert Atserias, Moritz Müller (Universitat Politecnica de Catalunya)
Machtey Award (Best Student Paper)
-
Efficient Construction of Rigid Matrices Using an NP Oracle
Authors: Josh Alman, Lijie Chen (MIT) -
Faster Minimum k-cut of a Simple Graph
Authors: Jason Li (Carnegie Mellon University)
FOCS Test of Time Award
1989
-
The Weighted Majority Algorithm
Authors: Nick Littlestone, Manfred K. Warmuth -
Constant Depth Circuits, Fourier Transform, and Learnability
Authors: Nathan Linial, Yishay Mansour, Noam Nisan -
On the Computational Power of PP and (+)P
Authors: Seinosuke Toda
1999
- Cache-Oblivious Algorithms
Authors: Matteo Frigo, Charles E. Leiserson, Harald Prokop, Sridhar Ramachandran
TCMF Distinguished Service Award: Sandy Irani
The Steering Committee of the IEEE Technical Committee on Mathematical Foundations of Computing recognizes and thanks
for her dedicated and indispensable service to the theory community; for her chairing of the SafeToC ad-hoc committee, and her dedicated involvement in adopting and implementing its recommendations at FOCS and many other theory conferences.