2 Search Results for "Chin, Wei-Ngan"

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.52
Lower Bounds for XOR of Forrelations

Authors: Uma Girish, Ran Raz, and Wei Zhan

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

Abstract
The Forrelation problem, first introduced by Aaronson [Scott Aaronson, 2010] and Aaronson and Ambainis [Scott Aaronson and Andris Ambainis, 2015], is a well studied computational problem in the context of separating quantum and classical computational models. Variants of this problem were used to give tight separations between quantum and classical query complexity [Scott Aaronson and Andris Ambainis, 2015]; the first separation between poly-logarithmic quantum query complexity and bounded-depth circuits of super-polynomial size, a result that also implied an oracle separation of the classes BQP and PH [Ran Raz and Avishay Tal, 2019]; and improved separations between quantum and classical communication complexity [Uma Girish et al., 2021]. In all these separations, the lower bound for the classical model only holds when the advantage of the protocol (over a random guess) is more than ≈ 1/√N, that is, the success probability is larger than ≈ 1/2 + 1/√N. This is unavoidable as ≈ 1/√N is the correlation between two coordinates of an input that is sampled from the Forrelation distribution, and hence there are simple classical protocols that achieve advantage ≈ 1/√N, in all these models. To achieve separations when the classical protocol has smaller advantage, we study in this work the xor of k independent copies of (a variant of) the Forrelation function (where k≪ N). We prove a very general result that shows that any family of Boolean functions that is closed under restrictions, whose Fourier mass at level 2k is bounded by α^k (that is, the sum of the absolute values of all Fourier coefficients at level 2k is bounded by α^k), cannot compute the xor of k independent copies of the Forrelation function with advantage better than O((α^k)/(N^{k/2})). This is a strengthening of a result of [Eshan Chattopadhyay et al., 2019], that gave a similar statement for k = 1, using the technique of [Ran Raz and Avishay Tal, 2019]. We give several applications of our result. In particular, we obtain the following separations: Quantum versus Classical Communication Complexity. We give the first example of a partial Boolean function that can be computed by a simultaneous-message quantum protocol with communication complexity polylog(N) (where Alice and Bob also share polylog(N) EPR pairs), and such that, any classical randomized protocol of communication complexity at most õ(N^{1/4}), with any number of rounds, has quasipolynomially small advantage over a random guess. Previously, only separations where the classical protocol has polynomially small advantage were known between these models [Dmitry Gavinsky, 2016; Uma Girish et al., 2021]. Quantum Query Complexity versus Bounded Depth Circuits. We give the first example of a partial Boolean function that has a quantum query algorithm with query complexity polylog(N), and such that, any constant-depth circuit of quasipolynomial size has quasipolynomially small advantage over a random guess. Previously, only separations where the constant-depth circuit has polynomially small advantage were known [Ran Raz and Avishay Tal, 2019].
Cite as

Uma Girish, Ran Raz, and Wei Zhan. Lower Bounds for XOR of Forrelations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 52:1-52:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{girish_et_al:LIPIcs.APPROX/RANDOM.2021.52,
  author =	{Girish, Uma and Raz, Ran and Zhan, Wei},
  title =	{{Lower Bounds for XOR of Forrelations}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{52:1--52:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  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.2021.52},
  URN =		{urn:nbn:de:0030-drops-147453},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.52},
  annote =	{Keywords: Forrelation, Quasipolynomial, Separation, Quantum versus Classical, Xor}
}
Document
Invited Talk
DOI: 10.4230/OASIcs.FSFMA.2013.2
Specification, Verification and Inference (Invited Talk)

Authors: Wei-Ngan Chin

Published in: OASIcs, Volume 31, 1st French Singaporean Workshop on Formal Methods and Applications (FSFMA 2013)

Abstract
Traditionally, the focus of specification mechanism has been on improving its ability to cover a wider range of problems more accurately, while the effectiveness of verification is left to the underlying theorem provers. Our work attempts a novel approach, where the focus is on designing good specification mechanisms that can achieve both better expressiveness and better verifiability. Moreover, we shall also highlight a unified specification mechanism that can be used for both verification and inference. Our framework allows preconditions and postconditions to be selectively inferred via a set of uninterpreted relations which are computed using bi-abduction, and modularly synthesized to support concise specification for program codes.
Cite as

Wei-Ngan Chin. Specification, Verification and Inference (Invited Talk). In 1st French Singaporean Workshop on Formal Methods and Applications (FSFMA 2013). Open Access Series in Informatics (OASIcs), Volume 31, p. 2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{chin:OASIcs.FSFMA.2013.2,
  author =	{Chin, Wei-Ngan},
  title =	{{Specification, Verification and Inference}},
  booktitle =	{1st French Singaporean Workshop on Formal Methods and Applications (FSFMA 2013)},
  pages =	{2--2},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-56-9},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{31},
  editor =	{Choppy, Christine and Sun, Jun},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.FSFMA.2013.2},
  URN =		{urn:nbn:de:0030-drops-40827},
  doi =		{10.4230/OASIcs.FSFMA.2013.2},
  annote =	{Keywords: Expressive Specification, Automated Verification, Specification Inference}
}
  • Refine by Author
  • 1 Chin, Wei-Ngan
  • 1 Girish, Uma
  • 1 Raz, Ran
  • 1 Zhan, Wei

  • Refine by Classification
  • 1 Theory of computation → Communication complexity
  • 1 Theory of computation → Oracles and decision trees
  • 1 Theory of computation → Pseudorandomness and derandomization

  • Refine by Keyword
  • 1 Automated Verification
  • 1 Expressive Specification
  • 1 Forrelation
  • 1 Quantum versus Classical
  • 1 Quasipolynomial
  • Show More...

  • Refine by Type
  • 2 document

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