[Colloquium] TTIC Talks: Moshe Schwartz, Ben Gurion University

[Liv Leader]

When:       Friday, February 3 @ 11 a.m.

Where:     TTIC, 6045 S. Kenwood Avenue, Room #526

Who:        Moshe Schwartz, Ben Gurion University

Title:        Networks of Relations in the Service of Constrained Coding

Constrained systems are widely used today in communication and storage
systems. A two-dimensional constrained system is the set of all
two-dimensional binary arrays which obey a certain constraint. A well-known
example of such constraints is the (0,1)-RLL constraint, i.e., no two
adjacent zeros (horizontally or vertically) in the array. This is
equivalent to counting the number of independent sets in the grid graph.
When the diagonal directions are also included this is equivalent to
counting arrays of non-attacking kings. The logarithm of the number of such
arrays, divided by the area of the array as its sides go to infinity, is
called the capacity of the constraint.

We address the well-known problem of determining the capacity of
two-dimensional constrained systems. While the one-dimensional case is well
understood to the extent that there are techniques for rigorously deriving
the exact capacity, in contrast, computing the exact capacity of a
two-dimensional constrained system is still an elusive research goal.

We present a rigorous technique that yields an exact capacity of a
two-dimensional constrained coding system. In addition, we devise an
efficient (polynomial time) algorithm for counting the exact number of
constrained arrays of any given size. Our approach is a composition of a
number of ideas and techniques: describing the capacity problem as a
solution to a counting problem in networks of relations, graph-theoretic
tools originally developed in the field of statistical mechanics,
techniques for efficiently simulating quantum circuits, as well as ideas
from the theory related to the spectral distribution of Toeplitz matrices.

Using our technique we derive a closed form solution to the capacity
related to the Path-Cover constraint in a two-dimensional triangular array
(assigning 1's and 0's to the edges of the triangular grid such that every
vertex is incident to either one or two 1's). Path-Cover is a
generalization of the well known one-dimensional (0,1)-RLL constraint.

The talk is self-contained, and a brief survey of constrained coding will
be given, as well as a few open problems motivated by storage systems.

Host: Nati Srebro, nati at ttic.edu

-- 
Liv Leader
Human Resources Coordinator

Toyota Technological Institute Chicago
6045 S Kenwood Ave
Chicago, IL 60637
Phone- (773) 702-5033
Fax-     (773) 834-9881
Email-  lleader at ttic.edu <jam at ttic.edu>
Web-   www.ttic.edu
<http://www.ttic.edu/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20120131/110d31fb/attachment.htm