This workshop will bring together researchers in theoretical foundations of parallel and distributed computing for a discussion of recent progress and directions for future research in modeling and algorithms for modern massively parallel computational systems (such as Hadoop/MapReduce/Storm/Spark, etc.) The workshop will be primarily focused on theoretical aspects of such systems, including a comprehensive overview of their power and limitations. It will bring an uninitiated researcher from the STOC and SPAA community up to speed with the key results and challenges in the area, while also illustrating connections with other established areas in massive data processing (streaming, sublinear algorithms, etc.) We also expect this workshop to be of interest to a broader audience and in particular to researchers working in related areas where algorithms for big data are known to be impactful: machine learning, optimization, image and streaming data processing, etc.

A central goal of theoretical computer science is the classification of computational problems according to their complexity. The theory of NP-hardness has been successful in identifying problems that are unlikely to be solvable in time that is polynomial in the size of the input. Conversely, for many problems of practical interest, the field has developed intriguingly fast polynomial time solutions. However, improving the running times of many of these algorithms has been a longstanding open problem, with little to no progress. It is thus completely plausible that these algorithms are optimal. Showing that this is indeed the case would be a great accomplishment of the theory of algorithms. Unfortunately, unconditional lower bounds seem hard to obtain. Instead, an alternative approach for proving hardness of problems in P is to identify plausible complexity-theoretic conjectures and show that the currently best algorithms for the problems of interest are optimal if one assumes these conjectures. Such popular conjectures include the (Strong) Exponential Time Hypothesis (that concerns the complexity of CNF-SAT), the conjecture that all-pairs shortest paths (APSP) requires essentially cubic time, or that 3SUM requires essentially quadratic time. The goal of the tutorial is to expose the general theory community to the recent growing body of conditional lower bounds for a variety of problems in diverse areas, such as graph optimization, string matching, geometry, and dynamic data structures, and to the attempts at unifying and/or refuting the popular conjectures.

High-dimensional sampling has applications in many fields, and efficient algorithms for sampling and integration have become part of the standard algorithmic toolkit. The past three decades have witnessed remarkable improvements in the worst-case complexity of these problems and resulted in a rich set of algorithmic and analytic tools. This tutorial will be an in-depth exposition of the state-of-the-art, beginning with an introduction to high-dimensional geometry and algorithmic applications of sampling (Part I), a detailed discussion of closely related developments and conjectures in asymptotic convex geometry (Part II), an interlude with MATLAB experiments, then continuing with the analysis of Markov chains based in part on geometric isoperimetry, and concluding with a discussion of the many open questions and research directions highlighted by recent progress (Part III). The tutorial will assume only a basic knowledge of linear algebra, probability and algorithms.

Monday, June 15