ERATO河原林巨大グラフプロジェクトとELCの合同講演会を以下の要領で開催いたします．奮ってご参加下さい．

日時: 11/30(金) 15:30-17:30
場所: キャンパスイノベーションセンター東京 2階多目的室4

15:30-16:30
Speaker: Arnab Bhattacharyya (DIMACS/Rutgers)
Title: Every locally characterized affine-invariant property is testable
Abstract:
Let F = F_p for any fixed prime p >= 2. An affine-invariant property is a
property of functions on F^n that is closed under taking affine
transformations of the domain. We prove that all affine-invariant property
having local characterizations are testable. In fact, we show a
proximity-oblivious test for any such property P, meaning that there is a
test that, given an input function f, makes a constant number of queries to
f, always accepts if f satisfies P, and rejects with positive probability
if the distance between f and P is nonzero. More generally, we show that
any affine-invariant property that is closed under taking restrictions to
subspaces and has bounded complexity is testable.

We also prove that any property that can be described as the property of
decomposing into a known structure of low-degree polynomials is locally
characterized and is, hence, testable. For example, whether a function is a
product of two degree-d polynomials, whether a function splits into a
product of d linear polynomials, and whether a function has low rank are
all examples of degree-structural properties and are therefore locally
characterized.

Our results depend on a new Gowers inverse theorem by Tao and Ziegler for
low characteristic fields that decomposes any polynomial with large Gowers
norm into a function of low-degree non-classical polynomials. We establish
a new equidistribution result for high rank non-classical polynomials that
drives the proofs of both the testability results and the local
characterization of degree-structural properties.

Joint work with Eldar Fischer, Hamed Hatami, Pooya Hatami, and Shachar
Lovett.

16:30-17:30
Speaker: Mikkel Thorup (AT&T Labs Research)
Title: The Power of Tabulation Hashing
Abstract: 
Randomized algorithms are often enjoyed for their simplicity, but the hash functions
used to yield the desired theoretical guarantees are often neither simple nor practical.
Here we show that the simplest possible tabulation hashing provides unexpectedly strong guarantees.
The scheme itself dates back to Carter and Wegman (STOC'77). Keys are viewed as consisting
of c characters. We initialize c tables T1,…,Tc mapping characters to random hash codes.
A key x=(x1,…,xc) is hashed to T1[x1]⊕⋯⊕Tc[xc], where ⊕ denotes xor. While this scheme is not
even 4-independent, we show that it provides many of the guarantees that are normally obtained
via higher independence, e.g., Chernoff-type concentration, min-wise hashing for estimating
set intersection, and cuckoo hashing. We shall also discuss a twist to simple tabulation
that leads to extremely robust performance for linear probing with small buffers.