Seminars

Various motivations recently led Mendel and Naor, Hatami and Kalai to study functions in tail spaces - i.e. function all of whose low level Fourier coefficients vanish. I will discuss the questions and conjectures that they posed and our recent work...

We provide a simple proof of the Rota--Heron--Welsh conjecture for matroids realizable as c-arrangements in the sense of Goresky--MacPherson: we prove that the coefficients of the characteristic polynomial of the associated matroids form log-concave...

Given a $k$-edge-connected graph $G = (V,E)$, a spanning tree $T$ is $\alpha$-thin w.r.t. $G$, if for any $S \subset V$, $|T(S,V - S)| \leq \alpha.|E(S,V - S)|$. The thin tree conjecture asserts that for a sufficiently large $k$ (independent of size...

We compare methods of computing inverses of matrices over division rings. The most direct way is via Cohn's theory of full matrices, which was improved by Malcolmson, Schofield, and Westreich. But it is simpler to work with finite dimensional...

We prove an $\omega(\log n)$ lower bound on the conondeterministic communication complexity of the Clique vs. Independent Set problem introduced by Yannakakis (STOC 1988, JCSS 1991). As a corollary, this implies superpolynomial lower bounds for the...

The log-concavity conjecture predicts that the coefficients of the chromatic (characteristic) polynomial of a matroid form a log-concave sequence. The known proof for realizable matroids uses algebraic geometry in an essential way, and the...

A 2-server Private Information Retrieval (PIR) scheme allows a user to retrieve the $i$'th bit of an $n$-bit database replicated among two servers (which do not communicate) while not revealing any information about $i$ to either server. The privacy...

Given a $k$-dimensional linear subspace, consider the problem of approximating it (with respect to the spectral norm) in terms of another subspace spanned by the indicators of a $k$-partition of the coordinates. This is known as the spectral...

We introduce an abstract model of computation corresponding to an experiment in which identical, non-interacting bosons are sent through a non-adaptive linear circuit before being measured. We show that despite the very limited nature of the model...

We introduce an abstract model of computation corresponding to an experiment in which identical, non-interacting bosons are sent through a non-adaptive linear circuit before being measured. We show that despite the very limited nature of the model...