The firefighter problem is a monotone dynamic process in graphs
that can be viewed as modeling the use of a limited supply of
vaccinations to stop the spread of an epidemic. In more detail, a
fire spreads through a graph, from burning vertices to...
Let $f(x_1,...,x_n)$ be a low degree polynomial over $F_p$. I
will prove that there always exists a small set $S$ of variables,
such that `most` Fourier coefficients of $f$ contain some variable
from the set $S$. As an application, we will get a...
In our work we study the structure of polynomials of degree
three and four that have high bias or high Gowers norm, over
arbitrary prime fields. In particular we obtain the following
results.
We give a canonical representation for degree three or...
Locally decodable codes are error-correcting codes that admit
efficient decoding algorithms, that can recover any bit of the
original message by looking at only a small number of locations of
a corrupted codeword. The tradeoff between the rate of...
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$.
