Nexus Trimester - 2016 - Fundamental Inequalities and Lower Bounds Theme

Collection Nexus Trimester - 2016 - Fundamental Inequalities and Lower Bounds Theme

Organizer(s)

Date(s) 13/05/2024

00:00:00 / 00:00:00

28 51

Advances in Characterizing Turnstile Streaming Algorithms as Linear Sketches

By David Woodruff

I will cover recent developments in characterizing the space-optimal turnstile data stream algorithm for computing any relation of an underlying frequency vector as a linear sketch. I'll first discuss the original proof of this result, then several optimizations which have applications to obtaining optimal lower bounds for counting with additive error, dynamic graph matching, and frequency moments, which we do not know how to prove in another way. I'll also mention multi-pass extensions. Based on joint works with Yuqing Ai, Wei Hu, Yi Li, Huy Nguyen, and Omri Weinstein

Information about the video

Date of recording 26/02/2016
Date of publication 14/03/2016
Institution IHP
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

52:31

published on February 25, 2016

Entropy inequalities and linear rank inequalities

By Randall Dougherty

44:10

published on February 25, 2016

Geometry of the entropy region

By László Csirmaz

38:01

published on February 25, 2016

Geometry of the entropy region

By László Csirmaz

45:56

published on February 25, 2016

Geometry of the entropy region

By László Csirmaz

50:09

published on February 25, 2016

A little advice can be very helpful

By Arkadev Chattopadhyay

51:42

published on February 25, 2016

Composition Theorem for Conical Juntas with Applications to Query and Communication Complexity

By Thathatchar S. Jayram

53:23

published on February 25, 2016

Fundamental Inequalities and Capacity Upper Bounds

By Young Han Kim

50:27

published on February 25, 2016

From Pigeons to Fano, and beyond

By Suresh Venkatasubramanian

43:40

published on February 25, 2016

From Pigeons to Fano, and beyond

By Suresh Venkatasubramanian

50:11

published on February 25, 2016

From Pigeons to Fano, and beyond

By Suresh Venkatasubramanian

48:46

published on February 25, 2016

Rate Regions for Network Coding: Computation, Symmetry, and Hierarchy

By John Walsh

48:43

published on February 25, 2016

Secret Sharing in Distributed Storage Systems

By Salim El Rouayheb

48:45

published on February 25, 2016

Lower Bound Techniques for Multiparty Communication Complexity

By Qin Zhang

52:00

published on February 25, 2016

Partition-Symmetrical Entropy Functions

By Qi Chen

51:47

published on February 29, 2016

Entropy region and convolution

By František Matúš

42:52

published on February 29, 2016

On Outer Bounds for the Storage-Repair-Bandwidth Tradeoff of Exact-Repair Regenerating Codes

By P. Vijay Kumar

38:33

published on February 29, 2016

Entropy region and convolution

By František Matúš

50:39

published on February 29, 2016

Entropy region and convolution

By František Matúš

52:44

published on February 29, 2016

Beyond Shannon EPI: a Completely Monotone Conjecture

By Fan Cheng

31:34

published on February 29, 2016

Shannon's Information Measures and Markov Structures

By Raymond Yeung

51:01

published on February 29, 2016

Shannon's Information Measures and Markov Structures 2/3

By Raymond Yeung

44:59

published on February 29, 2016

Shannon's Information Measures and Markov Structures

By Raymond Yeung

49:16

published on February 29, 2016

Distributed Extremization : Fundamental Limits and Practical Schemes

By John Walsh

57:40

published on March 14, 2016

Branching Programs 2/3

By Paul Beame

45:26

published on March 14, 2016

Network Coding for Inter-cloud Storage

By Yuchong Hu

47:03

published on March 14, 2016

Branching Programs 3/3

By Paul Beame

47:25

published on March 14, 2016

Branching Programs 1/3

By Paul Beame

52:25

published on March 14, 2016

Advances in Characterizing Turnstile Streaming Algorithms as Linear Sketches

By David Woodruff

47:37

published on March 14, 2016

Tight Cell-probe bounds for Online Hamming distance

By Benjamin Sach

49:06

published on March 14, 2016

How to Approximate a Set without Knowing it's Size in Advance

By Udi Wieder

47:29

published on March 14, 2016

Fundamental aspects of information inequalities 3/3

By Terence Chan

47:20

published on March 14, 2016

Fundamental aspects of information inequalities 2/3

By Terence Chan

48:34

published on March 14, 2016

Fundamental aspects of information inequalities 1/3

By Terence Chan

47:49

published on March 14, 2016

The Stam region, or the differential entropy region for sums of independent random vectors

By Mokshay Madiman

44:25

published on March 14, 2016

Abelian Group Representability and Fundamental Inequalities

By Frédérique Oggier

44:05

published on March 14, 2016

Dual Information Inequalities

By Tarik Kaced

49:57

published on March 14, 2016

Coded MapReduce : how to optimally trade computation with communication

By Salman Avestimehr

39:59

published on March 14, 2016

Lower bounds for streaming problems 1/3

By Raphael Clifford

50:53

published on March 14, 2016

Lower bounds for streaming problems 2/3

By Raphael Clifford

40:38

published on March 14, 2016

Lower bounds for streaming problems 3/3

By Raphael Clifford

36:27

published on March 14, 2016

Finding the fundamental limits of information systems: A computational approach

By Chao Tian

51:36

published on March 14, 2016

Rectangle inequalities for data structure lower bounds

By Yitong Yin

35:43

published on March 14, 2016

Finite Dynamical Systems, Causal Networks and Information Inequalities - Part 2B

By Søren Riis

40:28

published on March 14, 2016

Finite Dynamical Systems, Causal Networks and Information Inequalities - Part 2A

By Søren Riis

42:28

published on March 14, 2016

Finite Dynamical Systems, Causal Networks and Information Inequalities - Part 1A

By Søren Riis

55:06

published on March 14, 2016

Simple Algorithms and Guarantees for Low Rank Matrix Completion over GF(2)

By Babak Hassibi

38:59

published on March 14, 2016

Data Structure Lower Bounds 3/3

By Kasper Green Larsen

46:18

published on March 14, 2016

Ingleton-violating Points in the Entropy Region

By Nigel Boston

35:33

published on March 14, 2016

Data Structure Lower Bounds 2/3

By Kasper Green Larsen

40:56

published on March 14, 2016

Data Structure Lower Bounds 1/3

By Kasper Green Larsen

46:01

published on March 14, 2016

Bounds on secure regenerating codes

By Kenneth Shum

Copyright Carmin.tv 2024

Give feedback