ERATO河原林巨大グラフプロジェクト & ELC合同講演会
日時
2012年11月30日（金）15:30-17:30
場所
キャンパスイノベーションセンター東京
http://www.cictokyo.jp/access.html
詳細
16:30-17: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.
17:30-18: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.
