More on average case vs approximation complexity

Abstract

We consider the problem to determine the maximal number of satisfiable equations in a linear system chosen at random. We make several plausible conjectures about the average case hardness of this problem for some natural distributions on the instances, and relate them to several interesting questions in the theory of approximation algorithms and in cryptography. Namely we show that our conjectures imply the following facts: (1) Feige's hypothesis about the hardness of refuting a random 3CNF is true, which in turn implies inapproximability within a constant for several combinatorial problems, for which no NP-hardness of approximation is known. (2) It is hard to approximate the nearest codeword within factor n/sup 1 - /spl epsi//. (3) It is hard to estimate the rigidity of a matrix. More exactly, it is hard to distinguish between matrices of low rigidity and random ones. (4) There exists a secure public-key (probabilistic) cryptosystem, based on the intractability of decoding of random binary codes. Our conjectures are strong in that they assume cryptographic hardness: no polynomial algorithm can solve the problem on any non-negligible fraction of inputs. Nevertheless, to the best of our knowledge no efficient algorithms are currently known that refute any of our hardness conjectures.