No abstract uploaded!

In this paper, we present a new algorithm, such that, for the learning with errors (LWE) problems, if the errors are bounded -- the errors do not span the whole prime finite field F_q but a fixed known subset of size D (D<q), which we call the learning with bounded errors (LWBE) problems, we can solve it with complexity O(n^D).

No abstract uploaded!

In this paper we study the support recovery problem for single index models Y=f(X⊺β,ε), where f is an unknown link function, X∼Np(0,𝕀p) and β is an s-sparse unit vector such that βi∈{±1s√,0}. In particular, we look into the performance of two computationally inexpensive algorithms: (a) the diagonal thresholding sliced inverse regression (DT-SIR) introduced by Lin et al. (2015); and (b) a semi-definite programming (SDP) approach inspired by Amini & Wainwright (2008). When s=O(p1−δ) for some δ>0, we demonstrate that both procedures can succeed in recovering the support of β as long as the rescaled sample size κ=nslog(p−s) is larger than a certain critical threshold. On the other hand, when κ is smaller than a critical value, any algorithm fails to recover the support with probability at least 12 asymptotically. In other words, we demonstrate that both DT-SIR and the SDP approach are optimal (up to a scalar) for recovering the support of β in terms of sample size. We provide extensive simulations, as well as a real dataset application to help verify our theoretical observations.

We study the tensor product decomposition of the split real quantum group Uqq~(sl(2,R)) from the perspective of finite dimensional representation theory of compact quantum groups. It is known that the class of positive representations of Uqq~(sl(2,R)) is closed under taking tensor product. In this paper, we show that one can derive the corresponding Hilbert space decomposition, given explicitly by quantum dilogarithm transformations, from the Clebsch-Gordan coefficients of the tensor product decomposition of finite dimensional representations of the compact quantum group Uq(sl2) by solving certain functional equations and using normalization arising from tensor products of canonical basis. We propose a general strategy to deal with the tensor product decomposition for the higher rank split real quantum group Uqq~(gR)