We show that if DTIME[2^{O(n)}] is not included in DSPACE}[2^{o(n)}], then, for every set B in PSPACE, all strings x in B of length n can be represented by a string compressed(x) of length at most log (|B^{=n}|) + O(log n), such that a polynomial-time algorithm, given compressed(x), can distinguish ... more >>>

A fundamental fact in the analysis of randomized algorithm is that when $n$ balls are hashed into $n$ bins independently and uniformly at random, with high probability each bin contains at most $O(\log n / \log \log n)$ balls. In various applications, however, the assumption that a truly random hash ... more >>>

We present several variants of the sunflower conjecture of Erd\H{o}s and Rado and discuss the relations among them.

We then show that two of these conjectures (if true) imply negative answers to questions of Coppersmith and Winograd and Cohn et al. regarding possible approaches for obtaining fast matrix multiplication algorithms. ... more >>>