Search Results

Documents authored by Matsliah, Arie

Document
DOI: 10.4230/LIPIcs.FSTTCS.2010.145
New Results on Quantum Property Testing

Authors: Sourav Chakraborty, Eldar Fischer, Arie Matsliah, and Ronald de Wolf

Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)

Abstract
We present several new examples of speed-ups obtainable by quantum algorithms in the context of property testing. First, motivated by sampling algorithms, we consider probability distributions given in the form of an oracle $f:[n]\to[m]$. Here the probability $P_f(j)$ of an outcome $j$ in $[m]$ is the fraction of its domain that $f$ maps to $j$. We give quantum algorithms for testing whether two such distributions are identical or $epsilon$-far in $L_1$-norm. Recently, Bravyi, Hassidim, and Harrow showed that if $P_f$ and $P_g$ are both unknown (i.e., given by oracles $f$ and $g$), then this testing can be done in roughly $sqrt{m}$ quantum queries to the functions. We consider the case where the second distribution is known, and show that testing can be done with roughly $m^{1/3}$ quantum queries, which we prove to be essentially optimal. In contrast, it is known that classical testing algorithms need about $m^{2/3}$ queries in the unknown-unknown case and about $sqrt{m}$ queries in the known-unknown case. Based on this result, we also reduce the query complexity of graph isomorphism testers with quantum oracle access. While those examples provide polynomial quantum speed-ups, our third example gives a much larger improvement (constant quantum queries vs polynomial classical queries) for the problem of testing periodicity, based on Shor's algorithm and a modification of a classical lower bound by Lachish and Newman. This provides an alternative to a recent constant-vs-polynomial speed-up due to Aaronson.
Cite as

Sourav Chakraborty, Eldar Fischer, Arie Matsliah, and Ronald de Wolf. New Results on Quantum Property Testing. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 145-156, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.FSTTCS.2010.145,
  author =	{Chakraborty, Sourav and Fischer, Eldar and Matsliah, Arie and de Wolf, Ronald},
  title =	{{New Results on Quantum Property Testing}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
  pages =	{145--156},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-23-1},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{8},
  editor =	{Lodaya, Kamal and Mahajan, Meena},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.145},
  URN =		{urn:nbn:de:0030-drops-28603},
  doi =		{10.4230/LIPIcs.FSTTCS.2010.145},
  annote =	{Keywords: quantum algorithm, property testing}
}
Document
DOI: 10.4230/DagSemProc.09421.5
Learning Parities in the Mistake-Bound model

Authors: Harry Buhrman, David Garcia-Soriano, and Arie Matsliah

Published in: Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010)

Abstract
We study the problem of learning parity functions that depend on at most $k$ variables ($k$-parities) attribute-efficiently in the mistake-bound model. We design a simple, deterministic, polynomial-time algorithm for learning $k$-parities with mistake bound $O(n^{1-frac{c}{k}})$, for any constant $c > 0$. This is the first polynomial-time algorithms that learns $omega(1)$-parities in the mistake-bound model with mistake bound $o(n)$. Using the standard conversion techniques from the mistake-bound model to the PAC model, our algorithm can also be used for learning $k$-parities in the PAC model. In particular, this implies a slight improvement on the results of Klivans and Servedio cite{rocco} for learning $k$-parities in the PAC model. We also show that the $widetilde{O}(n^{k/2})$ time algorithm from cite{rocco} that PAC-learns $k$-parities with optimal sample complexity can be extended to the mistake-bound model.
Cite as

Harry Buhrman, David Garcia-Soriano, and Arie Matsliah. Learning Parities in the Mistake-Bound model. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 9421, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{buhrman_et_al:DagSemProc.09421.5,
  author =	{Buhrman, Harry and Garcia-Soriano, David and Matsliah, Arie},
  title =	{{Learning Parities in the Mistake-Bound model}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9421},
  editor =	{Manindra Agrawal and Lance Fortnow and Thomas Thierauf and Christopher Umans},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09421.5},
  URN =		{urn:nbn:de:0030-drops-24178},
  doi =		{10.4230/DagSemProc.09421.5},
  annote =	{Keywords: Attribute-efficient learning, parities, mistake-bound}
}
Document
DOI: 10.4230/LIPIcs.STACS.2009.1811
Hardness and Algorithms for Rainbow Connectivity

Authors: Sourav Chakraborty, Eldar Fischer, Arie Matsliah, and Raphael Yuster

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
An edge-colored graph $G$ is {\em rainbow connected} if any two vertices are connected by a path whose edges have distinct colors. The {\em rainbow connectivity} of a connected graph $G$, denoted $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow connected. In addition to being a natural combinatorial problem, the rainbow connectivity problem is motivated by applications in cellular networks. In this paper we give the first proof that computing $rc(G)$ is NP-Hard. In fact, we prove that it is already NP-Complete to decide if $rc(G)=2$, and also that it is NP-Complete to decide whether a given edge-colored (with an unbounded number of colors) graph is rainbow connected. On the positive side, we prove that for every $\epsilon >0$, a connected graph with minimum degree at least $\epsilon n$ has bounded rainbow connectivity, where the bound depends only on $\epsilon$, and the corresponding coloring can be constructed in polynomial time. Additional non-trivial upper bounds, as well as open problems and conjectures are also presented.
Cite as

Sourav Chakraborty, Eldar Fischer, Arie Matsliah, and Raphael Yuster. Hardness and Algorithms for Rainbow Connectivity. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 243-254, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.STACS.2009.1811,
  author =	{Chakraborty, Sourav and Fischer, Eldar and Matsliah, Arie and Yuster, Raphael},
  title =	{{Hardness and Algorithms for Rainbow Connectivity}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{243--254},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1811},
  URN =		{urn:nbn:de:0030-drops-18115},
  doi =		{10.4230/LIPIcs.STACS.2009.1811},
  annote =	{Keywords: }
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact