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

Cayley Graphs and List-decodable Zero-rate Codes

  • Start Date: February 26, 2018
  • Event Start Time: 2:00 PM
  • Event End Time: 3:00 PM
  • Seminar Series: Rutgers Discrete Mathematics Seminar
  • Presenter(s): Noga Alon - Princeton University and Tel Aviv University
  • Event Location: Hill Center-Room 705
  • Presentation Type: Stand Alone Presentation
  • Abstract:

    What is the maximum possible number of words in a binary code of length n so that there is no Hamming ball of radius (1/4+epsilon)n containing more than two words ? I will show that the answer is Theta(1/epsilon^{3/2}). A crucial ingredient in the proof is a construction of a family of Cayley graphs which is useful in tackling several additional extremal problems in Graph Theory and Geometry. Joint work with Bukh and Polyanskiy.