The Sensitivity Conjecture, posed in 1994, states that the fundamental measures known as the sensitivity and block sensitivity of a Boolean function $f$, $s(f)$ and $bs(f)$ respectively, are polynomially related. It is known that $bs(f)$ is polynomially related to important measures in computer science including the decision-tree depth, polynomial degree, ... more >>>

We study the covering complexity of constraint satisfaction problems (CSPs). The covering number of a CSP instance C, denoted $\nu(C)$, is the smallest number of assignments to the variables, such that each constraint is satisfied by at least one of the assignments. This covering notion describes situations in which we ... more >>>

We study the $\leadingones$ game, a Mastermind-type guessing game first
regarded as a test case in the complexity theory of randomized search
heuristics. The first player, Carole, secretly chooses a string $z \in \{0,1\}^n$ and a
permutation $\pi$ of $[n]$.
The goal of the second player, Paul, is to ... more >>>