Tutte seminar - Stefan van ZwamExport this event to calendar

Friday, June 4, 2010 — 3:30 PM to 4:30 PM EDT

Sphere Packing with SDP

Speaker: Stefan van Zwam
Affiliation: CWI Amsterdam and University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

Abstract:

The sphere packing problem in dimension $n$ asks for the maximum fraction of $\mathbb{R}^n$ that can be covered by (infinitely many) disjoint, equal-sized, $n$-dimensional spheres. We will study a special case in which the spheres are required to be centered on the vertices of a \emph{lattice}, the set of integer linear combinations of a vector basis of $\mathbb{R}^n$. The optimal density is known for $n \leq 8$ and $n = 24$.

We will model the problem as a semidefinite programming problem with additional constraints on the ranks of the matrices. By relaxing these rank constraints we obtain a proper SDP to approximate the optimum. We will then use a branch-and-bound technique to compute upper bounds. Finally we round to fractional solutions to make these bounds mathematically rigorous. Our results reproduce the known bounds up to dimension 8 (up to a small margin), and yield some new insights in the theory of Korkin-Zolotarev reduced lattice bases.

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
29
30
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
1
2
  1. 2019 (143)
    1. October (14)
    2. September (15)
    3. August (9)
    4. July (17)
    5. June (18)
    6. May (16)
    7. April (9)
    8. March (24)
    9. February (13)
    10. January (8)
  2. 2018 (138)
    1. December (2)
    2. November (18)
    3. October (14)
    4. September (9)
    5. August (2)
    6. July (10)
    7. June (13)
    8. May (17)
    9. April (9)
    10. March (19)
    11. February (14)
    12. January (11)
  3. 2017 (103)
  4. 2016 (137)
  5. 2015 (136)
  6. 2014 (88)
  7. 2013 (48)
  8. 2012 (39)
  9. 2011 (36)
  10. 2010 (40)
  11. 2009 (40)
  12. 2008 (39)
  13. 2007 (15)