Georgia Institute of Technology College of Sciences

Sergio will be leading discussion and presenting 6.2: The John-Nirenberg Theorem. Stop by, we will be havIng a good Time.

Suppose that each node of a rooted tree has a message that it wants to pass up the tree to the root. How can we design a protocol that guarantees all messages (eventually) reach there without being interfered with by other messages, if the nodes themselves do not know the underlying structure of the tree, or even whether their previous messages were successfully transmitted or not? I will describe (near optimal) answers to several variations of this problem, based on joint work with Marek Chrobak (UCR), Laszek Gasieniec (Liverpool) and Dariusz Kowalski (Liverpool).

Using basic linear algebra as a natural language of special relativity, and assuming very little knowledge of physics, we present a novel linear-algebraic derivation of the Lorentz transformation. Through the geometry of Minkowski diagrams, we analyze properties and paradoxes of special relativity including the Twin paradox and the bug-rivet paradox.Dr. de Pillis is a renowned cartoonist and animator, and his new book entitled Illustrated Special Relativity Through its Paradoxes is a fusion of Linear Algebra, Graphics, and Reality.

The closest vector problem (CVP) on lattices (i.e. given an n dimensional lattice L with basis B and target point t, find a closest lattice point in L to t) is fundamental NP-hard problem with applications in coding, cryptography & optimization. In this talk, we will consider the preprocessing version of CVP (CVPP), an important variant of CVP, where we allow arbitrary time to preprocess the lattice before answering CVP queries. In breakthrough work, Micciancio & Voulgaris (STOC 2010) gave the first single exponential time algorithm for CVP under the l_2 norm based on Voronoi cell computations. More precisely, after a preprocessing step on L requiring tilde{O}(2^{2n}) time, during which they compute the Voronoi cell of L (the set of points closer to the origin than to any other point in L), they show that additional CVP queries on L (i.e. CVPP) can be solved in tilde{O}(2^{2n}) time. For our main result, we show that given the Voronoi cell V of L as preprocessing, CVP on any target t can be solved in expected tilde{O}(2^n) time. As our main technical contribution, we give a new randomized procedure that starting from any close enough lattice point to the target t, follows a path in the Voronoi graph of L (i.e. x,y in L are adjacent if x+V and y+V share a facet) to the closest lattice vector to t of expected polynomial size. In contrast, the path used by MV algorithm is only known to have length bounded by tilde{O}(2^n). Furthermore, for points x,y in L, we show that the distance between x and y in the Voronoi graph is within a factor n of ||x-y||_V (norm induced by the Voronoi cell), which is best possible. For our analysis, we rely on tools from high dimensional convex geometry. No background in convex geometry or lattices will be assumed. Time permitting, I will describe related results & open questions about paths on more general lattice Cayley graphs. Joint work with Nicolas Bonifas (Ecole Polytechnique).