3 Search Results for "Huang, Neng"

Document
DOI: 10.4230/LIPIcs.TQC.2023.11
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
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.58
On the Approximability of Presidential Type Predicates

Authors: Neng Huang and Aaron Potechin

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Abstract
Given a predicate P: {-1, 1}^k → {-1, 1}, let CSP(P) be the set of constraint satisfaction problems whose constraints are of the form P. We say that P is approximable if given a nearly satisfiable instance of CSP(P), there exists a probabilistic polynomial time algorithm that does better than a random assignment. Otherwise, we say that P is approximation resistant. In this paper, we analyze presidential type predicates, which are balanced linear threshold functions where all of the variables except the first variable (the president) have the same weight. We show that almost all presidential type predicates P are approximable. More precisely, we prove the following result: for any δ₀ > 0, there exists a k₀ such that if k ≥ k₀, δ ∈ (δ₀,1 - 2/k], and {δ}k + k - 1 is an odd integer then the presidential type predicate P(x) = sign({δ}k{x₁} + ∑_{i = 2}^{k} {x_i}) is approximable. To prove this, we construct a rounding scheme that makes use of biases and pairwise biases. We also give evidence that using pairwise biases is necessary for such rounding schemes.
Cite as

Neng Huang and Aaron Potechin. On the Approximability of Presidential Type Predicates. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 58:1-58:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.APPROX/RANDOM.2020.58,
  author =	{Huang, Neng and Potechin, Aaron},
  title =	{{On the Approximability of Presidential Type Predicates}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{58:1--58:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.58},
  URN =		{urn:nbn:de:0030-drops-126612},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.58},
  annote =	{Keywords: constraint satisfaction problems, approximation algorithms, presidential type predicates}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.45
On the Decision Tree Complexity of String Matching

Authors: Xiaoyu He, Neng Huang, and Xiaoming Sun

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
String matching is one of the most fundamental problems in computer science. A natural problem is to determine the number of characters that need to be queried (i.e. the decision tree complexity) in a string in order to decide whether this string contains a certain pattern. Rivest showed that for every pattern p, in the worst case any deterministic algorithm needs to query at least n-|p|+1 characters, where n is the length of the string and |p| is the length of the pattern. He further conjectured that this bound is tight. By using the adversary method, Tuza disproved this conjecture and showed that more than one half of binary patterns are evasive, i.e. any algorithm needs to query all the characters (see Section 1.1 for more details). In this paper, we give a query algorithm which settles the decision tree complexity of string matching except for a negligible fraction of patterns. Our algorithm shows that Tuza's criteria of evasive patterns are almost complete. Using the algebraic approach of Rivest and Vuillemin, we also give a new sufficient condition for the evasiveness of patterns, which is beyond Tuza's criteria. In addition, our result reveals an interesting connection to Skolem's Problem in mathematics.
Cite as

Xiaoyu He, Neng Huang, and Xiaoming Sun. On the Decision Tree Complexity of String Matching. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 45:1-45:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{he_et_al:LIPIcs.ESA.2018.45,
  author =	{He, Xiaoyu and Huang, Neng and Sun, Xiaoming},
  title =	{{On the Decision Tree Complexity of String Matching}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{45:1--45:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.45},
  URN =		{urn:nbn:de:0030-drops-95082},
  doi =		{10.4230/LIPIcs.ESA.2018.45},
  annote =	{Keywords: String Matching, Decision Tree Complexity, Boolean Function, Algebraic Method}
}
  • Refine by Author
  • 2 Huang, Neng
  • 1 Bassirian, Roozbeh
  • 1 Fefferman, Bill
  • 1 He, Xiaoyu
  • 1 Marwaha, Kunal
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Oracles and decision trees
  • 1 Theory of computation → Quantum complexity theory
  • 1 Theory of computation → Rounding techniques

  • Refine by Keyword
  • 1 Algebraic Method
  • 1 Boolean Function
  • 1 Decision Tree Complexity
  • 1 QCMA
  • 1 String Matching
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2018
  • 1 2020
  • 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact