2026-07-22T14:20:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17169 2024-03-06T10:59:09Z ddc:004 open_access

The Biased Homogeneous r-Lin Problem Ghoshal, Suprovat Biased Approximation Resistance Constraint Satisfaction Problems The p-biased Homogeneous r-Lin problem (Hom-r-Lin_p) is the following: given a homogeneous system of r-variable equations over m{F}₂, the goal is to find an assignment of relative weight p that satisfies the maximum number of equations. In a celebrated work, Håstad (JACM 2001) showed that the unconstrained variant of this i.e., Max-3-Lin, is hard to approximate beyond a factor of 1/2. This is also tight due to the naive random guessing algorithm which sets every variable uniformly from {0,1}. Subsequently, Holmerin and Khot (STOC 2004) showed that the same holds for the balanced Hom-r-Lin problem as well. In this work, we explore the approximability of the Hom-r-Lin_p problem beyond the balanced setting (i.e., p ≠ 1/2), and investigate whether the (p-biased) random guessing algorithm is optimal for every p. Our results include the following: - The Hom-r-Lin_p problem has no efficient 1/2 + 1/2 (1 - 2p)^{r-2} + ε-approximation algorithm for every p if r is even, and for p ∈ (0,1/2] if r is odd, unless NP ⊂ ∪_{ε>0}DTIME(2^{n^ε}). - For any r and any p, there exists an efficient 1/2 (1 - e^{-2})-approximation algorithm for Hom-r-Lin_p. We show that this is also tight for odd values of r (up to o_r(1)-additive factors) assuming the Unique Games Conjecture. Our results imply that when r is even, then for large values of r, random guessing is near optimal for every p. On the other hand, when r is odd, our results illustrate an interesting contrast between the regimes p ∈ (0,1/2) (where random guessing is near optimal) and p → 1 (where random guessing is far from optimal). A key technical contribution of our work is a generalization of Håstad’s 3-query dictatorship test to the p-biased setting. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Suprovat Ghoshal 2022 Is Part Of LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2022.47 urn:nbn:de:0030-drops-171695 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.47 eng https://creativecommons.org/licenses/by/4.0/legalcode