The Experts below are selected from a list of 10101 Experts worldwide ranked by ideXlab platform
Thomas Vidick - One of the best experts on this subject based on the ideXlab platform.
-
three player entangled xor games are np hard to approximate
SIAM Journal on Computing, 2016Co-Authors: Thomas VidickAbstract:We show that for any $\varepsilon>0$ the problem of finding a factor $(2-\varepsilon)$ approximation to the entangled value of a three-player XOR game is NP-hard. Equivalently, the problem of approximating the largest possible quantum violation of a tripartite Bell correlation inequality to within any Multiplicative Constant is NP-hard. These results are the first Constant-factor hardness of approximation results for entangled games or quantum violations of Bell inequalities shown under the sole assumption that P$\neq$NP. They can be thought of as an extension of H\aastad's optimal hardness of approximation results for MAX-E3-LIN2 [J. ACM, 48 (2001), pp. 798--859] to the entangled-player setting. The key technical component of our work is a soundness analysis of a plane-vs-point low-degree test against entangled players. This extends and simplifies the analysis of the multilinearity test by Ito and Vidick [Proceedings of the $53$rd FOCS, IEEE, Piscataway, NJ, 2012, pp. 243--252]. Our results demonstrate t...
-
three player entangled xor games are np hard to approximate
Foundations of Computer Science, 2013Co-Authors: Thomas VidickAbstract:We show that for any e > 0 the problem of finding a factor (2 - e) approximation to the entangled value of a three-player XOR game is NP-hard. Equivalently, the problem of approximating the largest possible quantum violation of a tripartite Bell correlation inequality to within any Multiplicative Constant is NP-hard. These results are the first Constant-factor hardness of approximation results for entangled games or quantum violations of Bell inequalities shown under the sole assumption that P≠NP. They can be thought of as an extension of Hastad's optimal hardness of approximation results for MAX-E3-LIN2 (JACM'01) to the entangled-player setting. The key technical component of our work is a soundness analysis of a point-vs-plane low-degree test against entangled players. This extends and simplifies the analysis of the multilinearity test by Ito and Vidick (FOCS'12). Our results demonstrate the possibility for efficient reductions between entangled-player games and our techniques may lead to further hardness of approximation results.
-
three player entangled xor games are np hard to approximate
arXiv: Quantum Physics, 2013Co-Authors: Thomas VidickAbstract:We show that for any eps>0 the problem of finding a factor (2-eps) approximation to the entangled value of a three-player XOR game is NP-hard. Equivalently, the problem of approximating the largest possible quantum violation of a tripartite Bell correlation inequality to within any Multiplicative Constant is NP-hard. These results are the first Constant-factor hardness of approximation results for entangled games or quantum violations of Bell inequalities shown under the sole assumption that P \neq NP. They can be thought of as an extension of Hastad's optimal hardness of approximation results for MAX-E3-LIN2 (JACM'01) to the entangled-player setting. The key technical component of our work is a soundness analysis of a point-vs-plane low-degree test against entangled players. This extends and simplifies the analysis of the multilinearity test by Ito and Vidick (FOCS'12). Our results demonstrate the possibility for efficient reductions between entangled-player games and our techniques may lead to further hardness of approximation results.
Pengkun Yang - One of the best experts on this subject based on the ideXlab platform.
-
minimax rates of entropy estimation on large alphabets via best polynomial approximation
IEEE Transactions on Information Theory, 2016Co-Authors: Pengkun YangAbstract:Consider the problem of estimating the Shannon entropy of a distribution over $k$ elements from $n$ independent samples. We show that the minimax mean-square error is within the universal Multiplicative Constant factors of $\big ({k }/{n \log k}\big )^{2} + {\log ^{2} k}/{n}$ if $n$ exceeds a Constant factor of $({k}/{\log k})$ ; otherwise, there exists no consistent estimator. This refines the recent result of Valiant and Valiant that the minimal sample size for consistent entropy estimation scales according to $\Theta ({k}/{\log k})$ . The apparatus of the best polynomial approximation plays a key role in both the construction of optimal estimators and, by a duality argument, the minimax lower bound.
-
minimax rates of entropy estimation on large alphabets via best polynomial approximation
arXiv: Information Theory, 2014Co-Authors: Pengkun YangAbstract:Consider the problem of estimating the Shannon entropy of a distribution over $k$ elements from $n$ independent samples. We show that the minimax mean-square error is within universal Multiplicative Constant factors of $$\Big(\frac{k }{n \log k}\Big)^2 + \frac{\log^2 k}{n}$$ if $n$ exceeds a Constant factor of $\frac{k}{\log k}$; otherwise there exists no consistent estimator. This refines the recent result of Valiant-Valiant \cite{VV11} that the minimal sample size for consistent entropy estimation scales according to $\Theta(\frac{k}{\log k})$. The apparatus of best polynomial approximation plays a key role in both the construction of optimal estimators and, via a duality argument, the minimax lower bound.
Eduardo V. Ludeña - One of the best experts on this subject based on the ideXlab platform.
-
relativistic dirac fock exchange and breit interaction energy functionals based on the local density approximation and the self consistent Multiplicative Constant method
Physical Review A, 2004Co-Authors: Valentin V. Karasiev, Eduardo V. Ludeña, Olga A ShukrutoAbstract:Local approximations, formulated in the context of a relativistic extension of the self-consistent a method, are advanced for the case of the relativistic exact Coulomb exchange functional—defined as the Dirac-Fock exchange—and for the Breit expression for the transverse photon exchange, given in terms of the expectation value of the Breit operator. The resulting potentials are local (Multiplicative) operators, in both cases. Using these new functionals, fully relativistic calculations have been performed for selected atoms with Z between 10 and 94, within the framework of relativistic density functional theory (RDFT). The total and exchange energies and ionization potentials obtained from these functionals are quite close to those of the relativistic optimized potential method (ROPM). The computational effort involved in the application of this new method is, however, significantly lower.
-
Self-consistent Multiplicative Constant method for the exchange energy in density-functional theory
Physical Review A, 2002Co-Authors: Valentin V. Karasiev, Eduardo V. LudeñaAbstract:We advance a self-consistent Multiplicative Constant (SCMC) method based on a local exchange potential that yields total, exchange, and atomization energies approaching quite closely, but at a much lower computational cost, those of the exact orbital-dependent exchange treatment [S. Ivanov, S. Hirata, and R. J. Bartlett, Phys, Rev. Lett. 83, 5455 (1999); A. Gorling, ibid. 83. 5459 (1999)]. Application of the SCMC method to any approximate exchange energy functional permits us to remove the self-interaction correction from the latter as well as to restore its variational character. The SCMC method is implemented here using the following exchange energy functionals: local-density approximation, the Perdew-Wang 1991, Becke 1988, and the one-parameter hybrid Becke Lee-Yang-Parr functional. Calculations for atoms and diatomic molecules are presented. In addition, we prove that the exchange energy evaluated from the Kohn-Sham exchange-only determinant is an upper bound to the Hartree-Fock exchange energy.
Valentin V. Karasiev - One of the best experts on this subject based on the ideXlab platform.
-
relativistic dirac fock exchange and breit interaction energy functionals based on the local density approximation and the self consistent Multiplicative Constant method
Physical Review A, 2004Co-Authors: Valentin V. Karasiev, Eduardo V. Ludeña, Olga A ShukrutoAbstract:Local approximations, formulated in the context of a relativistic extension of the self-consistent a method, are advanced for the case of the relativistic exact Coulomb exchange functional—defined as the Dirac-Fock exchange—and for the Breit expression for the transverse photon exchange, given in terms of the expectation value of the Breit operator. The resulting potentials are local (Multiplicative) operators, in both cases. Using these new functionals, fully relativistic calculations have been performed for selected atoms with Z between 10 and 94, within the framework of relativistic density functional theory (RDFT). The total and exchange energies and ionization potentials obtained from these functionals are quite close to those of the relativistic optimized potential method (ROPM). The computational effort involved in the application of this new method is, however, significantly lower.
-
Self-consistent Multiplicative Constant method for the exchange energy in density-functional theory
Physical Review A, 2002Co-Authors: Valentin V. Karasiev, Eduardo V. LudeñaAbstract:We advance a self-consistent Multiplicative Constant (SCMC) method based on a local exchange potential that yields total, exchange, and atomization energies approaching quite closely, but at a much lower computational cost, those of the exact orbital-dependent exchange treatment [S. Ivanov, S. Hirata, and R. J. Bartlett, Phys, Rev. Lett. 83, 5455 (1999); A. Gorling, ibid. 83. 5459 (1999)]. Application of the SCMC method to any approximate exchange energy functional permits us to remove the self-interaction correction from the latter as well as to restore its variational character. The SCMC method is implemented here using the following exchange energy functionals: local-density approximation, the Perdew-Wang 1991, Becke 1988, and the one-parameter hybrid Becke Lee-Yang-Parr functional. Calculations for atoms and diatomic molecules are presented. In addition, we prove that the exchange energy evaluated from the Kohn-Sham exchange-only determinant is an upper bound to the Hartree-Fock exchange energy.
R Budaca - One of the best experts on this subject based on the ideXlab platform.
-
harmonic oscillator potential with a sextic anharmonicity in the prolate γ rigid collective geometrical model
Physics Letters B, 2014Co-Authors: R BudacaAbstract:Abstract An analytical expression for the energy spectrum of the ground and β bands was obtained through the JWKB approximation in the axially symmetric γ -rigid regime of the Bohr–Mottelson Hamiltonian with an oscillator potential and a sextic anharmonicity in the β shape variable. Due to the scaling property of the problem, the resulting energy depends up to an overall Multiplicative Constant on a single parameter. Studying the behavior of the energy spectrum as a function of the free parameter, one establishes the present model's place among other prolate γ -rigid models and in the more general extent of collective solutions. The agreement with experiment is achieved through model fits for few nuclei.
-
Harmonic oscillator potential with a sextic anharmonicity in the prolate γ-rigid collective geometrical model
Elsevier, 2014Co-Authors: R BudacaAbstract:An analytical expression for the energy spectrum of the ground and β bands was obtained through the JWKB approximation in the axially symmetric γ-rigid regime of the Bohr–Mottelson Hamiltonian with an oscillator potential and a sextic anharmonicity in the β shape variable. Due to the scaling property of the problem, the resulting energy depends up to an overall Multiplicative Constant on a single parameter. Studying the behavior of the energy spectrum as a function of the free parameter, one establishes the present model's place among other prolate γ-rigid models and in the more general extent of collective solutions. The agreement with experiment is achieved through model fits for few nuclei. Keywords: Collective states, Sextic oscillato
