Luca Trevisan

We prove an extremal combinatorial result regarding

the fraction of satisfiable clauses in boolean CNF

formulae enjoying a locally checkable property, thus

solving a problem that has been open for several years.

We then generalize the problem to arbitrary constraint

satisfaction ...
more >>>

Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami

We study the complexity of Boolean constraint satisfaction problems (CSPs) when the assignment must have Hamming weight in some congruence class modulo $M$, for various choices of the modulus $M$. Due to the known classification of tractable Boolean CSPs, this mainly reduces to the study of three cases: 2SAT, HornSAT, ... more >>>

Abhibhav Garg, Rafael Mendes de Oliveira, Akash Sengupta

We prove a robust generalization of a Sylvester-Gallai type theorem for quadratic polynomials, generalizing the result in [S'20].

More precisely, given a parameter $0 < \delta \leq 1$ and a finite collection $\mathcal{F}$ of irreducible and pairwise independent polynomials of degree at most 2, we say that $\mathcal{F}$ is a ...
more >>>