Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-012 | 3rd February 2026 13:46

Perfectly Satisfiable Systems of Linear Equations and Fixed Weight Solutions

RSS-Feed




TR26-012
Authors: Johan Håstad
Publication: 3rd February 2026 13:46
Downloads: 59
Keywords: 


Abstract:

We study systems of linear equations modulo two in $n$ variables
with three variables in each equation. We assume that the system has
a solution with $pn$ variables taking the value 1 for some value
$00$ it is hard to find a solution
of the same weight that satisfies at least a fraction
$c_p +\delta$ of the equations. The constant $c_p$ is
upper bounded by $.9$ for any value of $p$.



ISSN 1433-8092 | Imprint