Dear all, the DFG Research Unit ADYN invites you to their next online seminar session on Zoom: *Monday, April 7th, 17:00 CEST*. Link: https://rwth.zoom-x.de/j/68837156442?pwd=H4OW7bUYYAMXSPiqvxXuEMuTTmk7VY.1 Meeting-ID: 688 3715 6442 Kenncode: 593098 The following talks will be given: (1) "Constraint Satisfaction Problems with Advice" by Suprovat Ghoshal (Indiana University) (2) "A Combinatorial Approach to Chernoff Bounds" by William Kuszmaul (Carnegie Mellon University) Abstracts: (1) We initiate the study of algorithms for Constraint Satisfaction Problems (CSPs) with ML oracle advice. We introduce two models of advice and then design approximation algorithms for several fundamental CSPs, such as Max Cut, Max 2-Lin, and Max 3-Lin in these models. In particular, we show the following. 1. For Max-Cut and Max 2-Lin, we design an algorithm that yields near-optimal solutions when the average degree is larger than a threshold degree, which only depends on the amount of advice and is independent of the instance size. We also give an algorithm for nearly satisfiable Max 3-Lin instances with quantitatively similar guarantees. 2. Further, we provide impossibility results for algorithms in these models. In particular, under standard complexity assumptions, we show that Max 3-Lin is still $1/2 + \eta$ hard to approximate given access to advice, when there are no assumptions on the instance degree distribution. Additionally, we also show that Max 4-Lin is $1/2 + \eta$ hard to approximate even when the average degree of the instance is linear in the number of variables. This is joint work with Konstantin Makarychev and Yury Makarychev. (2) - For more information on ADYN and the seminar series, visit our website using the link https://adyn.informatik.rwth-aachen.de/ . Best, Tim