The Experts below are selected from a list of 45297 Experts worldwide ranked by ideXlab platform

Mario Szegedy - One of the best experts on this subject based on the ideXlab platform.

  • THE QUANTUM ADVERSARY METHOD AND Classical Formula SIZE LOWER BOUNDS
    Computational Complexity, 2006
    Co-Authors: Sophie Laplante, Troy Lee, Mario Szegedy
    Abstract:

    We introduce two new complexity measures for Boolean functions, which we name sumPI and maxPI . The quantity sumPI has been emerging through a line of research on quantum query complexity lower bounds via the so-called quantum adversary method (Ambainis 2002, 2003; Barnum et al. 2003; Laplante & Magniez 2004; Zhang 2005), culminating in ?palek & Szegedy (2005) with the realization that these many different Formulations are in fact equivalent. Given that sumPI turns out to be such a robust invariant of a function, we begin to investigate this quantity in its own right and see that it also has applications to Classical complexity theory. As a surprising application we show that sumPI 2(f) is a lower bound on the Formula size, and even, up to a constant multiplicative factor, the probabilistic Formula size of f. We show that several Formula size lower bounds in the literature, specifically Khrapchenko and its extensions (Khrapchenko 1971; Koutsoupias 1993), including a key lemma of Hastad (1998), are in fact special cases of our method. The second quantity we introduce, maxPI (f), is always at least as large as sumPI(f) , and is derived from sumPI in such a way that maxPI 2(f) remains a lower bound on Formula size. Our main result is proven via a combinatorial lemma which relates the square of the spectral norm of a matrix to the squares of the spectral norms of its submatrices. The generality of this lemma implies that our methods can also be used to lower-bound the communication complexity of relations, and a related combinatorial quantity, the rectangle partition number. To exhibit the strengths and weaknesses of our methods, we look at the sumPI and maxPI complexity of a few examples, including the recursive majority of three function, a function defined by Ambainis (2003), and the collision problem.

  • the quantum adversary method and Classical Formula size lower bounds
    Conference on Computational Complexity, 2005
    Co-Authors: Sophie Laplante, Troy Lee, Mario Szegedy
    Abstract:

    We introduce two new complexity measures for Boolean functions, which we name sumPI and maxPI. The quantity sumPI has been emerging through a line of research on quantum query complexity lower bounds via the so-called quantum adversary, culminating with the realization that these many different Formulations are in fact equivalent. Given that sumPI turns out to be such a robust invariant of a function, we begin to investigate this quantity in its own right and see that it also has applications to Classical complexity theory. As a surprising application we show that sumPI/sup 2/(f) is a lower bound on the Formula size, and even, up to a constant multiplicative factor, the probabilistic Formula size of f. We show that several Formula size lower bounds in the literature, specifically Khrapchenko and its extensions [Khrapchenko, 1971, Koutsoupias, 1993], including a key lemma of [Hastad, 1998], are in fact special cases of our method. The second quantity we introduce, maxPI(f), is always at least as large as sumPI(f), and is derived from sumPI in such a way that maxPI/sup 2/(f) remains a lower bound on Formula size. Our main result is proven via a combinatorial lemma which relates the square of the spectral norm of a matrix to the squares of the spectral norms of its submatrices. The generality of this lemma gives that our methods can also be used to lower bound the communication complexity of relations, and a related combinatorial quantity, the rectangle partition number. To exhibit the strengths and weaknesses of our methods, we look at the sumPI and maxPI complexity of a few examples, including the recursive majority of three function, a function defined by Ambainis [2003], and the collision problem.

  • The quantum adversary method and Classical Formula size lower bounds
    arXiv: Quantum Physics, 2005
    Co-Authors: Sophie Laplante, Troy Lee, Mario Szegedy
    Abstract:

    We introduce two new complexity measures for Boolean functions, or more generally for functions of the form f:S->T. We call these measures sumPI and maxPI. The quantity sumPI has been emerging through a line of research on quantum query complexity lower bounds via the so-called quantum adversary method [Amb02, Amb03, BSS03, Zha04, LM04], culminating in [SS04] with the realization that these many different Formulations are in fact equivalent. Given that sumPI turns out to be such a robust invariant of a function, we begin to investigate this quantity in its own right and see that it also has applications to Classical complexity theory. As a surprising application we show that sumPI^2(f) is a lower bound on the Formula size, and even, up to a constant multiplicative factor, the probabilistic Formula size of f. We show that several Formula size lower bounds in the literature, specifically Khrapchenko and its extensions [Khr71, Kou93], including a key lemma of [Has98], are in fact special cases of our method. The second quantity we introduce, maxPI(f), is always at least as large as sumPI(f), and is derived from sumPI in such a way that maxPI^2(f) remains a lower bound on Formula size. While sumPI(f) is always a lower bound on the quantum query complexity of f, this is not the case in general for maxPI(f). A strong advantage of sumPI(f) is that it has both primal and dual characterizations, and thus it is relatively easy to give both upper and lower bounds on the sumPI complexity of functions. To demonstrate this, we look at a few concrete examples, for three functions: recursive majority of three, a function defined by Ambainis, and the collision problem.

