Certificate complexity $(C(f ))$ is a fundamental measure of complexity of Boolean functions $f$
which counts the number of bits of an input that need to be known in order for the value of the
function to be determined. A certificate can be viewed as a partial assignment, or a ... more >>>

We study the two-party communication complexity of functions with large outputs, and show that the communication complexity can greatly vary depending on what output model is considered. We study a variety of output models, ranging from the open model, in which an external observer can compute the outcome, to the ... more >>>

We introduce and study Certificate Game complexity, a measure of complexity based on the probability of winning a game where two players are given inputs with different function values and are asked to output some index $i$ such that $x_i\neq y_i$, in a zero-communication setting.

We give upper and lower ... more >>>

Recently, using spectral techniques, H. Huang proved that every subgraph of the hypercube of dimension n induced on more than half the vertices has maximum degree at least the square root of n. Combined with some earlier work, this completed a proof of the sensitivity conjecture. In this work we ... more >>>

Does the information complexity of a function equal its communication complexity? We examine whether any currently known techniques might be used to show a separation between the two notions. Recently, Ganor et al. provided such a separation in the distributional setting for a specific input distribution ?. We show that ... more >>>

We show that almost all known lower bound methods for communication complexity are also lower bounds for the information complexity. In particular, we define a relaxed version of the partition bound of Jain and Klauck and prove that it lower bounds the information complexity of any function. Our relaxed partition ... more >>>

In communication complexity, two players each have an input and they wish to compute some function of the joint inputs. This has been the object of much study and a wide variety of lower bound methods have been introduced to address the problem of showing lower bounds on communication. Recently, ... more >>>

A very important problem in quantum communication complexity is to show that there is, or isn?t, an exponential gap between randomized and quantum complexity for a total function. There are currently no clear candidate functions for such a separation; and there are fewer and fewer randomized lower bound techniques that ... more >>>

In model checking, program correctness on all inputs is verified
by considering the transition system underlying a given program.
In practice, the system can be intractably large.
In property testing, a property of a single input is verified
by looking at a small subset of that input.
We ... more >>>