Yijia Chen (陈翌佳), Graphs of bounded shrub-depth, through a logic lens
Zoom ID: 869 4632 6610 (ibsdimag)Shrub-depth is a graph invariant often considered as an extension of tree-depth to dense graphs. In this talk I will explain our recent proofs of two results about graphs of bounded shrub-depth. Every graph property definable in monadic-second order logic, e.g., 3-colorability, can be evaluated by Boolean circuits of constant depth and polynomial size, whose …