3 Search Results for "Huang, Yi"


Document
On the Power of Nonstandard Quantum Oracles

Authors: Roozbeh Bassirian, Bill Fefferman, and Kunal Marwaha

Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)


Abstract
We study how the choices made when designing an oracle affect the complexity of quantum property testing problems defined relative to this oracle. We encode a regular graph of even degree as an invertible function f, and present f in different oracle models. We first give a one-query QMA protocol to test if a graph encoded in f has a small disconnected subset. We then use representation theory to show that no classical witness can help a quantum verifier efficiently decide this problem relative to an in-place oracle. Perhaps surprisingly, a simple modification to the standard oracle prevents a quantum verifier from efficiently deciding this problem, even with access to an unbounded witness.

Cite as

Roozbeh Bassirian, Bill Fefferman, and Kunal Marwaha. On the Power of Nonstandard Quantum Oracles. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 11:1-11:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{bassirian_et_al:LIPIcs.TQC.2023.11,
  author =	{Bassirian, Roozbeh and Fefferman, Bill and Marwaha, Kunal},
  title =	{{On the Power of Nonstandard Quantum Oracles}},
  booktitle =	{18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)},
  pages =	{11:1--11:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-283-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{266},
  editor =	{Fawzi, Omar and Walter, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.11},
  URN =		{urn:nbn:de:0030-drops-183215},
  doi =		{10.4230/LIPIcs.TQC.2023.11},
  annote =	{Keywords: quantum complexity, QCMA, expander graphs, representation theory}
}
Document
Approximate Range Counting Under Differential Privacy

Authors: Ziyue Huang and Ke Yi

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)


Abstract
Range counting under differential privacy has been studied extensively. Unfortunately, lower bounds based on discrepancy theory suggest that large errors have to be introduced in order to preserve privacy: Essentially for any range space (except axis-parallel rectangles), the error has to be polynomial. In this paper, we show that by allowing a standard notion of geometric approximation where points near the boundary of the range may or may not be counted, the error can be reduced to logarithmic. Furthermore, our approximate range counting data structure can be used to solve the approximate nearest neighbor (ANN) problem and k-NN classification, leading to the first differentially private algorithms for these two problems with provable guarantees on the utility.

Cite as

Ziyue Huang and Ke Yi. Approximate Range Counting Under Differential Privacy. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.SoCG.2021.45,
  author =	{Huang, Ziyue and Yi, Ke},
  title =	{{Approximate Range Counting Under Differential Privacy}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{45:1--45:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.45},
  URN =		{urn:nbn:de:0030-drops-138441},
  doi =		{10.4230/LIPIcs.SoCG.2021.45},
  annote =	{Keywords: Differential Privacy, Approximate Range Counting}
}
Document
Network Construction with Ordered Constraints

Authors: Yi Huang, Mano Vikash Janardhanan, and Lev Reyzin

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


Abstract
In this paper, we study the problem of constructing a network by observing ordered connectivity constraints, which we define herein. These ordered constraints are made to capture realistic properties of real-world problems that are not reflected in previous, more general models. We give hardness of approximation results and nearly-matching upper bounds for the offline problem, and we study the online problem in both general graphs and restricted sub-classes. In the online problem, for general graphs, we give exponentially better upper bounds than exist for algorithms for general connectivity problems. For the restricted classes of stars and paths we are able to find algorithms with optimal competitive ratios, the latter of which involve analysis using a potential function defined over PQ-trees.

Cite as

Yi Huang, Mano Vikash Janardhanan, and Lev Reyzin. Network Construction with Ordered Constraints. 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. 34:1-34:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.FSTTCS.2017.34,
  author =	{Huang, Yi and Janardhanan, Mano Vikash and Reyzin, Lev},
  title =	{{Network Construction with Ordered Constraints}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{34:1--34: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.34},
  URN =		{urn:nbn:de:0030-drops-84090},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.34},
  annote =	{Keywords: subgraph connectivity, network construction, ordered connectivity constraints, PQ-trees}
}
  • Refine by Author
  • 1 Bassirian, Roozbeh
  • 1 Fefferman, Bill
  • 1 Huang, Yi
  • 1 Huang, Ziyue
  • 1 Janardhanan, Mano Vikash
  • Show More...

  • Refine by Classification
  • 1 Security and privacy → Formal methods and theory of security
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Quantum complexity theory

  • Refine by Keyword
  • 1 Approximate Range Counting
  • 1 Differential Privacy
  • 1 PQ-trees
  • 1 QCMA
  • 1 expander graphs
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2018
  • 1 2021
  • 1 2023

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