Title: Proof Producing Algorithms
Speaker: Sean McLaughlin, CSD
Location: NSH 1507
Time: 12-1 pm
Date: Friday, April 06, 2007
Abstract:
The design and implementation of algorithms is a fundamental task in computer science. But the process is error-prone, and historically many important programs and algorithms have contained serious errors.# While
often we can live with the bugs lurking in our algorithms and code, in some domains it is essential that the programs we write be error-free.
In this talk I will survey strategies for designing algorithms that, in addition to computing a result, produce a proof of the correctness of that result. I will then focus on the application of these strategies to a number of areas, such as automated reasoning, programming language semantics, and formalized mathematics.
Friday, April 6th, 2007
3:30pm
Wean Hall 7220
Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1
Piotr Indyk (MIT)
The area of geometric functional analysis is concerned with studying properties of geometric (normed) spaces. A typical question in the area is: given two geometric spaces X, Y, is there an embedding F of X into Y so that F distorts the distances between any pair of points by only a constant factor? One of the classic results of this type is a constant-distortion embedding of an n-dimensional space equipped with L2 norm, into an O(n)-dimensional space equipped with L1 norm (also known as Dvoretzky’s theorem for L1). Embeddings have many interesting applications, in computer science and beyond.
A ubiquitous tool for constructing such embeddings is the probabilistic method: the mapping is chosen at random, and one shows that it “works” with high probability. Unfortunately, this approach does not yield a concrete (or explicit) construction of an embedding. A folklore open problem has been to obtain explicit constructions with parameters that (almost) match the non-constructive bounds. However, the progress on this front has been somewhat limited. For example, the best known explicit construction of an embedding of an n-dimensional L2 space into an m-dimensional L1 space guarantees only m=O(n^2).
In this talk I will show an explicit construction of an embedding of an n-dimensional L2 space into L1 space of dimension n^{1+o(1)}. The construction utilizes two tools: discrete uncertainty principles (introduced by Donoho and Stark in the area of digital signal processing) and randomness extractors. If time allows, I will also show some related constructions, with application to signal sketching and compressed sensing.
Title : Integer Sets Having the Maximum Number of Distinct Differences
Speaker : Oleg Pikhurko
When : 4:30-5:30pm, April 5th
Where : Physical Plant Building(PPB) Room #300
Abstract:
We consider the function $D(k,n)$ which is the maximum of $ |A-A|=|\{a-b \mid a,b\in A\}| $ over all $k$-subsets $A$ of $[n]=\{0,\ldots,n\}$. In other words, we want to maximize the number of distinct differences that a $k$-subset of $[n]$ can have. The range of interest is when $k$ is of order $\sqrt n$. A few well-known problems from additive number theory can be restated in terms of the function $D(k,n)$.
We show that for any fixed real $c\ge 0$ and any function $k(n)=(c+o(1))\sqrt n$ the limit $ d(c)=\lim_{n\to\infty} \frac{D(k(n),n)}n $ exists. We present upper and lower bounds on $d(c)$, outlining (mostly combinatorial) proofs. A few other versions of the problem, such as maximizing the number of distinct sums, will be considered as well.
Some of the presented results are joint work with B\’ela Bollob\’as and with Tomasz Schoen.
