Mar

08

2021

### Computer Science/Discrete Mathematics Seminar I

Strong refutation of semi-random Boolean CSPs

11:15am|Remote Access - see Zoom link below

For a fixed integer k > 1, the Boolean k-XOR problem consists of a system of linear equations mod 2 with each equation involving exactly k variables. We give an algorithm to strongly refute *semi-random* instances of the Boolean k-XOR problem on n...