School of Mathematics

Choiceless Polynomial Time

Ben Rossman

The choiceless computation model of Blass, Gurevich and Shelah (1999, 2002) is an algorithmic framework for computing isomorphism-invariant properties of unordered structures. Machines in this model have the power of parallel execution, but lack...

In various applications, one is given the advice or predictions of several classifiers of unknown reliability, over multiple questions or queries. This scenario is different from standard supervised learning where classifier accuracy can be assessed...

An improved sunflower bound.

Jiapeng Zhang

A sunflower with $r$ petals is a collection of $r$ sets so that the intersection of each pair is equal to the intersection of all. Erdos and Rado in 1960 proved the sunflower lemma: for any fixed $r$, any family of sets of size $w$, with at least...