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

  • 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

  • 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

Sandy Irani

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.