1. Chenggang Wu: Testing Surface Area

2. Huy L. Nguyen: Approximate Near Neighbor Search Beyond Locality Sensitive Hashing

3. Reut Levi: A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor

4. Sangxia Huang: Improved Hardness of Approximating Chromatic Number

5. Avishay Tal: Properties and Applications of Boolean Function Composition

6. Zeyu Guo: Randomness-Efficient Curve Samplers

(1) [Completeness] If the surface area of F is at most $A$, then the algorithm accepts (whp);

(2) [Soundness] If F is not $\eps$-close to some set $G$ with surface area at most $\kappa A$, then the algorithm rejects (whp).

We call $\kappa \geq 1$ the *approximation factor* of the testing algorithm.

The $n = 1$ case (in which surface area is the number of endpoints) was introduced by Kearns and Ron, who solved the problem with $\kappa = 1/\eps$ and $O(1/\eps)$ oracle queries. Later, Balcan et al. [BBBY12] solved it with $\kappa =3D 1$ and $O(1/\eps^4)$ queries.

We give the first result for higher dimensions n. Perhaps surprisingly, our algorithm completely evades the "curse of dimensionality": for any n and any $\kappa > \frac{4}{\pi} \approx 1.27$, we give a test that uses $O(1/\eps)$ queries. For small $n$ we have improved bounds. For n=1 we can achieve $\kappa =1$ with $O(1/\eps^{3.5})$ queries (slightly improving [BBBY12]), or any $\kappa > 1$ with $O(1/\eps)$ queries (improving [KR98]). For n = 2, 3 we obtain $\kappa \approx 1.08, 1.125$ respectively, with $O(1/\eps)$ queries. Getting an arbitrary $\kappa > 1$ for n > 1 remains an open problem.

Finally, motivated by the learning results from [KOS08], we extend our techniques to obtain a similar tester for Gaussian surface area for any n, with query complexity $O(1/\eps)$ and any approximation factor $\kappa> \frac{4}{\pi} \approx 1.27$.

Joint work with Pravesh Kothari, Amir Nayyeri and Ryan O'Donnell.

We present a new data structure for the c=E2=80=93approximate near neighbor= problem (ANN) in the Euclidean space. For n points in R^d, our algorithm achieves O(dn^=CF=81) query time and O(n^{1+?=CF=81} + nd) space, where =CF=81 =E2= =89=A4 7/(8c^2) + O(1/c^3) + o(1). This is the first improvement over the result by Andoni and Indyk (FOCS 2006) and the first data structure that bypasses a locality=E2=80=93sensitive hashing lower bound proved by O=E2=80=99Donnell,= Wu and Zhou (ITCS 2011). By a standard reduction we obtain a data structure for the Hamming space and =E2=84=931 norm with =CF=81 =E2=89=A4 7/(8c) + O(1/c^{3/2= }) + o(1), which is the first improvement over the result of Indyk and Motwani (STOC 1998).

The talk is based on joint work with Alexandr Andoni, Piotr Indyk, and Ilya Razenshteyn.

We use this multiplicative behavior to establish several new applications. First, we give a counter-example using composition for a conjecture made by Adam Kalai in 2004, which if true would imply a better algorithm for the learning junta problem. Second, we show an unusual behaviour of block sensitivity with respect to composition which was not noticed before. We define a new complexity measure called "fractional block sensitivity" which better explains this behaviour. Last, we show how composition can tighten relations between complexity measures, by improving a result by Nisan and Szegedy about the relation between block sensitivity and degree as a polynomial.

**Note:** See
ECCC TR13-120.

Back to list of Oded's choices.