ELC Seminar (C01)
Date: July 15th
Time: 15:00 - 17:30
Place: CELC Seminar room (Rm.404)

*** NOTICE ***
The order of the talks has been changed.  Prof. Asterias first
(from 15:00) and then Prof. Ailon next (from 16:15).

Speaker: Professor Nir Ailon(Technion)
Title: Fast Johnson-Lindenstrauss: History, Recent Progress and Open Questions  
Abstract: 
A Johnson-Lindenstrauss Transform is defined to
be a distribution over k-by-n matrices with the following property:
For any fixed unit vector x in R^n, if A is drawn from the istribution
then the estimator ||Ax|| looks like a Gaussian centered at 1 with
variance roughly 1/k. A Fast Johnson-Lindenstrauss Transform (FJLT)
has the additional property that Ax can be computed in time O(n log n).
Such transformations are related to design of restricted isometry
matrices, useful for universal sparse reconstruction.
FJLT constructions are known for k at most an order of sqrt(n).
For k above sqrt(n), best constructions slightly compromise the
distribution guarantees of ||Ax||. I will survey the history
of results and efforts for constructing FJLTs, including some recent progress.
Based on joint work with Bernard Chazelle, Edo Liberty and Holger Rauhut.


Speaker: Albert Atserias( Universitat Polit�cnica de Catalunya )
Title: On Continuous and Combinatorial Relaxations of Graph Isomorphism
Abstract: 
The graph isomorphism problem is one of the most celebrated
computational problems whose complexity status lies somewhere imediate 
between P and NP-complete. We revisit two very different-looking 
relaxations of the problem. In the first relaxation we require the graphs
to preserve the number of types of local neighborhoods through the well-known 
vertex-refinement heuristic and its obvious extension to refinement of k-tuples. 
In the second relaxation we write the natural 0-1 linear program for
graph isomorphism and relax it to the continuum through the hierarchy of 
continuous relaxations suggested by Sherali and Adams for general 0-1
combinatorial problems. We show that these two very different-looking
relaxations are indeed equivalent. An interesting consequence of this
is that the graph  isomorphism problem restricted to planar graphs 
can be solved by an explicit polynomial-size linear program.