[Colloq] Colloquium: Wednesday, April 14, 10:30-11:45am, 366 WVH, Elena Grigorescu, MIT

[kirsten at ccs.neu.edu]

Elena Grigorescu, MIT

Title: Symmetries in Algebraic Property
Testing Abstract:

In Property Testing the goal is to quickly distinguish objects that
satisfy a property from objects that need to be changed in a large
fraction of places in order to satisfy the property. In this context,
Locally Testable Codes (LTCs) are error-correcting codes for which
membership can be decided from reading only a small section of the
input. Recent studies of LTCs focus on identifying what attributes of
codes allow them to be testable by local inspection. In particular, the 
``symmetries'' of a code seem to play an important role in providing
sufficient conditions for testing.  Kaufman and Sudan supported this
view by showing that the duals of linear codes that have the ``single
local orbit property'' under the affine symmetry group are locally
testable. A code has the single local orbit property if it is specified 
by a single local constraint and its translations under the symmetry
group of the code.

In this talk I will present a result motivated by questions arising in
previous studies of LTCs regarding error-correcting codes that have the
single local orbit property. We show that the dual of every ``sparse''
binary code whose coordinates are indexed by elements of F_{2^n} for
prime n, and whose symmetry group includes the group of non-singular
affine transformations of F_{2^n}, has the single local orbit property.
(A code is said to be  sparse if it contains polynomially many codewords
in its block length.) In particular, this class includes the dual-BCH
codes for whose duals (i.e., for BCH codes) simple bases were not known.
Our result gives the first short(O(n)-bit, as opposed to the natural
exp(n)-bit) description of a low-weight basis for BCH codes.

Our techniques involve the use of recent results from additive number
theory to prove that the codes we consider, and related codes emerging
from our proofs, have high distance. We then combine these with the
MacWilliams identities and some careful analysis of the invariance
properties to derive our results.

Joint work with Tali Kaufman and Madhu Sudan.



Kirsten Anderson
Northeastern University
College of Computer & Information Science
202 West Village H
360 Huntington Ave
Boston, MA 02115
(617) 373-8685
(617) 373-5121