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

1 51

Partition-Symmetrical Entropy Functions

Let N={1,…,n}. Let p={N1,…,Nt} be a t-partition of N. An entropy function h is called p-symmetrical if for all A, B⊂N, h(A)=h(B) whenever |A∩Ni|=|B∩Ni|, i=1,…,t. We prove that the closure of the set of p-symmetrical entropy functions is completely characterized by Shannon-type information inequalities if and only if p is the 1-partition or a 2-partition with one of its blocks being a singleton. The characterization of the partition-symmetrical entropy functions can be useful for solving some information theory and related problems where symmetry exists in the structure of the problems.

Information about the video

Date of recording 15/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

94A17 Measures of information, entropy

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