Master’s Thesis Presentation • Algorithms and Complexity — Monotonicity Testing for Boolean Functions over Graph Products

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.

To joint this master’s thesis presentation on Zoom, please go to https://us02web.zoom.us/j/81968244835.