Nexus Trimester - 2016 - Fundamental Inequalities and Lower Bounds Theme

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

Organizer(s)

Date(s) 12/05/2024

00:00:00 / 00:00:00

27 51

Branching Programs 1/3

Branching programs are clean and simple non-uniform models of computation that capture both time and space simultaneously. We present the best methods known for obtaining lower bounds on the size of (length-restricted) branching programs and the applications of these methods to derive general time-space tradeoff lower bounds for specific natural problems.

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