Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

Mathematical Theories of Interaction with Oracles: Active Property Testing and New Models for Learning Boolean Functions

Liu Yang
School of Computer Science, Carnegie Mellon University
February 11, 2013

With the notion of interaction with oracles as a unifying theme of much of my dissertation work, I discuss novel models and results for property testing and computational learning, with the use of Fourier analytic and probabilistic methods.

The Ribe Program

Manor Mendel
The Open University of Israel; Member, School of Mathematics
January 29, 2013

A linear property of Banach spaces is called "local" if it depends on finite number of vectors and is invariant under renorming (i.e., distorting the norm by a finite factor). A famous theorem of Ribe states that local properties are invariant under (non linear) uniform-homeomorphisms, suggesting that local properties should have purely metric characterizations.
The Ribe program attempts to uncover explicit metric characterizations of local properties, and study them in the context of metric spaces. More broadly it attempts to apply ideas from Banach

Sparsity Lower Bounds for Dimensionality Reducing Maps

Jelani Nelson
Member, School of Mathematics
January 22, 2013

We give near-tight lower bounds for the sparsity required in several dimensionality reducing linear maps. In particular, we show:
(1) The sparsity achieved by [Kane-Nelson, SODA 2012] in the sparse Johnson-Lindenstrauss lemma is optimal up to a log(1/eps) factor.
(2) RIP_2 matrices preserving k-space vectors in R^n with the optimal number of rows must be dense as long as k < n / polylog(n).