2016 - T1 - WS2 - Fundamental inequalities and lower bounds theme

Collection 2016 - T1 - WS2 - Fundamental inequalities and lower bounds theme

Organizer(s) Green Larsen, Kasper ; Hassibi, Babak ; Kerenidis, Iordanis ; Yeung, Raymond

Date(s) 15/02/2016 - 26/02/2016

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

00:00:00 / 00:00:00

51 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
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

52:00

published on February 25, 2016

Partition-Symmetrical Entropy Functions

By Qi Chen

48:43

published on February 25, 2016

Secret Sharing in Distributed Storage Systems

By Salim El Rouayheb

51:42

published on February 25, 2016

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

By Thathatchar S. Jayram

48:45

published on February 25, 2016

Lower Bound Techniques for Multiparty Communication Complexity

By Qin Zhang

50:09

published on February 25, 2016

A little advice can be very helpful

By Arkadev Chattopadhyay

44:10

published on February 25, 2016

Geometry of the entropy region 1/3

By László Csirmaz

45:56

published on February 25, 2016

Geometry of the entropy region 2/3

By László Csirmaz

38:01

published on February 25, 2016

Geometry of the entropy region 3/3

By László Csirmaz

52:31

published on February 25, 2016

Entropy inequalities and linear rank inequalities

By Randall Dougherty

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 1/3

By Suresh Venkatasubramanian

43:40

published on February 25, 2016

From Pigeons to Fano, and beyond 2/3

By Suresh Venkatasubramanian

50:11

published on February 25, 2016

From Pigeons to Fano, and beyond 3/3

By Suresh Venkatasubramanian

48:46

published on February 25, 2016

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

By John Walsh

49:16

published on February 29, 2016

Distributed Extremization : Fundamental Limits and Practical Schemes

By John Walsh

44:59

published on February 29, 2016

Shannon's Information Measures and Markov Structures 1/3

By Raymond Yeung

51:01

published on February 29, 2016

Shannon's Information Measures and Markov Structures 2/3

By Raymond Yeung

31:34

published on February 29, 2016

Shannon's Information Measures and Markov Structures 3/3

By Raymond Yeung

52:44

published on February 29, 2016

Beyond Shannon EPI: a Completely Monotone Conjecture

By Fan Cheng

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

50:39

published on February 29, 2016

Entropy region and convolution 1/3

By František Matúš

51:47

published on February 29, 2016

Entropy region and convolution 2/3

By František Matúš

38:33

published on February 29, 2016

Entropy region and convolution 3/3

By František Matúš

46:18

published on March 14, 2016

Ingleton-violating Points in the Entropy Region

By Nigel Boston

40:56

published on March 14, 2016

Data Structure Lower Bounds 1/3

By Kasper Green Larsen

35:33

published on March 14, 2016

Data Structure Lower Bounds 2/3

By Kasper Green Larsen

38:59

published on March 14, 2016

Data Structure Lower Bounds 3/3

By Kasper Green Larsen

46:01

published on March 14, 2016

Bounds on secure regenerating codes

By Kenneth Shum

55:06

published on March 14, 2016

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

By Babak Hassibi

42:28

published on March 14, 2016

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

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

35:43

published on March 14, 2016

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

By Søren Riis

49:57

published on March 14, 2016

Coded MapReduce : how to optimally trade computation with communication

By Salman Avestimehr

51:36

published on March 14, 2016

Rectangle inequalities for data structure lower bounds

By Yitong Yin

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

44:05

published on March 14, 2016

Dual Information Inequalities

By Tarik Kaced

36:27

published on March 14, 2016

Finding the fundamental limits of information systems: A computational approach

By Chao Tian

48:34

published on March 14, 2016

Aspects of Entropies and Inequalities 1/3

By Terence Chan

47:20

published on March 14, 2016

Aspects of Entropies and Inequalities 2/3

By Terence Chan

47:29

published on March 14, 2016

Aspects of Entropies and Inequalities 3/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

49:06

published on March 14, 2016

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

By Udi Wieder

47:25

published on March 14, 2016

Branching Programs 1/3

By Paul Beame

57:40

published on March 14, 2016

Branching Programs 2/3

By Paul Beame

47:03

published on March 14, 2016

Branching Programs 3/3

By Paul Beame

45:26

published on March 14, 2016

Network Coding for Inter-cloud Storage

By Yuchong Hu

47:37

published on March 14, 2016

Tight Cell-probe bounds for Online Hamming distance

By Benjamin Sach

52:25

published on March 14, 2016

Advances in Characterizing Turnstile Streaming Algorithms as Linear Sketches

By David Woodruff

Copyright Carmin.tv 2025

Give feedback