Please note: This master’s thesis presentation will be given online.
Zhengkun Chen, Master’s candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Eric Blais
We establish a directed analogue of Chung and Tetali’s isoperimetric inequality for graph products. We use this inequality to obtain new bounds on the query complexity for testing monotonicity of Boolean-valued functions over products of general posets.