4 Search Results for "Shparlinski, Igor E."


Document
Sets of Linear Forms Which Are Hard to Compute

Authors: Michael Kaminski and Igor E. Shparlinski

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


Abstract
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).

Cite as

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
Optimal Quantum Algorithm for Polynomial Interpolation

Authors: Andrew M. Childs, Wim van Dam, Shih-Han Hung, and Igor E. Shparlinski

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


Abstract
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.

Cite as

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
Subset Sum in the Absence of Concentration

Authors: Per Austrin, Petteri Kaski, Mikko Koivisto, and Jesper Nederlof

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)


Abstract
We study the exact time complexity of the Subset Sum problem. Our focus is on instances that lack additive structure in the sense that the sums one can form from the subsets of the given integers are not strongly concentrated on any particular integer value. We present a randomized algorithm that runs in O(2^0.3399nB^4) time on instances with the property that no value can arise as a sum of more than B different subsets of the n given integers.

Cite as

Per Austrin, Petteri Kaski, Mikko Koivisto, and Jesper Nederlof. Subset Sum in the Absence of Concentration. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 48-61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{austrin_et_al:LIPIcs.STACS.2015.48,
  author =	{Austrin, Per and Kaski, Petteri and Koivisto, Mikko and Nederlof, Jesper},
  title =	{{Subset Sum in the Absence of Concentration}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{48--61},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.48},
  URN =		{urn:nbn:de:0030-drops-49034},
  doi =		{10.4230/LIPIcs.STACS.2015.48},
  annote =	{Keywords: subset sum, additive combinatorics, exponential-time algorithm, homomorphic hashing, Littlewood--Offord problem}
}
Document
Bounds on the Fourier Coefficients of the Weighted Sum Function

Authors: Igor E. Shparlinski

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


Abstract
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.

Cite as

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}
}
  • Refine by Author
  • 3 Shparlinski, Igor E.
  • 1 Austrin, Per
  • 1 Childs, Andrew M.
  • 1 Hung, Shih-Han
  • 1 Kaminski, Michael
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Algebraic complexity theory

  • Refine by Keyword
  • 1 Fourier coefficients
  • 1 Linear algorithms
  • 1 Littlewood--Offord problem
  • 1 Quantum algorithms
  • 1 additive combinatorics
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2006
  • 1 2015
  • 1 2016
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail