Talk information

Date: Sunday, November 17, 2024
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Gregory Gutin (Royal Holloway University of London)
Title: Lower bounds for weighted max cut and bisection

Abstract:

Lower bounds for unweighted max cut and bisection have been studied by many researchers. There has not been much done for their weighted counterparts. We shall discuss new lower bounds for weighted max cut and bisection. Some of them generalize and/or improve known lower bounds for unweighted max cut and bisection. Our derivations include some new approaches, which may be of independent interest. For example, Kallaugher and Parekh used one of them in their FOCS 2022 paper on quantum and classical streaming complexity of quantum and classical max cut.

Joint work with Stefanie Gerke, Anders Yeo and Yacong Zhou.