The Power of Randomness in Computation

March 16 - 20, 2015

Discrete Structures: Analysis and Applications

Content

Overview

Advisory:

Please note, this workshop will take place at Georgia Institute of Technology in Atlanta, Georgia.

Poster:

W3.16-20.15_poster.pdf

Organizers:

Dana Randall	Georgia Institute of Technology
Prasad Tetali	Georgia Institute of Technology
Santosh Vempala	Georgia Institute of Technology
Eric Vigoda	Korea Advanced Institute of Science and Technology (KAIST)

This workshop will bring together researchers from a variety of fields to highlight new results broadly related to the use of randomization in algorithm design. Talks will highlight new results in the area of randomized algorithms and probabilistic tools for algorithm design. The workshop will also include recent successes in derandomization and problems where there are efficient deterministic algorithms but not yet randomized versions, such as Weitz's approximate counting approach and recent extensions of it. The workshop will attempt to bring various experts interested in this general theme and identify challenging open problems and discuss ways to approach and attack them.

Schedule

Monday, March 16, 2015

9:00 am - 9:30 am	Coffee/Light Food
9:30 am - 10:10 am	The Complexity of Approximating Complex-Valued Ising and Tutte Partition Functions Leslie Goldberg (University of Oxford)	Klaus 2443
10:20 am - 11:00 am	Random Graph Coloring: The Replica Symmetric Phase Amin Coja-Oghlan (Johann Wolfgang Goethe-Universität Frankfurt)	Klaus 2443
11:00 am - 11:20 am	Break
11:20 am - 12:00 pm	The Exact k-SAT Threshold for Large k Nike Sun (Microsoft Research)	Klaus 2443
12:00 pm - 2:00 pm	Lunch
2:00 pm - 2:40 pm	The Melbourne Shuffle: Secure Oblivious Storage in the Cloud Eli Upfal (Brown University)	Klaus 2443
2:50 pm - 3:30 pm	Invertible Bloom Lookup Tables and Applications Michael Mitzenmacher (Harvard University)	Klaus 2443
3:30 pm - 4:00 pm	Tea
4:00 pm - 4:40 pm	Recent Progress on the Lovasz Local Lemma Aravind Srinivasan (University of Maryland)	Klaus 2443

Tuesday, March 17, 2015

9:00 am - 9:30 am	Coffee/Light Food
9:30 am - 10:10 am	Counting Small Subgraphs with a Specified Property in a Large Graph Mark Jerrum (Queen Mary and Westfield College)	Klaus 2443
10:20 am - 11:00 am	Spin Systems: Hardness of Approximate Counting via Phase Transitions Andreas Galanis (University of Oxford)	Klaus 2443
11:00 am - 11:05 am	Group Photo
11:05 am - 11:20 am	Break
11:20 am - 12:00 pm	Approximate Counting via Correlation Decay Pinyan Lu (Microsoft Research)	Klaus 2443
12:00 pm - 2:00 pm	Lunch
2:00 pm - 2:40 pm	Cool with a Gaussian: A Cubic Volume Algorithm Ben Cousins (Georgia Institute of Technology)	Klaus 2443
2:50 pm - 3:30 pm	Electrical Flows and Fast Graph Algorithms Aleksander Madry (Massachusetts Institute of Technology)	Klaus 2443
3:30 pm - 4:00 pm	Tea
4:00 pm - 4:40 pm	Decay of Correlations for the Hardcore Model in Random Regular Graphs Nayantara Bhatnagar (University of Delaware)	Klaus 2443

Wednesday, March 18, 2015

9:00 am - 9:30 am	Coffee/Light Food
9:30 am - 10:10 am	Solution Clusters for Locked CSP's: Random XORSAT on a Fixed Degree Sequence Mike Molloy (University of Toronto)	Klaus 1116
10:20 am - 11:00 am	On the Switch Markov Chain for Perfect Matchings Martin Dyer (University of Leeds)	Klaus 1116
11:00 am - 11:20 am	Break
11:20 am - 12:00 pm	Sampling Quasistationary Distributions: Computational Efficiency and Particle Based Algorithms Roberto Oliveira (Institute of Pure and Applied Mathematics (IMPA))	Klaus 1116
12:00 pm - 2:00 pm	Lunch
3:30 pm - 4:00 pm	Tea
4:00 pm - 5:00 pm	Open Problem Session
5:00 pm - 6:30 pm	Poster Session and Reception

