Mohammad Hajiaghayi<p>In our ongoing effort to put my courses online, we are continuing lectures for the Algorithmic Lower Bound Course. </p><p>Lesson 16: Algorithmic Lower Bounds by Mohammad Hajiaghayi: Massively Parallel Computation Lower Bounds 1</p><p><a href="https://youtu.be/ihfCWHmz1pc" rel="nofollow noopener" translate="no" target="_blank"><span class="invisible">https://</span><span class="">youtu.be/ihfCWHmz1pc</span><span class="invisible"></span></a></p><p>Lesson 17: Algorithmic Lower Bounds by Mohammad Hajiaghayi: Massively Parallel Computation Lower Bounds 2</p><p><a href="https://youtu.be/GYeiOHP9GIA" rel="nofollow noopener" translate="no" target="_blank"><span class="invisible">https://</span><span class="">youtu.be/GYeiOHP9GIA</span><span class="invisible"></span></a></p><p>Feel free to subscribe to our YouTube channel @hajiaghayi for upcoming lessons premiering every Wednesday at 7pm ET (you can access all the lectures for the Algorithmic Lower Bound course, including future sessions, in the following playlist: <a href="https://www.youtube.com/playlist" rel="nofollow noopener" translate="no" target="_blank"><span class="invisible">https://www.</span><span class="">youtube.com/playlist</span><span class="invisible"></span></a>...</p><p> Additionally, all lectures on Introduction to Algorithms are available in this playlist: <a href="https://www.youtube.com/@hajiaghayi/playlists" rel="nofollow noopener" translate="no" target="_blank"><span class="invisible">https://www.</span><span class="ellipsis">youtube.com/@hajiaghayi/playli</span><span class="invisible">sts</span></a>)</p><p>Jan Olkowski discusses Lower Bounds in Massively Parallel Computation (MPC) models, introducing the shuffle model for understanding function computability. The lecture explores theoretical aspects, including the formal MPC model and its challenges. The second session extends to upper and lower bounds, focusing on rounds, machine limitations, and polynomials in the shuffle model. Conditional hardness assumptions lead to lower bounds for problems like maximal matching and connectivity in MPC. Ongoing research aims to enhance our understanding of solvability under these assumptions.</p><p><a href="https://mathstodon.xyz/tags/MPC" class="mention hashtag" rel="nofollow noopener" target="_blank">#<span>MPC</span></a> <a href="https://mathstodon.xyz/tags/ShuffleModel" class="mention hashtag" rel="nofollow noopener" target="_blank">#<span>ShuffleModel</span></a> <a href="https://mathstodon.xyz/tags/LowerBounds" class="mention hashtag" rel="nofollow noopener" target="_blank">#<span>LowerBounds</span></a> <a href="https://mathstodon.xyz/tags/UpperBounds" class="mention hashtag" rel="nofollow noopener" target="_blank">#<span>UpperBounds</span></a> <a href="https://mathstodon.xyz/tags/Polynomials" class="mention hashtag" rel="nofollow noopener" target="_blank">#<span>Polynomials</span></a> <a href="https://mathstodon.xyz/tags/Connectivity" class="mention hashtag" rel="nofollow noopener" target="_blank">#<span>Connectivity</span></a> <a href="https://mathstodon.xyz/tags/ConditionalHardness" class="mention hashtag" rel="nofollow noopener" target="_blank">#<span>ConditionalHardness</span></a> <a href="https://mathstodon.xyz/tags/Algorithms" class="mention hashtag" rel="nofollow noopener" target="_blank">#<span>Algorithms</span></a> <a href="https://mathstodon.xyz/tags/BigData" class="mention hashtag" rel="nofollow noopener" target="_blank">#<span>BigData</span></a> <a href="https://mathstodon.xyz/tags/ResearchPresentation" class="mention hashtag" rel="nofollow noopener" target="_blank">#<span>ResearchPresentation</span></a> <a href="https://mathstodon.xyz/tags/DataDistribution" class="mention hashtag" rel="nofollow noopener" target="_blank">#<span>DataDistribution</span></a></p>