CSDM Seminars

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...

Erdos conjectured that N points in the plane determine at least c N (log N)^{-1/2} different distances. Building on work of Elekes-Sharir, Nets Katz and I showed that the number of distances is at least c N (log N)^{-1} . (Previous estimates had...

A ``tournament'' is a digraph obtained from a complete graph by directing its edges, and ``colouring'' a tournament means partitioning its vertex set into acyclic subsets (``acyclic'' means the subdigraph induced on the subset has no directed cycles...

A "proof assistant" is a software package comprising a validity checker for proofs in a particular logic, accompanied by semi-decision procedures called "tactics" that assist the mathematician in filling in the easy parts of the proofs. I will...

The classical Dvoretzky theorem asserts that for every integer k>1 and every target distortion D>1 there exists an integer n=n(k,D) such that any n-dimensional normed space contains a subspace of dimension k that embeds into Hilbert space with...

A hardness escalation method applies a simple transformation that increases the complexity of a computational problem. Using multiparty communication complexity we present a generic hardness escalation method that converts any family of...

We construct linear codes of almost-linear length and linear distance that can be locally self-corrected on average from a constant number of queries: 1. Given oracle access to a word $w\in\Sigma^n$ that is at least $\varepsilon$-close to a codeword...

In recent joint work with Alex Arkhipov, we proposed a quantum optics experiment, which would sample from a probability distribution that we believe cannot be sampled (even approximately) by any efficient classical algorithm, unless the polynomial...

A permutation pi=(pi_{1},...,pi_{n}) is consecutive 123-avoiding if there is no sequence of the form pi_i pi_{i+1} pi_{i+2}. More generally, for S a collection of permutations on m+1 elements, this definition extends to define consecutive S...

The famous theorem of Szemerédi says that for any natural number k and any a > 0 there exists n such that if N >= n then any subset A of the set [N] ={1,2,...,N} of size |A| >= a N contains an arithmetic progression of length k. We consider the...