2016 - T1 - WS1 - Distributed computation and communication theme

Collection 2016 - T1 - WS1 - Distributed computation and communication theme

Organizer(s) Gács, Péter ; Körner, János ; Schulman, Leonard

Date(s) 01/02/2016 - 12/02/2016

linked URL https://web.archive.org/web/20221228152145/http://iss.bu.edu/bobak/csnexus//distcomp.html

00:00:00 / 00:00:00

40 42

Worst-Case Optimal Algorithms for Parallel Query Processing

By Paris Koutris

We study the communication complexity for the problem of computing a conjunctive query on a large database in a massively parallel setting. In contrast to previous work, where upper and lower bounds on the communication were specified for particular structures of data, in this work we focus on worst-case analysis of the communication cost. We also show a surprising connection to the external memory model, which allows us to translate parallel algorithms to external memory algorithms. This technique allows us to recover several recent results on the I/O complexity for computing join queries, and also obtain optimal algorithms for other classes of queries.

Information about the video

Date of recording 11/02/2016
Date of publication 25/02/2016
Institution IHP
Licence CC BY-NC-ND
Language English
Format MP4

Domain(s)

Computer Science

MSC codes

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow

All the collection videos

58:00

published on February 2, 2016

Recent Advances in Randomized Rumor Spreading

By George Giakkoupis

01:02:20

published on February 1, 2016

Different versions of Kolmogorov complexity and a priori probability: a gentle introduction (1/2)

By Alexander Shen

51:36

published on February 1, 2016

Different versions of Kolmogorov complexity and a priori probability: a gentle introduction (2/2)

By Alexander Shen

50:40

published on February 3, 2016

Relation between monotonic complexity and algorithmic probability (1/2)

By Péter Gács

51:31

published on February 25, 2016

Relation between monotonic complexity and algorithmic probability (2/2)

By Péter Gács

58:10

published on February 2, 2016

Knowledge and Coordinated Action (1/2)

By Yoram Moses

56:17

published on February 3, 2016

Knowledge and Coordinated Action (2/2) Coordination and Time

By Yoram Moses

56:14

published on February 2, 2016

On Parallels Between Shannon’s and Kolmogorov’s Information Theories (where the parallelism fails and why)

By Andrei Romashchenko

01:01:54

published on February 3, 2016

Distributed compression: the algorithmic-information-theoretical view

By Marius Zimand

46:30

published on February 25, 2016

Tensorization of information functionals (1/2) Forward and Reverse hypercontractivity using information measures

By Chandra Nair

51:22

published on February 25, 2016

Tensorization of information functionals (2/2) Applications in establishing optimality of Gaussian distributions and in a Boolean function Conjecture

By Chandra Nair

51:26

published on February 25, 2016

Communication Cost in Parallel Query Processing

By Dan Suciu

01:06:49

published on February 25, 2016

Information Theory: A Classical, Partial View

By Cédric Villani

55:41

published on February 25, 2016

Some Some Information-Theoretic Problems in Theoretical Computer Science - Part II

By Omri Weinstein

48:45

published on February 25, 2016

High Probability Guarantees in Repeated Games: Theory and Applications in Information Theory

By Amin Aminzadeh Gohari

50:40

published on February 25, 2016

Lower Bounds for Distributed Graph Problems via Information Theory

By Stephan Sebastian Holzer

55:23

published on February 25, 2016

Codes in graphs

By János Körner

55:16

published on February 25, 2016

Exponential separation of information and communication and how to prove lower bounds on disjointness and the non-negative rank of matrices

By Anup Rao

56:46

published on February 25, 2016

Exponential separation of information and communication and how to prove lower bounds on disjointness and the non-negative rank of matrices (1/2)

By Anup Rao

54:02

published on February 25, 2016

Exponential separation of information and communication and how to prove lower bounds on disjointness and the non-negative rank of matrices (2/2)

By Anup Rao

46:55

published on February 25, 2016

Interactive Coding for Interactive Proofs

By Allison Bishop

53:42

published on February 25, 2016

A reductionist view of network information theory

By Michael Langberg

49:36

published on February 25, 2016

Interactive Information Complexity and Applications : Interactive Compression - Part I/1

By Omri Weinstein

01:12:42

published on February 25, 2016

Interactive Information Complexity and Applications : Interactive Compression - Part I/2

By Omri Weinstein

56:45

published on February 25, 2016

Interactive Information Complexity and Applications : Interactive Compression - Part II

By Omri Weinstein

55:42

published on February 25, 2016

Coding for interactive communication

By Ran Gelles

51:37

published on February 25, 2016

Tree codes - relaxations, constructions and applications

By Ran Gelles

55:08

published on February 25, 2016

Communication with Contextual Uncertainty

By Badih Ghazi

43:33

published on February 25, 2016

Secure and Reliable Codes for Cooperative Data Exchange

By Alex Sprintson

50:56

published on February 25, 2016

An Interactive Information Odometer and Applications

By Omri Weinstein

53:30

published on February 25, 2016

Strong Data Processing and the Entropy Power Inequality

By Thomas Courtade

52:06

published on February 25, 2016

Colony or ant, whose in charge?

By Ofer Feinerman

55:02

published on February 29, 2016

Polynomial-time interactive coding (1/2)

By Yael Kalai

48:20

published on February 25, 2016

Polynomial-time interactive coding (2/2)

By Yael Kalai

42:00

published on February 25, 2016

Confidence sharing: an economic strategy for efficient information flows in animal groups

By Amos Korman

57:06

published on April 14, 2016

Topology matters in communication

By Arkadev Chattopadhyay

52:43

published on February 25, 2016

Lower bounds for coding for multiparty interactive communication (1/2)

By Klim Efremenko

49:29

published on February 25, 2016

Lower bounds for coding for multiparty interactive communication (2/2)

By Klim Efremenko

58:20

published on February 25, 2016

On the Ultimate Limit of Two-Terminal Interactive Computing

By Prakash Ishwar

53:23

published on February 25, 2016

Worst-Case Optimal Algorithms for Parallel Query Processing

By Paris Koutris

01:01:54

published on February 25, 2016

Prospects for tree codes

By Dusa McDuff , Leonard Schulman

45:18

published on February 25, 2016

Randomized proof-labeling schemes

By Boaz Patt-Shamir

Copyright Carmin.tv 2025

Give feedback