Sophie Laplante - One of the best experts on this subject based on the ideXlab platform.

  • THE QUANTUM ADVERSARY METHOD AND Classical Formula SIZE LOWER BOUNDS
    Computational Complexity, 2006
    Co-Authors: Sophie Laplante, Troy Lee, Mario Szegedy
    Abstract:

    We introduce two new complexity measures for Boolean functions, which we name sumPI and maxPI . The quantity sumPI has been emerging through a line of research on quantum query complexity lower bounds via the so-called quantum adversary method (Ambainis 2002, 2003; Barnum et al. 2003; Laplante & Magniez 2004; Zhang 2005), culminating in ?palek & Szegedy (2005) with the realization that these many different Formulations are in fact equivalent. Given that sumPI turns out to be such a robust invariant of a function, we begin to investigate this quantity in its own right and see that it also has applications to Classical complexity theory. As a surprising application we show that sumPI 2(f) is a lower bound on the Formula size, and even, up to a constant multiplicative factor, the probabilistic Formula size of f. We show that several Formula size lower bounds in the literature, specifically Khrapchenko and its extensions (Khrapchenko 1971; Koutsoupias 1993), including a key lemma of Hastad (1998), are in fact special cases of our method. The second quantity we introduce, maxPI (f), is always at least as large as sumPI(f) , and is derived from sumPI in such a way that maxPI 2(f) remains a lower bound on Formula size. Our main result is proven via a combinatorial lemma which relates the square of the spectral norm of a matrix to the squares of the spectral norms of its submatrices. The generality of this lemma implies that our methods can also be used to lower-bound the communication complexity of relations, and a related combinatorial quantity, the rectangle partition number. To exhibit the strengths and weaknesses of our methods, we look at the sumPI and maxPI complexity of a few examples, including the recursive majority of three function, a function defined by Ambainis (2003), and the collision problem.

  • the quantum adversary method and Classical Formula size lower bounds
    Conference on Computational Complexity, 2005
    Co-Authors: Sophie Laplante, Troy Lee, Mario Szegedy
    Abstract:

    We introduce two new complexity measures for Boolean functions, which we name sumPI and maxPI. The quantity sumPI has been emerging through a line of research on quantum query complexity lower bounds via the so-called quantum adversary, culminating with the realization that these many different Formulations are in fact equivalent. Given that sumPI turns out to be such a robust invariant of a function, we begin to investigate this quantity in its own right and see that it also has applications to Classical complexity theory. As a surprising application we show that sumPI/sup 2/(f) is a lower bound on the Formula size, and even, up to a constant multiplicative factor, the probabilistic Formula size of f. We show that several Formula size lower bounds in the literature, specifically Khrapchenko and its extensions [Khrapchenko, 1971, Koutsoupias, 1993], including a key lemma of [Hastad, 1998], are in fact special cases of our method. The second quantity we introduce, maxPI(f), is always at least as large as sumPI(f), and is derived from sumPI in such a way that maxPI/sup 2/(f) remains a lower bound on Formula size. Our main result is proven via a combinatorial lemma which relates the square of the spectral norm of a matrix to the squares of the spectral norms of its submatrices. The generality of this lemma gives that our methods can also be used to lower bound the communication complexity of relations, and a related combinatorial quantity, the rectangle partition number. To exhibit the strengths and weaknesses of our methods, we look at the sumPI and maxPI complexity of a few examples, including the recursive majority of three function, a function defined by Ambainis [2003], and the collision problem.

  • The quantum adversary method and Classical Formula size lower bounds
    arXiv: Quantum Physics, 2005
    Co-Authors: Sophie Laplante, Troy Lee, Mario Szegedy
    Abstract:

    We introduce two new complexity measures for Boolean functions, or more generally for functions of the form f:S->T. We call these measures sumPI and maxPI. The quantity sumPI has been emerging through a line of research on quantum query complexity lower bounds via the so-called quantum adversary method [Amb02, Amb03, BSS03, Zha04, LM04], culminating in [SS04] with the realization that these many different Formulations are in fact equivalent. Given that sumPI turns out to be such a robust invariant of a function, we begin to investigate this quantity in its own right and see that it also has applications to Classical complexity theory. As a surprising application we show that sumPI^2(f) is a lower bound on the Formula size, and even, up to a constant multiplicative factor, the probabilistic Formula size of f. We show that several Formula size lower bounds in the literature, specifically Khrapchenko and its extensions [Khr71, Kou93], including a key lemma of [Has98], are in fact special cases of our method. The second quantity we introduce, maxPI(f), is always at least as large as sumPI(f), and is derived from sumPI in such a way that maxPI^2(f) remains a lower bound on Formula size. While sumPI(f) is always a lower bound on the quantum query complexity of f, this is not the case in general for maxPI(f). A strong advantage of sumPI(f) is that it has both primal and dual characterizations, and thus it is relatively easy to give both upper and lower bounds on the sumPI complexity of functions. To demonstrate this, we look at a few concrete examples, for three functions: recursive majority of three, a function defined by Ambainis, and the collision problem.

