{"id":279911,"date":"2016-08-19T08:56:18","date_gmt":"2016-08-19T15:56:18","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/?post_type=msr-event&#038;p=279911"},"modified":"2016-11-07T11:19:50","modified_gmt":"2016-11-07T19:19:50","slug":"workshop-local-algorithms","status":"publish","type":"msr-event","link":"https:\/\/www.microsoft.com\/en-us\/research\/event\/workshop-local-algorithms\/","title":{"rendered":"Workshop on Local Algorithms"},"content":{"rendered":"<p><strong>Venue:<\/strong><\/p>\n<p><span style=\"text-decoration: underline;\">October 14, 2016<\/span><br \/>\n<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/lab\/microsoft-research-new-england\/\" target=\"_blank\">Microsoft Research New England<\/a><br \/>\nCambridge, MA 02142<\/p>\n<p><span style=\"text-decoration: underline;\">October 15, 2016<\/span><br \/>\n<a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"http:\/\/web.mit.edu\/\" target=\"_blank\">Massachusetts Institute of Technology<\/a><br \/>\nCambridge, MA 02139<\/p>\n<p><strong>Contact us:<\/strong>\u00a0If you have any questions regarding this event please send email to\u00a0<a href=\"mailto:WOLA2016@microsoft.com\">WOLA2016@microsoft.com<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>This workshop was aimed at fostering dialogue and cross-pollination of ideas between the various communities studying local algorithms. To this end, the workshop featured longer talks that, in part, surveyed approaches by various communities, as well as short, focused talks on recent, exciting results.<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr_startdate":"2016-10-14","msr_enddate":"2016-10-15","msr_location":"Cambridge, MA, USA","msr_expirationdate":"","msr_event_recording_link":"","msr_event_link":"","msr_event_link_redirect":false,"msr_event_time":"","msr_hide_region":true,"msr_private_event":false,"footnotes":""},"research-area":[13561],"msr-region":[197900],"msr-event-type":[197944],"msr-video-type":[],"msr-locale":[268875],"msr-program-audience":[],"msr-post-option":[],"msr-impact-theme":[],"class_list":["post-279911","msr-event","type-msr-event","status-publish","hentry","msr-research-area-algorithms","msr-region-north-america","msr-event-type-hosted-by-microsoft","msr-locale-en_us"],"msr_about":"<strong>Venue:<\/strong>\r\n\r\n<span style=\"text-decoration: underline;\">October 14, 2016<\/span>\r\n<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/lab\/microsoft-research-new-england\/\" target=\"_blank\">Microsoft Research New England<\/a>\r\nCambridge, MA 02142\r\n\r\n<span style=\"text-decoration: underline;\">October 15, 2016<\/span>\r\n<a href=\"http:\/\/web.mit.edu\/\" target=\"_blank\">Massachusetts Institute of Technology<\/a>\r\nCambridge, MA 02139\r\n\r\n<strong>Contact us:<\/strong>\u00a0If you have any questions regarding this event please send email to\u00a0<a href=\"mailto:WOLA2016@microsoft.com\">WOLA2016@microsoft.com<\/a>","tab-content":[{"id":0,"name":"About","content":"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 was aimed at fostering dialogue and cross-pollination of ideas between the various communities. To this end, the workshop featured longer talks that, in part, surveyed approaches by various communities, as well as short, focused talks on recent, exciting results.\r\n\r\n[col-1-2]\r\n<h2>Overview talks<\/h2>\r\n<ul>\r\n \t<li><a href=\"http:\/\/www.ee.princeton.edu\/research\/eabbe\/\" target=\"_blank\">Emmanuel Abbe<\/a>,\u00a0Princeton University<\/li>\r\n \t<li><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/borgs\/\" target=\"_blank\">Christian Borgs<\/a>, Microsoft Research<\/li>\r\n \t<li><a href=\"http:\/\/people.csail.mit.edu\/ghaffari\/\" target=\"_blank\">Mohsen Ghaffari<\/a>,\u00a0ETH Zurich<\/li>\r\n \t<li><a href=\"http:\/\/www.stat.berkeley.edu\/~mossel\/\" target=\"_blank\">Elchanan Mossel<\/a>,\u00a0Massachusetts Institute of Technology<\/li>\r\n \t<li><a href=\"http:\/\/www.eng.tau.ac.il\/~danar\/\" target=\"_blank\">Dana Ron<\/a>,\u00a0Tel Aviv University<\/li>\r\n<\/ul>\r\n[\/col-1-2]\r\n\r\n[col-1-2_last]\r\n<h2>Organizing committee<\/h2>\r\n<ul>\r\n \t<li><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/borgs\/\" target=\"_blank\">Christian Borgs<\/a><\/li>\r\n \t<li><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/jchayes\/\" target=\"_blank\">Jennifer Chayes<\/a><\/li>\r\n \t<li><a href=\"http:\/\/www.mit.edu\/~yash\/\" target=\"_blank\">Yash Deshpande<\/a><\/li>\r\n \t<li><a href=\"http:\/\/people.mpi-inf.mpg.de\/~rlevi\/\" target=\"_blank\">Reut Levi<\/a><\/li>\r\n \t<li><a href=\"http:\/\/people.csail.mit.edu\/ronitt\/\" target=\"_blank\">Ronitt Rubinfeld<\/a><\/li>\r\n<\/ul>\r\n[\/col-1-2_last]\r\n<h2>Confirmed participants<\/h2>\r\n[col-1-2]\r\n<ul>\r\n \t<li>Maryam Aliakbarpour, Massachusetts Institute of Technology<\/li>\r\n \t<li>Zeyuan Allen-Zhu, Massachusetts Institute of Technology<\/li>\r\n \t<li>Alkida Balliu, Gran Sasso Science Institute<\/li>\r\n \t<li>Tugkan Batu, London School of Economics and Political Science<\/li>\r\n \t<li>Clement Canonne, Columbia University<\/li>\r\n \t<li>Artur Czumaj, University of Warwick<\/li>\r\n \t<li>Laurent Feuilloley, University of Paris Diderot<\/li>\r\n \t<li>Pierre Fraigniaud, University of Paris Diderot<\/li>\r\n \t<li>David Gamarnik, MIT Sloan School of Management<\/li>\r\n \t<li>Shafi Goldwasser, Massachusetts Institute of Technology<\/li>\r\n \t<li>Mika Goos, University of Toronto<\/li>\r\n \t<li>Elena Grigorescu, Purdue University<\/li>\r\n \t<li>Amin Karbasi, Yale University<\/li>\r\n \t<li>Kevin Matulef, Sandia National Laboratories<\/li>\r\n \t<li>Moti Medina, Max Planck Institute<\/li>\r\n \t<li>Jason Morton, Pennsylvania State University<\/li>\r\n \t<li>Meiram Murzabulatov, Pennsylvania State University<\/li>\r\n \t<li>Huy N. Nguyen, Northeastern University<\/li>\r\n \t<li>Dennis Olivetti, Gran Sasso Science Institute<\/li>\r\n<\/ul>\r\n[\/col-1-2]\r\n\r\n[col-1-2_last]\r\n<ul>\r\n \t<li>Krzystof Onak, IBM<\/li>\r\n \t<li>Lorenzo Orecchia, Boston University<\/li>\r\n \t<li>Asu Ozdaglar, Massachusetts Institute of Technology<\/li>\r\n \t<li>John Peebies<\/li>\r\n \t<li>Vijaya Ramachandran, University of Texas at Austin<\/li>\r\n \t<li>Sofya Raskhodnikova, Pennsylvania State University<\/li>\r\n \t<li>Adi Rosen, University of Paris Diderot<\/li>\r\n \t<li>Devavrat Shah, Massachusetts Institute of Technology<\/li>\r\n \t<li>Asaf Shapira, Tel Aviv University<\/li>\r\n \t<li>Christian Sohler, Technical University of Dortmund<\/li>\r\n \t<li>Hsin-Hao Su<\/li>\r\n \t<li>Madhu Sudan, Harvard University<\/li>\r\n \t<li>Jukka Suomela, Aalto University<\/li>\r\n \t<li>Robert Tarjan, Princeton University<\/li>\r\n \t<li>Ali Vakilian, Massachusetts Institute of Technology<\/li>\r\n \t<li>Greg Valiant, Stanford University<\/li>\r\n \t<li>Shai Vardi,\u00a0California Institute of Technology<\/li>\r\n \t<li>Nithin Varma, Pennsylvania State University<\/li>\r\n \t<li>Gandikota Venkata<\/li>\r\n \t<li>Anak Yodpinyanee, Massachusetts Institute of Technology<\/li>\r\n<\/ul>\r\n[\/col-1-2_last]"},{"id":1,"name":"Agenda","content":"<h2>Day 1 | Friday, October 14<\/h2>\r\n<table class=\"msr-table-schedule\">\r\n<thead class=\"thead\">\r\n<tr class=\"tr\">\r\n<th class=\"th\">Time<\/th>\r\n<th class=\"th\">Session<\/th>\r\n<th class=\"th\">Speaker<\/th>\r\n<\/tr>\r\n<\/thead>\r\n<tbody class=\"tbody\">\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">8:30\u20139:00<\/div><\/td>\r\n<td>Registration and Breakfast<\/td>\r\n<td><\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">9:00\u20139:10<\/div><\/td>\r\n<td>Opening remarks<\/td>\r\n<td>Ronitt Rubinfeld<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">9:10\u20139:50<\/div><\/td>\r\n<td>The power of locality for network algorithms<\/td>\r\n<td>Christian Borgs<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">9:50\u201310:10<\/div><\/td>\r\n<td>Latent Space Model (aka Blind Regression)<\/td>\r\n<td>Devavrat Shah<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">10:10\u201310:30<\/div><\/td>\r\n<td>Global Convergence Rate of Proximal Incremental Aggregated Gradient Methods<\/td>\r\n<td>Asu Ozdaglar<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">10:30\u201310:50<\/div><\/td>\r\n<td>Break<\/td>\r\n<td><\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">10:50\u201311:30<\/div><\/td>\r\n<td>A short (and partial) survey on Partition Oracles<\/td>\r\n<td>Dana Ron<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">11:30\u201311:50<\/div><\/td>\r\n<td>Local Computation Algorithms for High Degree Graphs<\/td>\r\n<td>Shai Vardi<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">11:50\u201312:10<\/div><\/td>\r\n<td>Testing Graph Properties with a Polynomial Query Complexity<\/td>\r\n<td>Asaf Shapira<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">12:10\u201312:30<\/div><\/td>\r\n<td>A Local Algorithm for Constructing Spanners in Minor-Free Graphs<\/td>\r\n<td>Reut Levi<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">12:30\u20132:10<\/div><\/td>\r\n<td>Lunch<\/td>\r\n<td><\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">2:10\u20132:50<\/div><\/td>\r\n<td>Local to global amplification: the block model vignette<\/td>\r\n<td>Emmanuel Abbe<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">2:50\u20133:10<\/div><\/td>\r\n<td>On Limits of Local Algorithms for Solving Random Constraint Satisfaction Problems<\/td>\r\n<td>David Gamarnik<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">3:10\u20133:30<\/div><\/td>\r\n<td>Locality in Coding Theory<\/td>\r\n<td>Madhu Sudan<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">3:30\u20133:50<\/div><\/td>\r\n<td>Local algorithms, message passing and the hidden clique problem<\/td>\r\n<td>Yash Deshpande<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">3:50\u20134:20<\/div><\/td>\r\n<td>\r\n<div class=\"msr-table-schedule-cell\">Break<\/div><\/td>\r\n<td><\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">4:20\u20135:00<\/div><\/td>\r\n<td>A few perspectives on local algorithms for sparse graphs<\/td>\r\n<td>Elchanan Mossel<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">5:00\u20135:20<\/div><\/td>\r\n<td>Sublinear Time Algorithms via Optimization<\/td>\r\n<td>Zheyuan Allen-Zhu<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">5:20\u20135:40<\/div><\/td>\r\n<td>An Optimization Approach to Local Graph Partitioning<\/td>\r\n<td>Lorenzo Orrecchia<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">5:40\u20136:00<\/div><\/td>\r\n<td>Erasure-Resilient Property Testing<\/td>\r\n<td>Sofya Raskhodnikova<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<h2>Day 2 | Saturday, October 15<\/h2>\r\n<table class=\"msr-table-schedule\">\r\n<thead class=\"thead\">\r\n<tr class=\"tr\">\r\n<th class=\"th\"><span style=\"font-weight: normal\">Time<\/span><\/th>\r\n<th class=\"th\"><span style=\"font-weight: normal\">Session<\/span><\/th>\r\n<th class=\"th\"><span style=\"font-weight: normal\">Speaker<\/span><\/th>\r\n<\/tr>\r\n<\/thead>\r\n<tbody class=\"tbody\">\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">8:30\u20139:00<\/div><\/td>\r\n<td>Registration and Breakfast<\/td>\r\n<td><\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">9:00\u20139:40<\/div><\/td>\r\n<td>Improved Distributed Local Graph Algorithms<\/td>\r\n<td>Mohsen Ghaffari<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">9:40\u201310:00<\/div><\/td>\r\n<td>\r\n<div class=\"msr-table-schedule-cell\">Non-Local Probes Do Not Help with Many Graph Problems<\/div><\/td>\r\n<td>Moti Medina<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">10:00\u201310:20<\/div><\/td>\r\n<td>\r\n<div class=\"msr-table-schedule-cell\">Local Conflict Coloring<\/div><\/td>\r\n<td>Pierre Fraigniaud<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">10:20\u201310:40<\/div><\/td>\r\n<td>\r\n<div class=\"msr-table-schedule-cell\">Designing Local Algorithms with Algorithms<\/div><\/td>\r\n<td>Jukka Suomela<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">10:40\u201311:10<\/div><\/td>\r\n<td>Break<\/td>\r\n<td><\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">11:10\u201311:30<\/div><\/td>\r\n<td>\r\n<div class=\"msr-table-schedule-cell\">Random walks approach in property testing<\/div><\/td>\r\n<td>Artur Czumaj<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">11:30\u201311:50<\/div><\/td>\r\n<td>Approximating the Spectrum of a Graph<\/td>\r\n<td>Christian Sohler<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">11:50\u201312:20<\/div><\/td>\r\n<td>Poster session<\/td>\r\n<td><\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">12:20\u20132:00<\/div><\/td>\r\n<td>\r\n<div class=\"msr-table-schedule-cell\">Lunch + poster session contd<\/div><\/td>\r\n<td><\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">2:00\u20132:20<\/div><\/td>\r\n<td>\r\n<div class=\"msr-table-schedule-cell\">Fast Constrained Submodular Maximization<\/div><\/td>\r\n<td>Amin Karbasi<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">2:20\u20132:40<\/div><\/td>\r\n<td>\r\n<div class=\"msr-table-schedule-cell\">Sublinear Random-Access Generators for Preferential Attachement Graphs<\/div><\/td>\r\n<td>Adi Rosen<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">2:40\u20133:00<\/div><\/td>\r\n<td>\r\n<div class=\"msr-table-schedule-cell\">Robust Learning and the Semi-Verified Model<\/div><\/td>\r\n<td>Greg Valiant<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">3:00\u20133:20<\/div><\/td>\r\n<td>\r\n<div class=\"msr-table-schedule-cell\">Heavy hitters via cluster-preserving clustering<\/div><\/td>\r\n<td>Huy L. Nguyen<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">3:20\u20133:40<\/div><\/td>\r\n<td>Slow inconsistent statistics<\/td>\r\n<td>Jason Morten<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">3:40\u20134:10<\/div><\/td>\r\n<td>Break<\/td>\r\n<td><\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">4:10\u20134:30<\/div><\/td>\r\n<td>Testing K-Monotonicity<\/td>\r\n<td>Elena Grigorescu<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">4:30\u20134:50<\/div><\/td>\r\n<td>HyperHeadTail: a Streaming Algorithm for Estimating the Degree Distribution of Dynamic Multigraphs<\/td>\r\n<td>Kevin Matulef<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">4:50\u20135:10<\/div><\/td>\r\n<td>Computing with Unknown Noise Rate<\/td>\r\n<td>Jared Saia<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">5:10\u20135:30<\/div><\/td>\r\n<td>Concurrent Disjoint Set Union<\/td>\r\n<td>Robert Tarjan<\/td>\r\n<\/tr>\r\n<tr class=\"tr\">\r\n<td class=\"td-1-3\">\r\n<div class=\"msr-table-schedule-cell\">5:30\u20135:50<\/div><\/td>\r\n<td>Locality and Parallelism<\/td>\r\n<td>Krzysztof Onak<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>"},{"id":2,"name":"Abstracts","content":"<h2>Day 1 | Friday, October 14<\/h2>\r\n[accordion]\r\n[panel header=\"The power of locality for network algorithms\"]\r\n<strong>Speaker:<\/strong>\u00a0Christian Borgs\r\n\r\nTBA\r\n[\/panel]\r\n[panel header=\"Latent Space Model (aka Blind Regression)\"]\r\n<strong>Speaker:<\/strong>\u00a0Devavrat Shah\r\n\r\nIn this talk, we shall discuss the Latent Space Model in the context of various modern applications: recommendation systems, crowd-sourcing and demand prediction in retail. We'll briefly discuss the connection between popular heuristic \"collaborative filtering\" and the first-order Taylor's expansion in the context of this model. Time permitting, we'll discuss desiderata of local algorithms in the context of these models.\r\n\r\nBased on joint works with Christina Lee, Dogyoon Song, Jehangir Muhammad and Yehua Li.\r\n[\/panel]\r\n[panel header=\"Global Convergence Rate of Proximal Incremental Aggregated Gradient Methods\"]\r\n<strong>Speaker:<\/strong> Asu Ozdaglar\r\n\r\nWe focus on the problem of minimizing the sum of smooth component functions (where the sum is strongly convex) and a non-smooth convex function, which arises in regularized empirical risk minimization in machine learning and distributed constrained optimization in wireless sensor networks and smart grids. We consider solving this problem using the proximal incremental aggregated gradient (PIAG) method, which at each iteration moves along an aggregated gradient (formed by incrementally updating gradients of component functions according to a deterministic order) and taking a proximal step with respect to the non-smooth function. While the convergence properties of this method with randomized orders (in updating gradients of component functions) have been investigated, this paper, to the best of our knowledge, is the first study that establishes the convergence rate properties of the PIAG method for any deterministic order. In particular, we show that the PIAG algorithm is globally convergent with a linear rate provided that the step size is sufficiently small. We explicitly identify the rate of convergence and the corresponding step size to achieve this convergence rate. Our results improve upon the best known condition number dependence of the convergence rate of the incremental aggregated gradient methods used for minimizing a sum of smooth functions.\r\n\r\nThis is joint work with Denizcan Vanli and Mert Gurbuzbalaban.\r\n[\/panel]\r\n[panel header=\"A short (and partial) survey on Partition Oracles\"]\r\n<strong>Speaker:<\/strong> Dana Ron\r\n\r\nIn this talk I will present the notion of a Partition Oracle, as defined by Hassidim, Kelner, Nguyenn and Onak.\u00a0 I will describe several partition oracles, for various families of graphs, and show how such oracles can be applied to solve a variety of approximation problems in sublinear time.\r\n[\/panel]\r\n[panel header=\"Local Computation Algorithms for High Degree Graphs\"]\r\n<strong>Speaker:<\/strong> Shai Vardi\r\n\r\nLocal Computation Algorithms (abbreviated LCA) is a computational model aimed at problem instances with huge inputs and output. For graph problems, the input graph is accessed using probes, where a probe specifies the ID of a vertex and receives in reply the IDs of its neighbors.\u00a0 Given a local query (e.g., ``is a certain vertex in the vertex cover of the input graph?''), an LCA should compute the corresponding local output (e.g., ``yes'' or ``no'') while making only a small number of probes. The requirement is that all local outputs form a single global solution (e.g., a legal vertex cover).\r\n\r\nIn this talk, I will discuss the possibilities and limitations of LCAs that are required to work on graphs that may have arbitrarily large degrees (possibly linear in $n$) but are limited to a number of probes that is significantly smaller than the minimal degree. \u00a0I will present negative and positive results: I will show a probe complexity lower bounds for approximating minimum vertex cover and finding a maximal matching, and an algorithm for finding an approximate maximum matching on high-girth regular graphs that uses a constant number of probes.\r\n[\/panel]\r\n[panel header=\"Testing Graph Properties with a Polynomial Query Complexity\"]\r\n<strong>Speaker:<\/strong> Asaf Shapira\r\n\r\nAbout 10 years ago, I proved with N. Alon that every hereditary graph property can be tested\u00a0with a constant number of queries. Unfortunately, the constants involved were enormous. A natural question is therefore to decide if for natural graph properties one can get a polynomial bound.\r\n\r\nOur first result in this work is a very simple sufficient combinatorial criteria which guarantees that a graph property can be tested with a polynomial number of queries. This allows us to recover (almost) all previous results in the area, as well as obtain some new ones.\r\n\r\nOur second main result is a very simple sufficient combinatorial criteria which guarantees that a graph\u00a0property cannot be tested with a polynomial number of queries. This allows us to recover (almost) all previous results in the area, as well as obtain some new ones.\r\n\r\nJoint work with L. Gishboliner.\r\n[\/panel]\r\n[panel header=\"A Local Algorithm for Constructing Spanners in Minor-Free Graphs\"]\r\n<strong>Speaker:<\/strong> Reut Levi\r\n\r\nConstructing a spanning tree of a graph is one of the most basic tasks in graph theory. We consider this problem in the setting of local algorithms: one wants to quickly determine whether a given edge $e$ is in a specific spanning tree, without computing the whole spanning tree, but rather by inspecting the local neighborhood of $e$. The challenge is to maintain consistency. That is, to answer queries about different edges according to the {\\em same\\\/} spanning tree. Since it is known that this problem cannot be solved without essentially viewing all the graph, we consider the relaxed version\u00a0of finding a spanning subgraph with $(1+\\eps)n$ edges instead of $n-1$ edges (where $n$ is the number of vertices and $\\eps$ is a given approximation\/sparsity parameter).\u00a0 It is known that this relaxed problem requires inspecting $\\Omesdfsdf\\sqrt{n})$ edges in general graphs (for any constant $\\eps$),\u00a0which motivates the study of natural restricted families of graphs.\u00a0 One such family is the family of graphs with an excluded minor (which in particular includes planar graphs).\u00a0 For this family there is an algorithm that achieves constant success probability, and inspects $(d\/\\eps)^{\\poly(h)\\log(1\/\\eps)}$ edges (for each edge it is queried on), where $d$ is the maximum degree in the graph and $h$ is the size of the excluded minor. The distances between pairs of vertices in the spanning subgraph $G'$ are at most a factor of $\\poly(d, 1\/\\eps, h)$ larger than in $G$.\r\n\r\nIn this work, we show that for an input graph that is $H$-minor free for any $H$ of size $h$, this task can be performed by inspecting only $\\poly(d, 1\/\\eps, h)$ edges in $G$. The distances between pairs of vertices in the spanning subgraph $G'$ are at most a factor of $\\tilde{O}(h\\log(d)\/\\eps)$ larger than in $G$.\u00a0 Furthermore, the error probability of the new algorithm is significantly improved to $\\Theta(1\/n)$.\r\n\r\nThis algorithm can also be easily adapted to yield an efficient algorithm for the distributed (message passing) setting.\r\n\r\nJoint work with Dana Ron and Ronitt Rubinfeld.\r\n[\/panel]\r\n[panel header=\"Local to global amplification: the block model vignette\"]\r\n<strong>Speaker:<\/strong> Emmanuel Abbe\r\n\r\nI will attempt to describe a framework in which variables need to be recovered from their local noisy interactions, and for which a single phase transition takes place between the computationally solvable and information-theoretically unsolvable regimes. The idea is based on amplifying local thresholds to global ones. Our study-case will be exact recovery in the stochastic block model. We will also discuss how this breaks down for the detection problem, with the emergence of computational gaps.\r\n[\/panel]\r\n[panel header=\"On Limits of Local Algorithms for Solving Random Constraint Satisfaction Problems\"]\r\n<strong>Speaker:<\/strong> David Gamarnik\r\n\r\nThe talk will discuss algorithms for finding solutions of randomly generated constraint satisfaction problem such random K-SAT problem or finding a largest independent set of a graph. We establish a fundamental barrier on the power of local algorithms to solve such problems, despite some conjectures put forward in the past. In particular, we refute a conjecture regarding the power of so-called i.i.d factors to find nearly largest independent sets in random regular graphs. Similarly, we show that a broad class of sequential local algorithms are incapable of finding satisfying assignments for a random NAE-K-SAT problem, above a certain asymptotic threshold, below which even simple algorithms succeed with high probability. Our negative results exploit fascinating geometry of feasible solutions of random constraint satisfaction problems, which was first predicted by physicists heuristically and now confirmed by rigorous methods. According to this picture, the solution space exhibits a clustering property whereby the feasible solutions tend to cluster according to the underlying Hamming distance.\u00a0 We show that success of local algorithms would imply violation of such a clustering property thus leading to a contradiction.\r\n\r\nJoint work with Madhu Sudan, Microsoft Research.\r\n[\/panel]\r\n[panel header=\"Locality in Coding Theory\"]\r\n<strong>Speaker:<\/strong> Madhu Sudan\r\n\r\nI will survey the concept of locality in coding theory, including the notions of locally decodable codes, locally testable codes, local reconstruction codes etc. Several of these notions are accompanied by strikingly strong constructions, and a few have even turned to be valuable (measured in $$$s).\r\n[\/panel]\r\n[panel header=\"Local algorithms, message passing and the hidden clique problem\"]\r\n<strong>Speaker:<\/strong> Yash Deshpande\r\n\r\nThe hidden clique problem posits to find a large clique, or completely connected subgraph, in an otherwise random Erdos-Renyi graph. This problem was originally posed in theoretical computer science as an average case version of the maximum clique problem. More recently, it has seen intense interest from a variety of communities as a statistical estimation problem wherein computationally efficient algorithms are far from achieving known statistically optimal thresholds. I will discuss local algorithms in the context of the hidden clique problem and generalizations, which form the basis of the best-known algorithms for this setting.\r\n\r\nThis is joint work with Andrea Montanari.\r\n[\/panel]\r\n[panel header=\"A few perspectives on local algorithms for sparse graphs\"]\r\n<strong>Speaker:<\/strong> Elchanan Mossel\r\n\r\nI will give a few different perspectives on local algorithms in sparse graphs coming from inference and optimization on random graphs, Bayesian economics on sparse graphs and deep learning.\r\n[\/panel]\r\n[panel header=\"Sublinear Time Algorithms via Optimization\"]\r\n<strong>Speaker:<\/strong> Zheyuan Allen-Zhu\r\n\r\nIn this talk, I will discuss how to use optimization to obtain sublinear algorithms, as well as an interpolation between sublinear-time and linear-time algorithms using optimization insights and acceleration techniques.\r\n[\/panel]\r\n[panel header=\"An Optimization Approach to Local Graph Partitioning\"]\r\n<strong>Speaker:<\/strong> Lorenzo Orrecchia\r\n\r\nLocal clustering algorithms find a good approximation to a local sparse cut around a seed node while running in nearly-linear time in the size of the output. The main idea behind many of these algorithms is of spectral nature. The algorithms simulate a random walk starting at the seed node. The target local cut will limit the mixing, allowing the walk to both approximate the conductance of the cut and maintain the locality of the algorithm. In this talk, I will consider an optimization interpretation of these algorithms. Besides giving us a more principle framework to think about random walks for local clustering, the optimization view will also allow us to discuss non-spectral analogues of these algorithms and introduce local maximum flow computations. I will show how this novel local primitive can be combined with random walks to yield improved guarantees for local clustering. Finally, I will discuss a\u00a0number of open questions about localizing SDP-based global approximation algorithms for sparsest cut using local random walks and local maximum flows.\r\n[\/panel]\r\n[panel header=\"Erasure-Resilient Property Testing\"]\r\n<strong>Speaker:<\/strong> Sofya Raskhodnikova\r\n\r\nProperty testers form an important class of sublinear algorithms. In the\u00a0standard property testing model, an algorithm accesses the input function via\u00a0an oracle that returns function values at all queried domain points. In many\u00a0realistic situations, the oracle may be unable to reveal the function values at\u00a0some domain points due to privacy concerns, or when some of the values get\u00a0erased by mistake or by an adversary.\r\n\r\nWe initiate a study of property testers that are resilient to the presence of\u00a0adversarially erased function values. An alpha-erasure-resilient epsilon-tester\u00a0for a property P is given parameters alpha, epsilon in (0,1), along with oracle\u00a0access to a function f such that at most an alpha fraction of the function\u00a0values have been erased. The tester does not know whether a point is erased\u00a0unless it queries that point. The tester has to accept with high probability if\u00a0there is a way to assign values to the erased points such that the resulting\u00a0function satisfies P. It has to reject with high probability if, for all\u00a0assignments of values to the erased points, the resulting function has to be\u00a0changed in at least an epsilon-fraction of the nonerased domain points to\u00a0satisfy P.\r\n\r\nWe design erasure-resilient property testers for a large class of properties.\u00a0For some properties, it is possible to obtain erasure-resilient testers by\u00a0using standard testers as a black box. But there are more challenging\u00a0properties for which all known testers rely on querying a specific point. If\u00a0this point is erased, all these testers break. We give efficient\u00a0erasure-resilient testers for several classes of such properties including\u00a0monotonicity, the Lipschitz property, and convexity. Finally, we describe a\u00a0property that can be epsilon-tested with O(1\/epsilon) queries in the standard\u00a0model, whereas testing it in the erasure-resilient model requires number of\u00a0queries polynomial in the input size.\r\n\r\nJoint work with Kashyap Dixit, Abhradeep Thakurta, and Nithin Varma.\r\n[\/panel]\r\n[\/accordion]\r\n<h2>Day 2 | Saturday, October 15<\/h2>\r\n[accordion]\r\n[panel header=\"Improved Distributed Local Graph Algorithms\"]\r\n<strong>Speaker:<\/strong> Mohsen Ghaffari\r\n\r\nTBA\r\n[\/panel]\r\n[panel header=\"Non-Local Probes Do Not Help with Many Graph Problems\"]\r\n<strong>Speaker:<\/strong>\u00a0Moti Medina\r\n\r\nThis work bridges the gap between distributed and centralised models of computing in the context of sublinear-time graph algorithms.\u00a0 A priori, typical centralised models of computing\u00a0 (e.g., parallel decision trees or centralised local algorithms) seem to be much more powerful than distributed message-passing algorithms: centralised algorithms can directly probe any part of the input, while in distributed algorithms nodes can only communicate with their immediate neighbours. We show that for a large class of graph problems, this extra freedom does not help centralised algorithms at all: efficient\u00a0stateless deterministic centralised local algorithms can be simulated with efficient distributed message-passing algorithms. In particular, this enables us to transfer existing lower bound results from distributed algorithms to centralised local algorithms.\r\n\r\nJoint work with Mika Goos, Juho Hirvonen, Reut Levi, and Jukka Suomela.\r\n[\/panel]\r\n[panel header=\"Local Conflict Coloring\"]\r\n<strong>Speaker:<\/strong>\u00a0Pierre Fraigniaud\r\n\r\nLocally finding a solution to \\emph{symmetry-breaking} tasks such as vertex-coloring, edge-coloring, maximal matching, maximal independent set, etc., is a long-standing challenge in \\emph{distributed network} computing. More recently, it has also become a challenge in the framework of \\emph{centralized local} computation. We introduce \\emph{conflict coloring} as a general symmetry-breaking task that includes all the aforementioned tasks as specific instantiations --- conflict coloring includes all \\emph{locally checkable labeling}~tasks from [Naor\\ \\&amp;\\ Stockmeyer, STOC 1993]. Conflict coloring is characterized by two parameters $l$ and $d$, where the former measures the amount of freedom given to the nodes for selecting their colors, and the latter measures the number of constraints which colors of adjacent nodes are subject to. We show that, in the standard \\LOCAL model for distributed network computing, if $l\/d &gt; \\Delta$, then conflict coloring can be solved in $\\Otilde(\\sqrt{\\Delta})+\\log^*n$ rounds in $n$-node graphs with maximum degree~$\\Delta$, where $\\Otilde$ ignores the polylog factors in $\\Delta$. The dependency in~$n$ is optimal, as a consequence of the $\\Omesdfsdf\\log^*n)$ lower bound by [Linial, SIAM J. Comp. 1992] for $(\\Delta+1)$-coloring. An important special case of our\u00a0 result is a significant improvement over the best known algorithm for\u00a0 distributed $(\\Delta+1)$-coloring due to [Barenboim, PODC 2015], which required $\\Otilde(\\Delta^{3\/4})+\\log^*n$ rounds. Improvements for other variants of coloring, including\u00a0 $(\\Delta+1)$-list-coloring, $(2\\Delta-1)$-edge-coloring, coloring with forbidden color distances, etc., also follow from our general result on conflict coloring. Likewise, in the framework of centralized local computation algorithms (LCAs), our general result yields an LCA which requires a smaller number of probes than the previously best known algorithm for vertex-coloring, and works for a wide range of coloring problems.\r\n\r\nJoint work with Marc Heinrich and Adrian Kosowski.\r\n[\/panel]\r\n[panel header=\"Designing Local Algorithms with Algorithms\"]\r\n<strong>Speaker:<\/strong>\u00a0Jukka Suomela\r\n\r\nIn this talk I will show that there are settings in which the design of local distributed algorithms can be automated. In essence, we can synthesize asymptotically optimal local algorithms for solving nontrivial graph problems.\r\n\r\nI will focus on LCL problems (locally checkable labellings). These are problems in which valid solutions can be detected by checking the constant-radius neighborhoods of all nodes. Examples of such problems include maximal independent sets, maximal matchings, vertex coloring, and edge coloring.\r\n\r\nWe will study LCL problems on 2-dimensional grids (more precisely, toroidal n x n grids with consistent orientations and unique identifiers). In this setting, each LCL problem has a complexity of precisely O(1), Theta(log^* n), or Theta(n) rounds. There are no problems with an \"intermediate complexity\" of e.g. Theta(log n); all problems are either local or global.\r\n\r\nThe bad news is that it is undecidable to tell if a given LCL problem is local or global. However, we show that this is the only obstacle for algorithm synthesis: if we are told (or make a lucky guess) that the problem is local, then we can use a computer program to find an O(log^* n)-round algorithm for solving it! Furthermore, this is not merely a theoretical construction: we have successfully used computers to design local algorithms for numerous LCL problems, many of which do not have any human-designed algorithms. Perhaps the most interesting case is a computer-designed local algorithm for 4-coloring, complemented with a human-designed proof that shows that 3-coloring cannot be solved locally.\r\n\r\nThis is joint work with Sebastian Brandt, Orr Fischer, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempi\u00e4inen, Christopher Purcell, Joel Rybicki, Patric \u00d6sterg\u00e5rd, and Przemys\u0142aw Uzna\u0144ski.\r\n[\/panel]\r\n[panel header=\"Random walks approach in property testing\"]\r\n<strong>Speaker:<\/strong>\u00a0Artur Czumaj\r\n\r\nI'll survey some of the recent results in graph property testing that rely on the random walk approach, and then I'll briefly discuss some of the challenges of this approach.\r\n[\/panel]\r\n[panel header=\"Approximating the Spectrum of a Graph\"]\r\n<strong>Speaker:<\/strong> Christian Sohler\r\n\r\nThe spectrum of a graph $G=(V,E)$ with adjacency matrix $A$ consists of the eigenvalues of the normalized Laplacian of $L= I - D^{-1\/2} A D^{-1\/2}$. We study the problem of approximating the spectrum $\\lambda = (\\lambda_1,\\dots,\\lambda_{|V|})$, $0 \\le \\lambda_1,\\le \\dots, \\le \\lambda_{|V|}\\le 2$ of $G$ when\u00a0 the algorithm can query random vertices of $G$ and for a given vertex a random neighbor in $O(1)$ time.\u00a0 We present a sublinear time algorithm that computes a succinct representation of an approximation $\\widetilde \\lambda = (\\widetilde \\lambda_1,\\dots,\\widetilde \\lambda_{|V|})$, $0 \\le \\widetilde\\lambda_1,\\le \\dots, \\le \\widetilde \\lambda_{|V|}\\le 2$ such that $\\|\\widetilde \\lambda - \\lambda\\|_1 \\le \\epsilon n$. Our algorithm has query complexity and running time $exp(O(1\/\\eps))$, independent of $|V|$.\r\n\r\nWe then study the implications of our algorithm to property testing in the bounded degree graph model.\r\n\r\nJoint work with David Cohen-Steiner and Gregory Valiant.\r\n[\/panel]\r\n[panel header=\"Poster session\"]\r\n<ul>\r\n \t<li>Maryam Aliakbarpour<\/li>\r\n \t<li>Alkida Balli: Local Distributed Verification<\/li>\r\n \t<li>Clement Canonne<\/li>\r\n \t<li>Laurent Feuilloley<\/li>\r\n \t<li>Meiram Murzabulatov: Tolerant Testers of Image Properties<\/li>\r\n \t<li>Ali Vakilian<\/li>\r\n \t<li>Nithin Varma: Erasure-resilient property testing<\/li>\r\n \t<li>Gandikota Venkata: Local Testing for Membership in Lattices<\/li>\r\n<\/ul>\r\n[\/panel]\r\n[panel header=\"Fast Constrained Submodular Maximization\"]\r\n<strong>Speaker:\u00a0<\/strong>Amin Karbasi\r\n\r\nCan we summarize multi-category data based on user preferences in a scalable manner? Many utility functions used for data summarization satisfy submodularity, a natural diminishing returns property. We cast personalized data summarization as an instance of a general submodular maximization problem subject to multiple constraints. We develop the first practical and FAst coNsTrained submOdular Maximization algorithm, FANTOM, with strong theoretical guarantees. FANTOM maximizes a submodular function (not necessarily monotone) subject to the intersection of a p-system and l knapsacks constrains. It achieves a (p+1)(2p+2l+1)\/p approximation guarantee with only O(nrp log(n)) query complexity (n and r indicate the size of the ground set and the size of the largest feasible solution, respectively). We then show how we can use FANTOM for personalized data summarization. In particular, a p-system can model different aspects of data, such as categories or time stamps, from which the users choose. In addition, knapsacks encode users\u2019 constraints including budget or time. In our set of experiments, we consider several concrete applications: movie recommendation over 11K movies, personalized image summarization with 10K images, and revenue maximization on the YouTube social networks with 5000 communities. We observe that FANTOM constantly provides the highest utility against all the baselines.\r\n[\/panel]\r\n\r\n[panel header=\"Sublinear Random-Access Generators for Preferential Attachement Graphs\"]\r\n<strong>Speaker:\u00a0<\/strong>Adi Rosen\r\n\r\nWe consider the problem of giving to a user access to a graph which is sampled according to a certain probability distribution, and are interested in the time, space\r\nand randomness complexities of such samplers. We are specifically interested in the\u00a0case when the distribution is defined using a sequentially-evolving graph model.\r\n\r\nIn the standard approach the whole graph is sampled according to the probability distribution, then stored, and later the user can issue certain queries, e.g., asking for the adjacency list of a given node. This however may require prohibitive amounts of time, space and random bits, especially when the size of the graph is big and only few queries are actually issued. Instead, we propose to generate the graph on the fly,\u00a0in response to queries, while being able to respect the probability distribution defined by the sequential model.\r\n\r\nWe focus on the Barabasi-Albert Preferential Attachement model (BA-graphs),\u00a0and give on-the-fly generation algorithms with the following properties:\u00a0Let n denote the number of nodes in the underlying sampled graph;\u00a0with probability 1-1\/poly(n), each query is answered in polylog(n) time, and for each query both the increase in space, and the amount of random bits used are polylog(n). The answers that the user gets to its queries are (with probability 1)\u00a0distributed according to the probability distribution which is the projection, on the queried\u00a0nodes, of the original distribution on graphs.\r\n\r\nJoint work with Guy Even, Reut Levi, and Moti Medina.\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Robust Learning and the Semi-Verified Model\"]\r\n\r\n<strong>Speaker:<\/strong> Greg Valiant\r\n\r\nHow can the availability of a very small amount of high-quality or trusted data enable the efficient extraction of the information contained in a large but less-trusted dataset?\u00a0 We investigate this\u00a0question via the introduction of a new model for studying robust estimation, learning, and optimization, which we term the \"semi-verified\" model.\u00a0 In this model, we assume a large dataset of which a subset consists of points drawn from the distribution of interest, and make no assumptions on the remaining points---they could be well-behaved, extremely biased, or even adversarially generated as a function of the remaining points.\u00a0 Additionally we assume a much smaller (typically constant-sized) set of \"verified\" or trusted data points that have been drawn from the distribution of interest.\u00a0\u00a0 We present several results in this model, for a large class of mathematically clean and practically relevant robust estimation and learning tasks.\u00a0 These results include both local and non-local algorithms that achieve information theoretic limits for two different parameter regimes.\r\n\r\nThe talk is based on joint works with Jacob Steinhardt and Moses Charikar, and with Michela Meister.\r\n[\/panel]\r\n[panel header=\"Heavy hitters via cluster-preserving clustering\"]\r\n<strong>Speaker:<\/strong> Huy L. Nguyen\r\n\r\nIn the turnstile L_p heavy hitters problem with parameter eps, one must maintain a high-dimensional vector x in R^n subject to updates of the form update(i, Delta), which increases x_i by Delta, where i is in [n], and Delta is an integer. Upon receiving a query, the goal is to report every ``heavy hitter'' i in[n] with |x_i| &gt;= eps*|x|_p as part of a list L, which is a subset of [n] of size O(1\/\\eps^p), i.e. proportional to the maximum possible number of heavy hitters. In fact we solve the stronger tail version, in which L should include every i such that |x_i| &gt;= \\eps |x_{proj{1\/eps^p}}|_p and |x_i| &gt; 0, where x_{proj{k}} denotes the vector obtained by zeroing out the largest k entries of x in magnitude.\r\n\r\nWe provide a new algorithm, which in the most general turnstile model achieves optimal O(\\eps^{-p}\\log n) space, O(\\log n) update time, and fast O(\\eps^{-p}\\poly(\\log n)) query time, providing correctness whp. Our main innovation is an efficient reduction from the heavy hitters to a clustering problem in which each heavy hitter is encoded as some form of noisy spectral cluster in a much bigger graph, and the goal is to identify every cluster. Since every heavy hitter must be found, correctness requires that every cluster be found. We thus need a ``cluster-preserving clustering'' algorithm, that partitions the graph into clusters with the promise of not destroying any original cluster. To do this we first apply standard spectral graph partitioning, and then we use some novel combinatorial techniques to modify the cuts obtained so as to make sure that the original clusters are sufficiently preserved.\u00a0 Our cluster-preserving clustering may be of broader interest much beyond heavy hitters.\r\n\r\nJoint work with Kasper Green Larsen, Jelani Nelson, and Mikkel Thorup.\r\n[\/panel]\r\n[panel header=\"Slow inconsistent statistics\"]\r\n<strong>Speaker:<\/strong> Jason Morten\r\n\r\nTraditionally categorical data analysis (e.g. generalized linear models) works with simple, flat datasets akin to a single table in a database with no missing data. What if we have a distributed database with many partial local tables, and data is streaming in too fast for the local tables ever to be globally consistent? I'll discuss how some hints from physics (e.g. quantum nonlocality) could help define\u00a0sensible models in this scenario.\r\n\r\n[\/panel]\r\n[panel header=\"Testing K-Monotonicity\"]\r\n<strong>Speaker:<\/strong> Elena Grigorescu\r\n\r\nIn this work we initiate the study of Boolean k-monotone functions in the Property Testing model.\u00a0 K-monotone functions defined over a finite poset domain D\u00a0 alternate between the values 0 and 1 at most k times on any ascending chain in D. Hence, k-monotone functions are natural generalizations of the classical monotone functions, which are the 1-monotone functions. This work is motivated by the recent interest in k-monotone functions in the context of circuit complexity and learning theory, and by the central role that monotonicity testing plays in the context of property testing.\r\n\r\nI will present our results on testing k-monotonicity on the hypercube and hypergrid domains, outline some connections with other problems from the literature, and discuss a few important open questions.\r\n\r\nJoint work with Clement Canonne, Siyao Guo, Akash Kumar, Karl Wimmer.\r\n\r\n[\/panel]\r\n[panel header=\"HyperHeadTail: a Streaming Algorithm for Estimating the Degree Distribution of Dynamic Multigraphs\"]\r\n<strong>Speaker:<\/strong> Kevin Matulef\r\n\r\nWe present HyperHeadTail, a new streaming algorithm for estimating the degree distribution of a graph from a stream of edges using very little space. Our algorithm builds upon the HeadTail algorithm of Simpson, Comandur, and McGregor (2015), but extends it to handle repeat edges and sliding time windows, making it suitable for application to real-world streams such as those generated by network traffic or other communications networks. We implement HyperHeadTail, and demonstrate its utility on both synthetic and real-world data sets, showing that it effectively captures the degree distribution, with space requirements equal to only a small fraction of the graph.\r\n[\/panel]\r\n[panel header=\"Computing with Unknown Noise Rate\"]\r\n<strong>Speaker:<\/strong> Jared Saia\r\n\r\nHow can we compute over a noisy channel? Say Alice and Bob want to run a distributed algorithm, but can only communicate over a channel where some number of bits may be flipped.\u00a0 What is the smallest number of bits they must send in order to obtain the correct output, with\u00a0high probability? This general problem is called Interactive Communication (IC).\r\n\r\nSeveral results in IC take a protocol requiring L bits of noise-free communication, and make it robust over a channel with adversarial noise. In a recent result, Haeupler described an algorithm that sends\u00a0a number of bits that is conjectured to be near optimal. However, his algorithm critically requires a priori knowledge of the number of bits that will be flipped by the adversary.\r\n\r\nIn this talk, we describe an algorithm requiring no such knowledge. To achieve this result, our algorithm must make local decisions about communication redundancy, without access to global information about past and future noise rates.\u00a0 If an adversary flips T bits, our algorithm sends L + soft-O (T + \u221a (LT))\u00a0bits in expectation and succeeds with high probability in L. Assuming a conjectured lower bound by Haeupler, our result is optimal up to logarithmic factors.\r\n[\/panel]\r\n[panel header=\"Concurrent Disjoint Set Union\"]\r\n<strong>Speaker:<\/strong> Robert Tarjan\r\n\r\nThe disjoint set union problem is a classical problem in data structures with a simple and efficient sequential solution that has a notoriously complicated analysis. One application is to find strongly connected components in huge, implicitly defined graphs arising in model checking. In this application, the use of multiprocessors has the potential to produce significant speedups. We explore this possibility. We devise and analyze concurrent versions of standard sequential algorithms that use single and double compare-and-swap primitives for synchronization, making them wait-free. We obtain work bounds that grow logarithmically with the number of processors, suggesting the possibility of significant speedup in practice. This is joint work with Siddhartha Jayanti, an undergraduate at Princeton.\r\n[\/panel]\r\n\r\n[panel header=\"Locality and Parallelism\"]\r\n\r\n<strong>Speaker:<\/strong>\u00a0Krzysztof Onak\r\n\r\nThe last decade has seen an unprecedented success of massive parallel\u00a0and distributed systems such as MapReduce, Spark, and Hadoop. Their\u00a0computation consists of a small number of rounds in which machines first\u00a0process local data and then exchange information. After introducing the\u00a0computational model in more detail, I will discuss how its complexity\u00a0relates to the notion of locality for graph problems. On the one hand,\u00a0some more standard local algorithms can be simulated efficiently, taking\u00a0additionally advantage of the global data exchange. On the other hand,\u00a0graph exploration seems to be hindered similarly to the streaming model.\u00a0Many interesting questions remain open in this relatively young area of\u00a0research.\r\n\r\n[\/panel]\r\n[\/accordion]"},{"id":3,"name":"Attendee info","content":"<strong>Hospitality Notice for University and Government Employees:<\/strong> Microsoft Research is providing hospitality at this event. Please consult with your institution to determine whether you can accept meals and other hospitality under your institution's ethics rules and any other laws that might apply.\r\n<h2>Hotel Accommodations<\/h2>\r\nTake advantage of the hotel room block for this event and book at the <a href=\"https:\/\/aws.passkey.com\/event\/15988456\/owner\/371\/home\" target=\"_blank\">Hyatt Regency Cambridge<\/a> by September 22.\r\n<h2>Arrival Guidance<\/h2>\r\n<strong>Friday, October 14:<\/strong>\r\n\r\n<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/lab\/microsoft-research-new-england\/\" target=\"_blank\">Microsoft Research New England<\/a>\r\n1st floor, 1 Memorial Drive\r\nCambridge, MA 02142\r\n\r\nUpon arrival, be prepared to show a picture ID and sign the Building Visitor Log when approaching the Lobby Floor Security Desk.\u00a0Alert them to the name of the event you are attending and ask them to direct you to the appropriate floor.\u00a0The talks will be held the first floor.\r\n\r\n<strong>Saturday, October\u00a015:<\/strong>\r\n\r\n<a href=\"http:\/\/web.mit.edu\/\" target=\"_blank\">Massachusetts Institute of Technology<\/a>\r\nKiva Seminar Room, 32-G449,\u00a032 Vassar Street\r\nCambridge, MA 02139\r\n\r\nEnter Building 32 at the front entrance and proceed straight ahead; there will be elevators to the right.\u00a0Take the elevators to the 4th floor; exit to the left and then turn right at the end of the elevator bank.\u00a0At the end of the short corridor bear to the left and continue around the R&amp;D Dining Room.\u00a0CSAIL Headquarters will be to your left and the Patil\/Kiva Seminar Room will be straight ahead."}],"msr_startdate":"2016-10-14","msr_enddate":"2016-10-15","msr_event_time":"","msr_location":"Cambridge, MA, USA","msr_event_link":"","msr_event_recording_link":"","msr_startdate_formatted":"October 14, 2016","msr_register_text":"Watch now","msr_cta_link":"","msr_cta_text":"","msr_cta_bi_name":"","featured_image_thumbnail":null,"event_excerpt":"This workshop was aimed at fostering dialogue and cross-pollination of ideas between the various communities studying local algorithms. To this end, the workshop featured longer talks that, in part, surveyed approaches by various communities, as well as short, focused talks on recent, exciting results.","msr_research_lab":[199563],"related-researchers":[{"type":"user_nicename","value":"borgs","display_name":"Christian Borgs","author_link":"<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/borgs\/\" aria-label=\"Visit the profile page for Christian Borgs\">Christian Borgs<\/a>","is_active":false,"user_id":31278,"last_first":"Borgs, Christian","people_section":0,"alias":"borgs"},{"type":"user_nicename","value":"jchayes","display_name":"Jennifer Chayes","author_link":"<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/jchayes\/\" aria-label=\"Visit the profile page for Jennifer Chayes\">Jennifer Chayes<\/a>","is_active":false,"user_id":32200,"last_first":"Chayes, Jennifer","people_section":0,"alias":"jchayes"}],"msr_impact_theme":[],"related-academic-programs":[],"related-groups":[],"related-projects":[],"related-opportunities":[],"related-publications":[],"related-videos":[],"related-posts":[],"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event\/279911"}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-event"}],"version-history":[{"count":1,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event\/279911\/revisions"}],"predecessor-version":[{"id":317219,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event\/279911\/revisions\/317219"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=279911"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=279911"},{"taxonomy":"msr-region","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-region?post=279911"},{"taxonomy":"msr-event-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event-type?post=279911"},{"taxonomy":"msr-video-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video-type?post=279911"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=279911"},{"taxonomy":"msr-program-audience","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-program-audience?post=279911"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=279911"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=279911"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}