Lesson 16: Algorithmic Lower Bounds by Mohammad Hajiaghayi: Massively Parallel Comput Lower Bounds 1
In this session guest lecturer Jan Olkowski talks about the Massively Parallel Computation (MPC) model and their lower bounds. The MPC model involves distributing data across multiple computers, each with limited memory, engaging in private communications, and sharing results over several rounds. Jan introduces the concept of the shuffle model, emphasizing its role in understanding the properties of functions that can be computed in this context. The lecture explores the theoretical model for lower bounds, focusing on shuffle circuits and their applications in dealing with big data, following a prior discussion on streaming models. Jan delves into the formal definition of the MPC model, highlighting parameters such as the number of machines and the memory of a single machine, and discusses the challenges and constraints associated with MPC computations. The lecture concludes with an invitation for questions and a promise to further explore the computability of functions in the shuffle model in the next session.
#MPC, #ShuffleModel, #LowerBounds, #BigData, #ComputationalModels, #ParallelComputation, #Algorithms, #DataDistribution,#CommunicationComplexity,#TheoreticalModel, #ImpossibilityResults#ComputationalComplexity, #TheoreticalComputerScience, #AlgorithmicLowerBounds
All handwritten lecture notes for this course are available through the website of the instructor
at http://www.cs.umd.edu/~hajiagha/ALB19... (Just click on the "Algorithmic Lower Bounds: Fun with Hardness Proofs" course from the website).
The BOOK for the course entitled "Computational Intractability: A Guide to Algorithmic Lower Bounds" by Demaine, Gasarch, and Hajiaghayi is freely available at https://hardness.mit.edu/