Thursday, March 19, 2015

9:00 am - 9:30 am	Coffee/Light Food
9:30 am - 10:10 am	Towards Optimal Algorithms for Prediction with Expert Advice Yuval Peres (Microsoft Research)	Klaus 1116
10:20 am - 11:00 am	The Surprising Power of Randomness in Belief Propagation. Elchanan Mossel (University of California, Berkeley)	Klaus 1116
11:00 am - 11:20 am	Break
11:20 am - 12:00 pm	Phase Transitions in Random Dyadic Tilings and Rectangular Dissections Sarah Miracle (Georgia Institute of Technology)	Klaus 1116
12:00 pm - 2:00 pm	Lunch
2:00 pm - 2:40 pm	Rectangles are Nonnegative Juntas Raghu Meka (University of California, Los Angeles)	Klaus 1116
2:50 pm - 3:30 pm	Counting Perfect Matchings via Random Matrices Mark Rudelson (University of Michigan)	Klaus 1116
3:30 pm - 4:00 pm	Tea
4:00 pm - 4:40 pm	Diffusion, Entropy, and the Geometry of Sets in Gaussian Space James Lee (University of Washington)	Klaus 1116

Friday, March 20, 2015

9:00 am - 9:30 am	Coffee/Light Food
9:30 am - 10:10 am	Some New Results on Random Points in the Unit Square Alan Frieze (Carnegie-Mellon University)	Klaus 1116
10:20 am - 11:00 am	Structure and Pseudo-Randomness in Coding Theory Shachar Lovett (University of California, San Diego)	Klaus 1116
11:00 am - 11:20 am	Break
11:20 am - 12:00 pm	Testing the Manifold Hypothesis Hariharan Narayanan (University of Washington)	Klaus 1116

Participants

