CSDM Seminars

Jan
17
2011

Computer Science/Discrete Mathematics Seminar I

Cross-Validation and Mean-Square Stability
Sergei Vassilvitskii
11:15am|S-101

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

Dec
14
2010

Computer Science/Discrete Mathematics Seminar II

Erdos Distinct distance Problem in the Plane
10:30am|S-101

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

Dec
13
2010

Computer Science/Discrete Mathematics Seminar I

Colouring Tournaments
Paul Seymour
11:15am|S-101

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

Dec
06
2010

Computer Science/Discrete Mathematics Seminar I

Nonlinear Dvoretzky Theory
11:15am|S-101

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

Nov
30
2010

Computer Science/Discrete Mathematics Seminar II

Hardness Escalation and the Rank of Polynomial Threshold Proofs
10:30am|S-101

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

Nov
29
2010

Computer Science/Discrete Mathematics Seminar

Self-Correction, Distance Estimation and Local Testing of Codes
3:15pm|S-101

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

Nov
29
2010

Computer Science/Discrete Mathematics Seminar I

The Permanents of Gaussian Matrices
11:15am|S-101

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

Nov
23
2010

Computer Science/Discrete Mathematics Seminar II

Counting Pattern Avoiding Permutations Via Integral Operators
10:30am|S-101

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

Nov
22
2010

Computer Science/Discrete Mathematics Seminar I

Combinatorial Theorems in Random Sets
David Conlon
11:15am|S-101

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