About

Local algorithms, that is, algorithms that compute and make decisions on parts of the output considering only a portion of the input, have been studied in a number of areas in theoretical computer science and mathematics. Some of these areas include sublinear-time algorithms, distributed algorithms, inference in large networks and graphical models. These communities have similar goals but a variety of approaches, techniques, and methods. This workshop is aimed at fostering dialogue and cross-pollination of ideas between the various communities. To this end, the workshop will feature a small number of longer talks that, in part, survey approaches by various communities, as well as short, focused talks on recent, exciting results. The first instantiation of the Workshop on Local Algorithms (WoLA) was held in Fall of 2016 (See https://www.microsoft.com/en-us/research/event/workshop-local-algorithms/ for details.)

We are inviting all students and postdocs to give a poster on their works. If we have time, we hope to accommodate very short talks as well. If you are interested in giving a poster and/or short talk, please contact Joanne Hanley at joanne@csail.mit.edu. Here is some advice about making the posters.

PLEASE NOTE: WoLA will be preceded by "Sublinear Algorithms, Local Algorithms and Robust Statistics" Workshop held June 11-13 with a bootcamp on June 10. Many of the talks will be relevant to WoLA attendees. The workshop is open to the public and is located in the same room as WoLA. See MIFODS.mit.edu/sublinear.php for more information.

Workshop Location

WOLA will be held in room 2-190 at MIT Department of Mathematics (182 Memorial Drive). Map The poster session on Thursday night will be held in 32-G449 (Stata Center). See Local Information for directions.

Confirmed Speakers and SCHEDULE

Clement Canonne, Distributed Simulation and Distributed Inference: Algorithms, Tradeoffs, and a Conjecture. Slides
Ann Condon, On design and analysis of chemical reaction network algorithms. Slides
Endre Csoka, Local algorithms on random graphs and on graph limits. Slides
Artur Czumaj, Testing H-freeness in Arbitrary Planar Graphs in Constant Time (Using Random Graph Exploration)
Ilias Diakonikolas, Computational Lower Bounds for Statistical Estimation Problems. Slides
Jelena Diakonikolas, Block Coordinate Descent and Exact Minimization. Slides
Charilaos Efthymiou, Improved bounds for sampling colorings of sparse random graphs. Slides
Guy Even, Local Computation Algorithms. Slides
Martin Farach-Colton, Closure Operators and Spam Markets for PageRank
Elena Grigorescu, Relaxed Locally Correctable Codes in Computationally Bounded Channels. Slides
Hamed Hassani, Submodular Maximization: The Decentralized Setting. Slides
Amin Karbasi, Probabilistic Submodular Maximization in Sub-Linear Time
Fabian Kuhn, On the Role of Randomization in Local Distributed Graph Algorithms
Sepideh Mahabadi, Set Cover in Sub-linear Time. Slides
Krzysztof Onak, Round Compression for Parallel Matching Algorithms. Slides
Merav Parter, Local Computation Algorithms for Spanners. Slides
Ami Paz, A (2+epsilon)-Approximation for Maximum Weight Matching in the Semi-Streaming Model. Slides
Seth Pettie, A Survey of the Distributed Lovasz Local Lemma Problem. Slides
Dana Randall, Local Algorithms for Programmable Active Matter
Sofya Raskhodnikova, Local Model for Differentially Private Data Analysis. Slides
Christian Sohler, Property Testing and Random Order Streams
Hsin-Hao Su, Optimal Gossip Algorithms for Exact and Approximate Quantile Computations. Slides
Ruediger Urbanke, Spatial-coupling: An Algorithm and a Proof Technique. Slides
Ramji Venkataramanan, Estimation of Low-Rank Matrices via Approximate Message Passing. Slides
Grigory Yaroslatsev, Badger Rampage: Multi-dimensional Balanced Partitioning of Facebook-scale Graphs. Slides
Yihong Wu, Recovering a Hidden Hamiltonian Cycle via Linear Programming. Slides
Yufei Zhao, Efficient property testing of induced bipartite patterns in groups. Slides

Confirmed Posters/Short Talks

Maryam Aliakbarpour, Differentially Private Identity and Equivalence Testing of Discrete Distributions. Slides
Omri Ben-Eliezer, Optimal testing of local properties via spherical queries. Slides
Yi-Jun Chang, Distributed Triangle Detection via Graph Partitioning. Slides
Michal Dory, Distributed Spanner Approximation. Slides
Talya Eden, Testing Bounded Arboricity. Slides
Hendrik Fichtenberger, A Sublinear Tester for Outerplanarity (and Other Forbidden Minors) With One-Sided Error. Slides
Manuela Fischer, Breaking the Linear-Memory Barrier in MPC: Fast MIS on Trees with $n^{\eps}$ Memory per Machine. Slides
Themis Gouleakis, Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover. Slides
Gautam Kamath, Sever: A Robust Meta-Algorithm for Stochastic Optimization
Ramesh Krishnan S. Pallavoor, Parameterized Property Testing of Functions
Amit Levi, Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs. Slides
Nithin Mahendra Varma, Erasure-resilient graph property testing. Slides
Yannic Maus, Deterministic Distributed Edge-Coloring with Fewer Colors. Slides
Yasamin Nazari, Distributed Distance-Bounded Network Design Through Distributed Convex Programming. Slides
Adam Sealfon, Population Stability: Regulating size in the presence of an adversary.
Huanyu Zhang, INSPECTRE: Privately Estimating the Unseen. Slides
Samson Zhou, Nearly-Optimal Distinct Elements and Heavy Hitters in the Sliding Window Model. Slides

Hotel Information

UPDATE: You can still try to get the Elliot hotel block price if you contact Maureen Toomey directly at mtoomey@eliothotel.com or 617-532-7126.
We have reserved a block of rooms at the Eliot Hotel in Boston under the group code WOLA18 for $275 per night. Guests can login to a special link at hotel or call them at 617-267-1607. Mention “WOLA18 Group” to get the discounted rate. THIS RATE IS GOOD UNTIL MAY 10, 2018. We strongly urge you to take advantage of this rate as hotels in Cambridge and Boston in June can be very pricey.

Guests must provide a valid credit card at the time of reservation.

Cancelations can be done up until 24 hours prior to the date of arrival without being charged.

All reservations are guaranteed for late arrival. If there is a no show, their credit card will be charged a one night’s room and tax.

The cut-off date for making reservations in the group rate is May 10th.

Contact Information

Joanne Hanley
CSAIL, MIT
telephone: (617) 253-6054
email: joanne at csail dot mit dot edu

Accessibility