Room 327

Solving a linear system with a global congruency constraint

Venkat Guruswami

CMU

We consider the following problem: Given input an affine subspace H of F_2^n (F_2 being the field of two elements), is there a vector in H whose Hamming weight is in a specific congruency class modulo M? We classify for which moduli M the problem is polytime solvable and for which it is (likely) not. (We encourage the audience to guess the answer for some small cases like M=3,4,6,9,15.) The question is related to the sparsity of polynomials representing the OR function modulo M, which in turn has some connections to coding theory.

Our study of this question is part of a broader investigation into the complexity of Boolean constraint satisfaction problems with a global congruency constraint, for which we obtain an (almost) full classification of the easy vs. hard cases. The talk will focus on the above linear systems question, and mention some other cases depending on time.

Joint work with Joshua Brakensiek and Sivakanth Gopi.