Workshop on Local Algorithms - WOLA 2018
June 14-15, 2018, MIT, Cambridge, MA

Organizers:

  • Mohsen Ghaffari, ETH Zurich
  • Reut Levi, Weizmann Institute of Science
  • Moti Medina, Ben Gurion University
  • Andrea Montanari, Stanford
  • Elchanan Mossel, MIT
  • Ronitt Rubinfeld, MIT

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
Ann Condon, On design and analysis of chemical reaction network algorithms
Endre Csoka, Local algorithms on random graphs and on graph limits
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
Jelena Diakonikolas, Block Coordinate Descent and Exact Minimization
Charilaos Efthymiou, Improved bounds for sampling colorings of sparse random graphs
Guy Even, Local Computation Algorithms
Martin Farach-Colton, Closure Operators and Spam Markets for PageRank
Elena Grigorescu, Relaxed Locally Correctable Codes in Computationally Bounded Channels
Hamed Hassani, Submodular Maximization: The Decentralized Setting
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
Krzysztof Onak, Round Compression for Parallel Matching Algorithms
Merav Parter,
Local Computation Algorithms for Spanners
Ami Paz, A (2+epsilon)-Approximation for Maximum Weight Matching in the Semi-Streaming Model
Seth Pettie, A Survey of the Distributed Lovasz Local Lemma Problem
Dana Randall, Local Algorithms for Programmable Active Matter
Sofya Raskhodnikova, Local Model for Differentially Private Data Analysis
Christian Sohler, Property Testing and Random Order Streams
Hsin-Hao Su, Optimal Gossip Algorithms for Exact and Approximate Quantile Computations
Ruediger Urbanke, Spatial-coupling: An Algorithm and a Proof Technique
Ramji Venkataramanan, Estimation of Low-Rank Matrices via Approximate Message Passing
Grigory Yaroslatsev, Badger Rampage: Multi-dimensional Balanced Partitioning of Facebook-scale Graphs
Yihong Wu, Recovering a Hidden Hamiltonian Cycle via Linear Programming
Yufei Zhao,
Efficient property testing of induced bipartite patterns in groups

Confirmed Posters/Short Talks

Maryam Aliakbarpour, Differentially Private Identity and Equivalence Testing of Discrete Distributions
Omri Ben-Eliezer, Optimal testing of local properties via spherical queries
Yi-Jun Chang, Distributed Triangle Detection via Graph Partitioning
Michal Dory, Distributed Spanner Approximation
Talya Eden, Testing Bounded Arboricity
Hendrik Fichtenberger, A Sublinear Tester for Outerplanarity (and Other Forbidden Minors) With One-Sided Error
Manuela Fischer, Breaking the Linear-Memory Barrier in MPC: Fast MIS on Trees with $n^{\eps}$ Memory per Machine
Themis Gouleakis
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
Nithin Mahendra Varma, Erasure-resilient graph property testing
Yannic Maus, Deterministic Distributed Edge-Coloring with Fewer Colors
Yonatan Nakar, On the Testability of Graph Partition Properties
Yasamin Nazari, Distributed Distance-Bounded Network Design Through Distributed Convex Programming
Adam Sealfon
Ali Vakilian
Huanyu Zhang
Samson Zhou, Nearly-Optimal Distinct Elements and Heavy Hitters in the Sliding Window Model

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