Computer Science and Discrete Mathematics (CSDM)

Recursive Majority-of-three (3-Maj) is a deceptively simple problem in the study of randomized decision tree complexity. The precise complexity of this problem is unknown, while that of the similarly defined Recursive NAND tree is completely...

Boolean Threshold Functions (BTF) arise in many contexts, ranging from computer science and learning theory to theoretical neurobiology. In this talk, I will present non-rigorous approaches developed in the statistical physics of disordered...

Given data drawn from a mixture of multivariate Gaussians, a basic problem is to accurately estimate the mixture parameters. We provide a polynomial-time algorithm for this problem for any fixed number ($k$) of Gaussians in $n$ dimensions (even...

We give an elementary proof of a generalization of Bourgain and Tzafriri's Restricted Invertibility Theorem, which says roughly that any matrix with columns of unit length and bounded operator norm has a large coordinate subspace on which it is well...

The Unique Games conjecture (UGC) has emerged in recent years as the starting point for several optimal inapproximability results. While for none of these results a reverse reduction to Unique Games is known, the assumption of bijective...

We study the local testabilty of sparse linear codes. This problem is intimately connected to the problem of tolerant linearity testing of Boolean functions under nonuniform distributions. We give linearity tests for several natural and...

We study the complexity of computing some basic arithmetic operations over GF(2^n), namely computing q-th root and q-th residuosity, by constant depth arithmetic circuits over GF(2) (also known as AC^0(parity)). Our main result is that these...

The Johnson-Lindenstrauss lemma states that for any n points in Euclidean space and error parameter 0

All known proofs of the lemma construct a distribution over linear mappings so that a random such mapping suffices with high probability. In this talk, I will present various proofs of the JL lemma satisfying, for example, (1) the support of the distribution is small, so that a random embedding can be selected with few random bits (e.g. O(log n loglog n) bits for constant eps, which is suboptimal by a loglog n factor), and (2) every embedding matrix in the support of the distribution is sparse (only O(eps*k) entries per column are non-zero), to speed up computation. I will also describe some open problems. This talk is based on joint works with Daniel Kane (Harvard).

A popular practical method of obtaining a good estimate of the error rate of a learning algorithm is k-fold cross-validation. Here, the set of examples is first partitioned into k equal-sized folds. Each fold acts as a test set for evaluating...

The Johnson-Lindenstrauss lemma (also known as Random Projections) states that any set of n points in Euclidian space can be embedded almost isometrically into another Euclidian space of dimension O(log(n)). The talk will focus on the efficiency...