Troy Lee - One of the best experts on this subject based on the ideXlab platform.

  • THE QUANTUM ADVERSARY METHOD AND Classical Formula SIZE LOWER BOUNDS
    Computational Complexity, 2006
    Co-Authors: Sophie Laplante, Troy Lee, Mario Szegedy
    Abstract:

    We introduce two new complexity measures for Boolean functions, which we name sumPI and maxPI . The quantity sumPI has been emerging through a line of research on quantum query complexity lower bounds via the so-called quantum adversary method (Ambainis 2002, 2003; Barnum et al. 2003; Laplante & Magniez 2004; Zhang 2005), culminating in ?palek & Szegedy (2005) with the realization that these many different Formulations are in fact equivalent. Given that sumPI turns out to be such a robust invariant of a function, we begin to investigate this quantity in its own right and see that it also has applications to Classical complexity theory. As a surprising application we show that sumPI 2(f) is a lower bound on the Formula size, and even, up to a constant multiplicative factor, the probabilistic Formula size of f. We show that several Formula size lower bounds in the literature, specifically Khrapchenko and its extensions (Khrapchenko 1971; Koutsoupias 1993), including a key lemma of Hastad (1998), are in fact special cases of our method. The second quantity we introduce, maxPI (f), is always at least as large as sumPI(f) , and is derived from sumPI in such a way that maxPI 2(f) remains a lower bound on Formula size. Our main result is proven via a combinatorial lemma which relates the square of the spectral norm of a matrix to the squares of the spectral norms of its submatrices. The generality of this lemma implies that our methods can also be used to lower-bound the communication complexity of relations, and a related combinatorial quantity, the rectangle partition number. To exhibit the strengths and weaknesses of our methods, we look at the sumPI and maxPI complexity of a few examples, including the recursive majority of three function, a function defined by Ambainis (2003), and the collision problem.

  • the quantum adversary method and Classical Formula size lower bounds
    Conference on Computational Complexity, 2005
    Co-Authors: Sophie Laplante, Troy Lee, Mario Szegedy
    Abstract:

    We introduce two new complexity measures for Boolean functions, which we name sumPI and maxPI. The quantity sumPI has been emerging through a line of research on quantum query complexity lower bounds via the so-called quantum adversary, culminating with the realization that these many different Formulations are in fact equivalent. Given that sumPI turns out to be such a robust invariant of a function, we begin to investigate this quantity in its own right and see that it also has applications to Classical complexity theory. As a surprising application we show that sumPI/sup 2/(f) is a lower bound on the Formula size, and even, up to a constant multiplicative factor, the probabilistic Formula size of f. We show that several Formula size lower bounds in the literature, specifically Khrapchenko and its extensions [Khrapchenko, 1971, Koutsoupias, 1993], including a key lemma of [Hastad, 1998], are in fact special cases of our method. The second quantity we introduce, maxPI(f), is always at least as large as sumPI(f), and is derived from sumPI in such a way that maxPI/sup 2/(f) remains a lower bound on Formula size. Our main result is proven via a combinatorial lemma which relates the square of the spectral norm of a matrix to the squares of the spectral norms of its submatrices. The generality of this lemma gives that our methods can also be used to lower bound the communication complexity of relations, and a related combinatorial quantity, the rectangle partition number. To exhibit the strengths and weaknesses of our methods, we look at the sumPI and maxPI complexity of a few examples, including the recursive majority of three function, a function defined by Ambainis [2003], and the collision problem.

  • The quantum adversary method and Classical Formula size lower bounds
    arXiv: Quantum Physics, 2005
    Co-Authors: Sophie Laplante, Troy Lee, Mario Szegedy
    Abstract:

    We introduce two new complexity measures for Boolean functions, or more generally for functions of the form f:S->T. We call these measures sumPI and maxPI. The quantity sumPI has been emerging through a line of research on quantum query complexity lower bounds via the so-called quantum adversary method [Amb02, Amb03, BSS03, Zha04, LM04], culminating in [SS04] with the realization that these many different Formulations are in fact equivalent. Given that sumPI turns out to be such a robust invariant of a function, we begin to investigate this quantity in its own right and see that it also has applications to Classical complexity theory. As a surprising application we show that sumPI^2(f) is a lower bound on the Formula size, and even, up to a constant multiplicative factor, the probabilistic Formula size of f. We show that several Formula size lower bounds in the literature, specifically Khrapchenko and its extensions [Khr71, Kou93], including a key lemma of [Has98], are in fact special cases of our method. The second quantity we introduce, maxPI(f), is always at least as large as sumPI(f), and is derived from sumPI in such a way that maxPI^2(f) remains a lower bound on Formula size. While sumPI(f) is always a lower bound on the quantum query complexity of f, this is not the case in general for maxPI(f). A strong advantage of sumPI(f) is that it has both primal and dual characterizations, and thus it is relatively easy to give both upper and lower bounds on the sumPI complexity of functions. To demonstrate this, we look at a few concrete examples, for three functions: recursive majority of three, a function defined by Ambainis, and the collision problem.

