The condition number of a matrix is at the heart of numerical
linear algebra. In the 1940s von-Neumann and Goldstine, motivated
by the problem of inverting, posed the following question:
(1) What is the condition number of a random matrix ?
In this talk I will insult your intelligence by showing a
non-original proof of the Central Limit Theorem, with
not-particularly-good error bounds. However, the proof is very
simple and flexible, allowing generalizations to multidimensional
and...
We give a pseudorandom generator, with seed length $O(log n)$,
for $CC0[p]$, the class of constant-depth circuits with unbounded
fan-in $MODp$ gates, for prime $p$. More accurately, the seed
length of our generator is $O(log n)$ for any constant...
I will describe the proof of the following surprising result:
the typical billiard paths form the family of the most uniformly
distributed curves in the unit square. I will justify this vague
claim with a precise statement. As a byproduct, we...
I will talk about the computational complexity of computing the
noncommutative determinant. In contrast to the case of commutative
algebras, we know of (virtually) no efficient algorithms to compute
the determinant over non-commutative domains...
Finding the longest increasing subsequence (LIS) is a classic
algorithmic problem. Simple $O(n log n)$ algorithms, based on
dynamic programming, are known for solving this problem exactly on
arrays of length $n$.
The small-set expansion conjecture introduced by Raghavendra and
Steuerer is a natural hardness assumption concerning the problem of
approximating edge expansion of small sets (of size $\delta n$) in
graphs. It was shown to be intimately...
The Stepanov method is an elementary method for proving bounds
on the number of roots of polynomials. At its core is the following
idea. To upper bound the number of roots of a polynomial f(x) in a
field, one sets up an auxiliary polynomial F...
An epsilon-biased set X in {0,1}n is a set so that for every
non-empty set T in [n] the following holds. The random bit B(T)
obtained by selecting at random a vector x in X, and computing the
mod-2 sum of its T-coordinates, has bias at most...
