A "proof assistant" is a software package comprising a validity
checker for proofs in a particular logic, accompanied by
semi-decision procedures called "tactics" that assist the
mathematician in filling in the easy parts of the proofs. I
will...
The classical Dvoretzky theorem asserts that for every integer
k>1 and every target distortion D>1 there exists an integer
n=n(k,D) such that any
n-dimensional normed space contains a subspace of dimension k that
embeds into Hilbert space with...
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 → [0, 1] such that for each v ∈ V we
have
e∋v w(e) = 1. Given n ≥ 3 and 3 ≤ k ≤ n...
A permutation pi=(pi_{1},...,pi_{n}) is consecutive 123-avoiding
if there is no sequence of the form pi_i pi_{i+1} pi_{i+2}. More
generally, for S a collection of permutations on m+1 elements, this
definition extends to define consecutive S...
The famous theorem of Szemerédi says that for any natural number
$k$ and any $a > 0$ there exists n such that if $N >= n$ then
any subset $A$ of the set $[N] ={1,2,...,N}$ of size $|A| >= a$
$N$ contains an arithmetic progression of length $k$. We...
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...
