Computer Science/Discrete Mathematics Seminar I

I will present recent joint work with O. Friedland and V. Milman, where we use simple probabilistic estimates on Bernoulli random variables, together with tools from convex geometric analysis, to arrive at some new results. The first result has to do with approximating the euclidean ball with sets described by fairly few linear inequalities, where we improve a result of Barron and Cheang. In the second part of the talk I will discuss some of our results which have to do with properties of (usually random) matrices, for example their norm and norm of inverse (so, smallest singular numbers), and also the usage of such matrices (+-1, and others) to find near-euclidean sections of the cross-polytope.