*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Algorithms & Randomness Center (ARC) and ACO Joint Colloquium
Monday, August 31, 2015
Klaus 1116 East & West - 1:00 pm
(Refreshments will be served in Klaus 2222 at 2 pm)
Title:
Algorithm Frameworks Based on Structure Preserving Sampling
Abstract:
Sampling is a widely used algorithmic tool: running routines on a small representative subset of the data often leads to speedups while preserving accuracy. Recent works on algorithmic frameworks that relied on sampling graphs and matrices highlighted several connections between graph theory, statistics, optimization, and functional analysis. This talk will describe some key ideas that emerged from these connections:
* Sampling as a generalized divide-and-conquer paradigm.
* Implicit sampling without constructing the larger data set, and its algorithmic applications.
* What does sampling need to preserve? What can sampling preserve?
These ideas have applications in solvers for structured linear systems, network flow algorithms, input-sparsity time numerical routines, coresets, and dictionary learning.
