We study pairs of families ${\cal A},{\cal B}\subseteq 2^{\{1,\ldots,r\}}$ such that $|A\cap B|\in L$ for any $A\in{\cal A}$, $B\in{\cal B}$. We are interested in the maximal product $|{\cal A}|\cdot|{\cal B}|$, given $r$ and $L$. We give asymptotically optimal bounds for $L$ containing only elements of $smore >>>

Razborov~\cite{Razborov96} recently proved that polynomial calculus proofs of the pigeonhole principle $PHP_n^m$ must have degree at least $\ceiling{n/2}+1$ over any field. We present a simplified proof of the same result. The main idea of our proof is the same as in the original proof of Razborov: we want to describe ... more >>>

We introduce the model of conservative one-way multiparty complexity and prove lower and upper bounds on the complexity of pointer jumping. The pointer jumping function takes as its input a directed layered graph with a starting node and layers of nodes, and a single edge from each node to one ... more >>>

We prove an unexpected upper bound on a communication game proposed by Jeff Edmonds and Russell Impagliazzo as an approach for proving lower bounds for time-space tradeoffs for branching programs. Our result is based on a generalization of a construction of Erdos, Frankl and Rodl of a large 3-hypergraph with ... more >>>