ARC Hosts Third Workshop on Algorithms and Randomness

The School of Computer Science’s Algorithms and Randomness Center (ARC) hosted its third Algorithms and Randomness Workshop from May 14 to 17. More than 70 scholars attended the 27 talks by leading researchers in the field.

The workshop brought together researchers from multiple disciplines, including combinatorics, computational complexity, optimization, probability, randomized algorithms, and statistical physics. While some speakers presented recent breakthrough results, others gave overviews on specific research areas or problems.

Some research highlights:

-Daniel Dadush, a researcher at Centrum Wiskunde & Informatica (Netherlands) and a GT alumnus, presented A Friendly Smoothed Analysis of the Simplex Method, providing an improved and simpler analysis of the shadow vertex simplex method.

-Professor Mark Jerrum of Queen Mary University of London, a Markov chain Monte Carlo pioneer, presented A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability on all terminal reliability of undirected graphs.

-Will Perkins, a fellow at University of Birmingham (UK), presented Sphere Packings, Codes, and Kissing Numbers via Hard Core Models, proving a lower bound on the expected size of spherical code from hard cap models.

-Professor Sofya Raskhodnikova of Boston University, an expert on property testing, presented Fast Algorithms for Testing Geometric Properties, which included an introduction and survey of the field.

-Professor Virginia Vassilevska-Williams of MIT presented Towards Tight Approximation Bounds for Graph Diameter and Eccentricities about breakthrough lower bounds on estimating the diameter of a graph, assuming the strong exponential-time hypothesis.

The workshop—organized by ARC director Professor Eric Vigoda, Professor Santosh Vempala, and Professor Prasad Tetalialso intended to introduce burgeoning scholars to the larger community and foster collaboration.

“Several senior researchers were particularly impressed at the next generation of researchers, judging by the high-quality results and lectures presented,” said Tetali. “It was gratifying, as well as humbling, to see and hear of breakthrough results by former postdocs and students of Georgia Tech colleagues and their collaborators.”

Related Media

Click on image(s) to view larger version(s)

  • ARC Workshop

For More Information Contact

Tess Malone, Communications Officer