Postdoctoral fellow Anup B. Rao, as well as SCS Ph.D. students David Durfee and Kevin A. Lai, made substantial contributions to five research papers accepted to the 2016 FOCS symposium. In addition, SCS Professors Santosh Vempala, Eric Vigoda, and Assistant Professor Richard Peng aided in the research featured in the papers.

The research teams analyzed core FOCS topics, such as dynamic algorithms and Newton iteration to name a few. Each paper was selected because of its contributions to broadening the reach of computing, while raising important questions that can benefit from investigation.

Sponsored by the Institute of Electrical and Electronics Engineers (IEEE) Computer Society, the FOCS symposium, along with its sister conference, the ACM Symposium on Theory of Computing (STOC), is one of two leading conference on theoretical computer science. The goal of FOCS is to provide extensive coverage and distribution of foundational research in theoretical computer science among researchers, academics, and practitioners.

For more information on the 2016 FOCS symposium and the papers accepted, please use the links provided.

Accelerated Newton Iteration for Roots of Black Box Polynomials

Anand Louis (Princeton University); Santosh Vempala (Georgia Institute of Technology, USA)

Agnostic Estimation of Mean and Covariance

Kevin Lai, Anup Rao, and Santosh Vempala (Georgia Institute of Technology)

Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model

Charilaos Efthymiou (Goethe University, Frankfurt); Thomas P. Hayes (University of New Mexico); Daniel Stefankovic (University of Rochester); Eric Vigoda (Georgia Institute of Technology); Yitong Yin (Nanjing University)

Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More

Michael B. Cohen, Jonathan Kelner, John Peebles (Massachusetts Institute of Technology); Richard Peng (Georgia Institute of Technology); Aaron Sidford (Microsoft Research - New England); Adrian Vladu (Massachusetts Institute of Technology)

On Fully Dynamic Graph Sparsifiers

Ittai Abraham (VMware Research); David Durfee (Georgia Institute of Technology); Ioannis Koutis (University of Puerto Rico -  Rio Piedras); Sebastian Krinninger (Max Planck Institute for Informatics); Richard Peng (Georgia Institute of Technology)