dimacs logo color

Events

Event Calendar

« Previous Month

August 2026

Next Month »
Sun Mon Tue Wed Thu Fri Sat
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

Seminar Details

Counting, Entropy, and Compression

  • Start Date: July 20, 2017
  • Event Start Time: 2:00 PM
  • Event End Time: 3:00 PM
  • Organizers: Lazaros Gallos
  • Seminar Series: REU Seminar
  • Presenter(s): Anand Sarwate - Rutgers University
  • Event Location: DIMACS Seminar room
  • Abstract: Information Theory started out as the study of the fundamental limits of data compression and communication. Information-theoretic models for data use simple probabilistic models and derive expressions for the asymptotic rate (as the number of data points goes to infinity) at which new information is generated. In this talk I will start out by looking at this idea from a combinatorial point of view. A little bounding here and there will reveal the Shannon entropy as the key quantity. A brief detour through some deviation bounds for probability will introduce the notion of “typicality.” This in turn will let us show how to compress the data source in an almost-optimal manner. Time permitting, I will connect these ideas to algorithms for compression such as those used to generate .zip files.