Name	Department	Affiliation
Victor Bapst		Johann Wolfgang Goethe-Universität Frankfurt
Ivona Bezakova	Department of Computer Science	Rochester Institute of Technology
Prateek Bhakta	Algorithms, Combinatorics and Optimization	Georgia Institute of Technology
Nayantara Bhatnagar	Department of Mathematical Sciences	University of Delaware
Milan Bradonjic	Mathematics of Networks and Systems	Alcatel-Lucent Technologies Bell Laboratories
Steve Butler	Department of Mathematics	Iowa State University
Jin-Yi Cai	Department of Computer Science	University of Wisconsin, Madison
Sarah Cannon		Georgia Institute of Technology
Guantao Chen	Department of Mathematics and Statistics	Georgia State University
Ameera Chowdhury	Institute for Mathematics and its Applications	University of Minnesota, Twin Cities
Emma Cohen	Department of Mathematics	Georgia Institute of Technology
Amin Coja-Oghlan	Mathematics Institute	Johann Wolfgang Goethe-Universität Frankfurt
Ben Cousins	College of Computing	Georgia Institute of Technology
David Durfee		Georgia Institute of Technology
Martin Dyer	School of Computing	University of Leeds
Charilaos Efthymiou	College of Computing	Georgia Institute of Technology
Naomi Feldheim	Institute for Mathematics and its Applications	University of Minnesota, Twin Cities
Ohad Feldheim	Institute for Mathematics and its Applications	University of Minnesota, Twin Cities
Laura Florescu	Courant Institute of Mathematical Sciences	New York University
Alan Frieze	Department of Mathematical Sciences	Carnegie-Mellon University
Andreas Galanis	Department of Computer Science	University of Oxford
Shirshendu Ganguly	Department of Mathematics	University of Washington
David Goldberg		Georgia Institute of Technology
Leslie Goldberg	Department of Computer Science	University of Oxford
Heng Guo	Computer Sciences	University of Wisconsin, Madison
Alex Gutierrez	Department of Mathematics	University of Minnesota, Twin Cities
Zachary Hamaker	Institute for Mathematics and its Applications	University of Minnesota, Twin Cities
Thomas Hayes	Computer Science Department	University of New Mexico
Peng He	Department of Mathematics	University of Pittsburgh
Samuel Hetterich		Johann Wolfgang Goethe-Universität Frankfurt
Seyed Kaave Hosseini	Department of Computer Science	University of California
Hao Huang	Institute for Mathematics and its Applications	University of Minnesota, Twin Cities
Nor Jaafari		Johann Wolfgang Goethe-Universität Frankfurt
Mark Jerrum	School of Mathematical Sciences	Queen Mary and Westfield College
Arindam Khan	School of Computer Science	Georgia Institute of Technology
James Lee	Department of Computer Science	University of Washington
Jiange Li	Department of Mathematics	University of Delaware
Richard Lipton	College of Computing	Georgia Institute of Technology
Shachar Lovett	Department of Computer Science and Engineering	University of California, San Diego
Pinyan Lu	Theory Group	Microsoft Research
Aleksander Madry	Department of Electrical Engineering and Computer Science	Massachusetts Institute of Technology
Zeinab Maleki	Department of Mathematical Sciences	Isfahan University of Technology
Ryan Martin	Department of Mathematics	Iowa State University
Raghu Meka	Computer Science Department	University of California, Los Angeles
Milena Mihail	College of Computing	Georgia Institute of Technology
Sarah Miracle	College of Computing	Georgia Institute of Technology
Abhinav Mishra		Georgia Institute of Technology
Michael Mitzenmacher	Department of Computer Science	Harvard University
Mike Molloy	Department of Computer Science	University of Toronto
Elchanan Mossel	Department of Statistics	University of California, Berkeley
Hariharan Narayanan	Department of Statistics and Mathematics	University of Washington
Humberto Naves	Institute for Mathematics and its Applications	University of Minnesota, Twin Cities
Roberto Oliveira		Institute of Pure and Applied Mathematics (IMPA)
Ioannis Panageas		Georgia Institute of Technology
Yuval Peres	Theory Group	Microsoft Research
Sebastian Pokutta	School of Industrial and Systems Engineering	Georgia Institute of Technology
Dana Randall	College of Computing	Georgia Institute of Technology
Felicia Rassmann		Johann Wolfgang Goethe-Universität Frankfurt
Michaela Rombach	Department of Mathematics	University of California, Los Angeles
Aurko Roy		Georgia Institute of Technology
Mark Rudelson	Department of Mathematics	University of Michigan
Youngsoo Seol	Department of Mathematics	Texas State University-San Marcos
Kathrin Skubch		Johann Wolfgang Goethe-Universität Frankfurt
Aravind Srinivasan	Department of Computer Science	University of Maryland
Daniel Stefankovic	Department of Computer Science	University of Rochester
Amanda Streib		Institute for Defense Analyses
Noah Streib	Applied and Computational Mathematics Division	National Institute of Standards and Technology
Nike Sun		Microsoft Research
Prasad Tetali	School of Mathematics and College of Computing	Georgia Institute of Technology
Eli Upfal	Department of Computer Science	Brown University
Vijay Vazirani	College of Computing	Georgia Institute of Technology
Santosh Vempala	College of Computing	Georgia Institute of Technology
Eric Vigoda		Korea Advanced Institute of Science and Technology (KAIST)
Bartosz Walczak	School of Mathematics	Georgia Institute of Technology
Ke Wang	Institute for Mathematics and its Applications	University of Minnesota, Twin Cities
Liguo Wang	Department of Mathematics	University of Tennessee
Yan Wang	School of Mathematics	Georgia Institute of Technology
Matthew Wright	Institute for Mathematics and its Applications	University of Minnesota, Twin Cities
Rupei Xu	Department of Computer Science	University of Texas at Dallas
Sadra Yazdanbod		Georgia Institute of Technology
Yitong Yin	Department of Computer Science and Technology	Nanjing University
Yumeng Zhang	Department of Statistics	University of California, Berkeley
Jun Zhao	Department of Electrical and Computer Engineering	Carnegie-Mellon University
Lingjiong Zhu	School of Mathematics	University of Minnesota, Twin Cities