Inapproximability results for the minimum integral solution problem with preprocessing overℓ∞norm

M. Ajtai, Generating hard instances of lattice problems, in: Proc. of the 28th Annual ACM Symposium on Theory of Computing, 1996, pp. 99–108. M. Alekhnovich, S. Khot, G. Kindler, N. Vishnoi, Hardness of approximating the closest vector problem with pre-processing, in: Proc. 46th IEEE Symposium on FOCS, 2005, pp. 216–225. S. Arora, Probabilistic checking of proofs and the hardness of approximation problems, Ph.D. Thesis, UC Berkeley, 1994. Arora, 1997, The hardness of approximate optima in lattices, codes, and systems of linear equations, Journal of Computer and System Sciences, 54, 317, 10.1006/jcss.1997.1472 Ausiello, 1995, Approximation solutions of NP-optimization problems, Theoretical Computer Science, 150, 1, 10.1016/0304-3975(94)00291-P M. Bellare, S. Goldwasser, C. Lund, A. Russel, Efficient Probabilistically Checkable Proofs with Applications to Approximation Problems, in: Proc. 25th ACM Symp. on Theory of Computing, 1993, pp. 294–304. Bollobás, 1986 Bruck, 1990, The hardness of decoding linear codes with preprocessing, IEEE Transactions on Information Theory, 36, 381, 10.1109/18.52484 Chen, 2006, The hardness of the closest vector problem with preprocessing over ℓ∞ norm, IEEE Transactions on Information Theory, 52, 4603, 10.1109/TIT.2006.881835 Chen, 2008, An improved lower bound for approximating minimum GCD multiplier in ℓ∞ norm (GCDM∞), Theoretical Computer Science, 396, 1, 10.1016/j.tcs.2007.09.030 Dinur, 2000, Approximating SV P∞ to within almost-polynomial factors is NP-hard, 1767 Dinur, 2003, Approximating CVP to within almost-polynomial factors is NP-hard, Combinatorica, 23, 205, 10.1007/s00493-003-0019-y Feige, 1996, Interactive proofs and the hardness of approximating cliques, Journal of ACM, 43, 268, 10.1145/226643.226652 Feige, 2004, The inapproximability of lattice and coding problems with preprocessing, Journal of Computer and System Sciences, 69, 45, 10.1016/j.jcss.2004.01.002 Garey, 1979 Lobstein, 1990, The hardness of solving subset sum with preprocessing, IEEE Transaction on Information Theory, 36, 943, 10.1109/18.53763 Micciancio, 2001, The hardness of the closest vector problem with preprocessing, IEEE Transaction on Information Theory, 47, 1212, 10.1109/18.915688 Micciancio, 2002 Regev, 2003, Improved inapproximability of lattice and coding problem with preprocessing, vol. 18, 363 O. Regev, R. Rosen, Lattice problems and norm embeddings, in: Proc. of STOC, 2006.