Document

**Published in:** LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Ajtai, Kumar and Sivakumar [Ajtai et al., 2001] gave the first 2^O(n) algorithm for solving the Shortest Vector Problem (SVP) on n-dimensional Euclidean lattices. The algorithm starts with N in 2^O(n) randomly chosen vectors in the lattice and employs a sieving procedure to iteratively obtain shorter vectors in the lattice, and eventually obtaining the shortest non-zero vector. The running time of the sieving procedure is quadratic in N. Subsequent works [Arvind and Joglekar, 2008; Blömer and Naewe, 2009] generalized the algorithm to other norms.
We study this problem for the special but important case of the l_infty norm. We give a new sieving procedure that runs in time linear in N, thereby improving the running time of the algorithm for SVP in the l_infty norm. As in [Ajtai et al., 2002; Blömer and Naewe, 2009], we also extend this algorithm to obtain significantly faster algorithms for approximate versions of the shortest vector problem and the closest vector problem (CVP) in the l_infty norm.
We also show that the heuristic sieving algorithms of Nguyen and Vidick [Nguyen and Vidick, 2008] and Wang et al. [Wang et al., 2011] can also be analyzed in the l_infty norm. The main technical contribution in this part is to calculate the expected volume of intersection of a unit ball centred at origin and another ball of a different radius centred at a uniformly random point on the boundary of the unit ball. This might be of independent interest.

Divesh Aggarwal and Priyanka Mukhopadhyay. Improved Algorithms for the Shortest Vector Problem and the Closest Vector Problem in the Infinity Norm. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 35:1-35:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{aggarwal_et_al:LIPIcs.ISAAC.2018.35, author = {Aggarwal, Divesh and Mukhopadhyay, Priyanka}, title = {{Improved Algorithms for the Shortest Vector Problem and the Closest Vector Problem in the Infinity Norm}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {35:1--35:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.35}, URN = {urn:nbn:de:0030-drops-99837}, doi = {10.4230/LIPIcs.ISAAC.2018.35}, annote = {Keywords: Lattice, Shortest Vector Problem, Closest Vector Problem, l\underlineinfty norm} }

Document

**Published in:** LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)

Let the randomized query complexity of a relation for error probability epsilon be denoted by R_epsilon(). We prove that for any relation f contained in {0,1}^n times R and Boolean function g:{0,1}^m -> {0,1}, R_{1/3}(f o g^n) = Omega(R_{4/9}(f).R_{1/2-1/n^4}(g)), where f o g^n is the relation obtained by composing f and g. We also show using an XOR lemma that R_{1/3}(f o (g^{xor}_{O(log n)})^n) = Omega(log n . R_{4/9}(f) . R_{1/3}(g))$, where g^{xor}_{O(log n)} is the function obtained by composing the XOR function on O(log n) bits and g.

Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, and Swagato Sanyal. A Composition Theorem for Randomized Query Complexity. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{anshu_et_al:LIPIcs.FSTTCS.2017.10, author = {Anshu, Anurag and Gavinsky, Dmitry and Jain, Rahul and Kundu, Srijita and Lee, Troy and Mukhopadhyay, Priyanka and Santha, Miklos and Sanyal, Swagato}, title = {{A Composition Theorem for Randomized Query Complexity}}, booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)}, pages = {10:1--10:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-055-2}, ISSN = {1868-8969}, year = {2018}, volume = {93}, editor = {Lokam, Satya and Ramanujam, R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.10}, URN = {urn:nbn:de:0030-drops-83967}, doi = {10.4230/LIPIcs.FSTTCS.2017.10}, annote = {Keywords: Query algorithms and complexity, Decision trees, Composition theorem, XOR lemma, Hardness amplification} }