School of Mathematics

In the first half of the talk I will give a very compressed introduction into parts of Theoretical Distributed Computing from the point of view of mathematician. I will describe how to construct simplicial models whose combinatorics contains...

In this talk we first introduce a new "singularity-free" approach to the proof of Seidel's long exact sequence, including the fixed-point version. This conveniently generalizes to Dehn twists along Lagrangian submanifolds which are rank one...

Ramanujan graphs are optimal expander graphs, and their existence and construction have been the focus of much research during the last three decades. We prove that every bipartite Ramanujan graph has a $d$-covering which is also Ramanujan. This...

Let $f$ be a polynomial of degree $d$ in $n$ variables over a finite field $\mathbb{F}$. The polynomial is said to be unbiased if the distribution of $f(x)$ for a uniform input $x \in \mathbb{F}^n$ is close to the uniform distribution over $\mathbb...

A theorem of Borel's asserts that for any positive real number $V$, there are at most finitely many arithmetic lattices in ${\rm PSL}_2({\mathbb C})$ of covolume at most $V$, or equivalently at most finitely many arithmetic hyperbolid $3$-orbifolds...

Joint work with Oded Goldreich. We prove that random $n$-by-$n$ Toeplitz matrices over $GF(2)$ have rigidity $\Omega(n^3/(r^2 \log n))$ for rank $r > \sqrt{n}$, with high probability. This improves, for $r = o(n / \log n \log\log n)$, over the $...

We will start with presenting the basic notions of (co)homomology of simplical complexes (which requires only basic linear algebra over the field of order 2) and then we will indicate its relevance for several topics in computer science and...

We introduce a method for proving lower bounds on the efficacy of semidefinite programming (SDP) relaxations for combinatorial problems. In particular, we show that the cut, TSP, and stable set polytopes on $n$-vertex graphs are not the linear image...

Higher-order Fourier analysis is a powerful tool that can be used to analyse the densities of linear systems (such as arithmetic progressions) in subsets of Abelian groups. We are interested in the group $\mathbb{F}_p^n$, for fixed $p$ and large $n$...

Following the revolutionary work of Thurston and Perelman, the topology of 3-manifolds is deeply intertwined with their geometry. In particular, hyperbolic geometry, the non-Euclidean geometry of constant negative curvature, plays a central role. In...