George H. Goedecke - One of the best experts on this subject based on the ideXlab platform.

  • Exact Formula for the sound scattering cross section per unit volume in a turbulent atmosphere
    Journal of the Acoustical Society of America, 2003
    Co-Authors: Vladimir E. Ostashev, George H. Goedecke
    Abstract:

    The sound scattering cross section per unit volume is one of the most important statistical characteristics of a sound wave propagating in a turbulent atmosphere. In the literature, a Formula for the sound scattering cross section is derived from an equation for a sound wave propagating in an atmosphere with temperature and velocity fluctuations. Such an equation is obtained from a complete set of linearized equations of fluid dynamics using some approximations. Thus, the Classical Formula for the sound scattering cross section is intrinsically approximate. In the present paper, sound scattering in a turbulent atmosphere is studied starting from the complete set of linearized equations of fluid dynamics. This approach results in an exact Formula for the sound scattering cross section. The exact Formula accounts for sound scattering by pressure fluctuations and by the divergence of velocity fluctuations while the Classical Formula does not. It follows from the exact Formula that, in a dry air, a sound wave...

Frédéric Faure - One of the best experts on this subject based on the ideXlab platform.

  • Semi-Classical Formula beyond the Ehrenfest time in quantum chaos. (I) Trace Formula
    Annales de l'Institut Fourier, 2007
    Co-Authors: Frédéric Faure
    Abstract:

    On considere une application M, Anosov non lineaire qui conserve l'aire sur le tore T 2 . C'est un des exemples les plus simples d'une dynamique chaotique. On s'interesse a la dynamique quantique pour les temps longs, generee par un operateur unitaire M. La formule des traces semi-classique habituelle exprime Tr (M t ) pour t fini, dans la limite h → 0, en termes d'orbites periodiques de M de periode t. Des travaux recents atteignent des temps t « t E /6 ou t E = log(1/h)/λ est le temps d'Ehrenfest, et λ est le coefficient de Lyapounov. En utilisant une description uniforme de la dynamique au moyen d'une forme normale semi-classique, nous montrons comment etendre la formule des traces pour des temps plus longs, de la forme t = C.t E , ou C'est une constante arbitraire, et avec une erreur arbitrairement petite.

  • Semi-Classical Formula beyond the Ehrenfest time in quantum chaos. (I) Trace Formula
    arXiv: Chaotic Dynamics, 2006
    Co-Authors: Frédéric Faure
    Abstract:

    We consider a nonlinear area preserving Anosov map M on the torus phase space, which is the simplest example of a fully chaotic dynamics. We are interested in the quantum dynamics for long time, generated by the unitary quantum propagator Mq. The usual semi-Classical Trace Formula expresses Tr(Mq^t) for finite time t, in the limit hbar->0, in terms of periodic orbits of M of period t. Recent work reach time t

  • semi Classical Formula beyond the ehrenfest time in quantum chaos i trace Formula
    arXiv: Chaotic Dynamics, 2006
    Co-Authors: Frédéric Faure
    Abstract:

    We consider a nonlinear area preserving Anosov map M on the torus phase space, which is the simplest example of a fully chaotic dynamics. We are interested in the quantum dynamics for long time, generated by the unitary quantum propagator Mq. The usual semi-Classical Trace Formula expresses Tr(Mq^t) for finite time t, in the limit hbar->0, in terms of periodic orbits of M of period t. Recent work reach time t<< tE/6 where tE=log(1/hbar)/lambda is the Ehrenfest time, and lambda is the Lyapounov coefficient. Using a semi-Classical normal form description of the dynamics uniformly over phase space, we show how to extend the trace Formula for longer time of the form t= C.tE where C is any constant, with an arbitrary small error.