Thursday, Oct 18, 2:15pm, WWH-513 (note different room)

  SPEAKER:
  Nir Ailon, Google

  TITLE:
  Dimension Reduction Using Rademacher Series on Dual Error Correcting
  Codes

  ABSTRACT:

  The Johnson-Lindenstrauss dimension reduction idea using random
  projections was discovered in the early 80's.  Since then many
  "computer science friendly" versions were published, offering constant
  factor but no big-Oh improvements in the runtime.  Two years ago Ailon
  and Chazelle showed a nontrivial algorithm with the first asymptotic
  improvement, and suggested the question:  What is the exact complexity
  of J-L computation from d dimensions to k dimensions?   An O(d log d)
  upper bound is implied by A-C for k up to d^{1/3} (in the L2->L2)
  case.  In this talk I will show how to achieve this bound for k up to
  d^{1/2} combining techniques from the theories of error correcting
  codes and probability in Banach spaces.  This is based on recent joint
  work with Edo Liberty.

------------------------------------------------------------------------