Abstract
The pbiased Homogeneous rLin problem (HomrLin_p) is the following: given a homogeneous system of rvariable 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., Max3Lin, 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 HomrLin problem as well. In this work, we explore the approximability of the HomrLin_p problem beyond the balanced setting (i.e., p ≠ 1/2), and investigate whether the (pbiased) random guessing algorithm is optimal for every p. Our results include the following:
 The HomrLin_p problem has no efficient 1/2 + 1/2 (1  2p)^{r2} + ε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 HomrLin_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 3query dictatorship test to the pbiased setting.
BibTeX  Entry
@InProceedings{ghoshal:LIPIcs.APPROX/RANDOM.2022.47,
author = {Ghoshal, Suprovat},
title = {{The Biased Homogeneous rLin Problem}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
pages = {47:147:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772495},
ISSN = {18688969},
year = {2022},
volume = {245},
editor = {Chakrabarti, Amit and Swamy, Chaitanya},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17169},
URN = {urn:nbn:de:0030drops171695},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.47},
annote = {Keywords: Biased Approximation Resistance, Constraint Satisfaction Problems}
}
Keywords: 

Biased Approximation Resistance, Constraint Satisfaction Problems 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) 
Issue Date: 

2022 
Date of publication: 

15.09.2022 