Document

**Published in:** LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

We present a uniform description of sets of m linear forms in n variables over the field of rational numbers whose computation requires m(n - 1) additions. Our result is based on bounds on the height of the annihilating polynomials in the Perron theorem and an effective form of the Lindemann-Weierstrass theorem which is due to Sert (1999).

Michael Kaminski and Igor E. Shparlinski. Sets of Linear Forms Which Are Hard to Compute. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 66:1-66:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kaminski_et_al:LIPIcs.MFCS.2021.66, author = {Kaminski, Michael and Shparlinski, Igor E.}, title = {{Sets of Linear Forms Which Are Hard to Compute}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {66:1--66:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.66}, URN = {urn:nbn:de:0030-drops-145065}, doi = {10.4230/LIPIcs.MFCS.2021.66}, annote = {Keywords: Linear algorithms, additive complexity, effective Perron theorem, effective Lindemann-Weierstrass theorem} }

Document

**Published in:** LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

We consider the number of quantum queries required to determine the coefficients of a degree-d polynomial over F_q. A lower bound shown independently by Kane and Kutin and by Meyer and Pommersheim shows that d/2 + 1/2 quantum queries are needed to solve this problem with bounded error, whereas an algorithm of Boneh and Zhandry shows that d quantum queries are sufficient. We show that the lower bound is achievable: d/2 + 1/2 quantum queries suffice to determine the polynomial with bounded error. Furthermore, we show that d/2 + 1 queries suffice to achieve probability approaching 1 for large q. These upper bounds improve results of Boneh and Zhandry on the insecurity of cryptographic protocols against quantum attacks. We also show that our algorithm’s success probability as a function of the number of queries is precisely optimal. Furthermore, the algorithm can be implemented with gate complexity poly(log(q)) with negligible decrease in the success probability. We end with a conjecture about the quantum query complexity of multivariate polynomial interpolation.

Andrew M. Childs, Wim van Dam, Shih-Han Hung, and Igor E. Shparlinski. Optimal Quantum Algorithm for Polynomial Interpolation. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 16:1-16:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{childs_et_al:LIPIcs.ICALP.2016.16, author = {Childs, Andrew M. and van Dam, Wim and Hung, Shih-Han and Shparlinski, Igor E.}, title = {{Optimal Quantum Algorithm for Polynomial Interpolation}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {16:1--16:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.16}, URN = {urn:nbn:de:0030-drops-62985}, doi = {10.4230/LIPIcs.ICALP.2016.16}, annote = {Keywords: Quantum algorithms, query complexity, polynomial interpolation, finite fields} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

We estimate Fourier coefficients of a Boolean function
which has recently been introduced in the study of read-once
branching programs. Our bound implies that this function
has an asymptotically ``flat'' Fourier spectrum and thus
implies several lower bounds of its various complexity
measures.

Igor E. Shparlinski. Bounds on the Fourier Coefficients of the Weighted Sum Function. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{shparlinski:DagSemProc.06111.5, author = {Shparlinski, Igor E.}, title = {{Bounds on the Fourier Coefficients of the Weighted Sum Function}}, booktitle = {Complexity of Boolean Functions}, pages = {1--9}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {6111}, editor = {Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.5}, URN = {urn:nbn:de:0030-drops-6171}, doi = {10.4230/DagSemProc.06111.5}, annote = {Keywords: Fourier coefficients, congruences, average sensitivity, decision tree} }