CSDM Seminars

Infinite continuous graphs emerge naturally in the geometric analysis of closed planar sets which cannot be presented as countable union of convex sets. The classification of such graphs leads in turn to properties of large classes of real functions...

A perfect matching in a $k$-uniform hypergraph $H= (V, E)$ on $n$ vertices is a set of $n/k$ disjoint edges of $H$, while a fractional perfect matching in $H$ is a function $w:E \to [0,1]$ such that for each $v \in V$ we have $\sum_{e \ni v}w(e) = 1...

We give an elementary proof of a generalization of Bourgain and Tzafriri's Restricted Invertibility Theorem, which says roughly that any matrix with columns of unit length and bounded operator norm has a large coordinate subspace on which it is well...

Let H be a fixed graph with h vertices. The graph removal lemma states that every graph on n vertices with o(n^h) copies of H can be made H-free by removing o(n^2) edges. We give a new proof which avoids Szemeredi's regularity lemma and gives a...

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 derandomized...

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. 1. We give a canonical representation for degree three or...

A (q,k,t)-design matrix is an m x n matrix whose pattern of zeros/non-zeros satisfies the following design-like condition: each row has at most q non-zeros, each column has at least k non-zeros and the supports of every two columns intersect in at...