Journal
COMPUTATIONAL COMPLEXITY
Volume 20, Issue 4, Pages 755-786Publisher
SPRINGER BASEL AG
DOI: 10.1007/s00037-011-0029-x
Keywords
Cryptographic primitives; hardness of approximation
Categories
Funding
- NSF [CCR 0205390]
- MIT NTT
Ask authors/readers for more resources
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: 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. It is hard to approximate the NEAREST CODEWORD within factor n(1-epsilon). 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. There exists a secure public-key (probabilistic) cryptosystem, based on the intractability of decoding of random binary codes.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available