ν-twin support vector machine with Universum data for classification

A novel ν-twin support vector machine with Universum data (\(\mathfrak {U}_{\nu }\)-TSVM) is proposed in this paper. \(\mathfrak {U}_{\nu }\)-TSVM allows to incorporate the prior knowledge embedded in the unlabeled samples into the supervised learning. It aims to utilize these prior knowledge to improve the generalization performance. Different from the conventional \(\mathfrak {U}\)-SVM, \(\mathfrak {U}_{\nu }\)-TSVM employs two Hinge loss functions to make the Universum data lie in a nonparallel insensitive loss tube, which makes it exploit these prior knowledge more flexibly. In addition, the newly introduced parameters ν₁, ν₂ in the \(\mathfrak {U}_{\nu }\)-TSVM have better theoretical interpretation than the penalty factor c in the \(\mathfrak {U}\)-TSVM. Numerical experiments on seventeen benchmark datasets, handwritten digit recognition, and gender classification indicate that the Universum indeed contributes to improving the prediction accuracy. Moreover, our \(\mathfrak {U}_{\nu }\)-TSVM is far superior to the other three algorithms (\(\mathfrak {U}\)-SVM, ν-TSVM and \(\mathfrak {U}\)-TSVM) from the prediction accuracy.     

Finite approximation of the first passage models for discrete-time Markov decision processes with varying discount factors

This paper deals with the finite approximation of the first passage models for discrete-time Markov decision processes with varying discount factors. For a given control model \(\mathcal {M}\) with denumerable states and compact Borel action sets, and possibly unbounded reward functions, under reasonable conditions we prove that there exists a sequence of control models \(\mathcal {M}_{n}\) such that the first passage optimal rewards and policies of \(\mathcal {M}_{n}\) converge to those of \(\mathcal {M}\), respectively. Based on the convergence theorems, we propose a finite-state and finite-action truncation method for the given control model \(\mathcal {M}\), and show that the first passage optimal reward and policies of \(\mathcal {M}\) can be approximated by those of the solvable truncated finite control models. Finally, we give the corresponding value and policy iteration algorithms to solve the finite approximation models.     

New asymmetric quantum codes over $$F_{q}$$

Two families of new asymmetric quantum codes are constructed in this paper. The first family is the asymmetric quantum codes with length \(n=q^{m}-1\) over \(F_{q}\), where \(q\ge 5\) is a prime power. The second one is the asymmetric quantum codes with length \(n=3^{m}-1\). These asymmetric quantum codes are derived from the CSS construction and pairs of nested BCH codes. Moreover, let the defining set \(T_{1}=T_{2}^{-q}\), then the real Z-distance of our asymmetric quantum codes are much larger than \(\delta _\mathrm{max}+1\), where \(\delta _\mathrm{max}\) is the maximal designed distance of dual-containing narrow-sense BCH code, and the parameters presented here have better than the ones available in the literature.     

Non-determinism in Gödel’s System <Emphasis Type="Italic">T</Emphasis>

The calculus T^? is a successor-free version of Gödel’s T. It is well known that a number of important complexity classes, like e.g. the classes logspace, \(\textsc{p}\), \(\textsc{linspace}\), \(\textsc{etime}\) and \(\textsc{pspace}\), are captured by natural fragments of T^? and related calculi. We introduce the calculus T^∽, which is a non-deterministic variant of T^?, and compare the computational power of T^∽ and T^?. First, we provide a denotational semantics for T^∽ and prove this semantics to be adequate. Furthermore, we prove that \(\textsc{linspace}\subseteq \mathcal {G}^{\backsim }_{0} \subseteq \textsc{linspace}\) and \(\textsc{etime}\subseteq \mathcal {G}^{\backsim }_{1} \subseteq \textsc{pspace}\) where \(\mathcal {G}^{\backsim }_{0}\) and \(\mathcal {G}^{\backsim }_{1}\) are classes of problems decidable by certain fragments of T^∽. (It is proved elsewhere that the corresponding fragments of T^? equal respectively \(\textsc{linspace}\) and \(\textsc{etime}\).) Finally, we show a way to interpret T^∽ in T^?.     

Symmetric triangular approximations of fuzzy numbers under a general condition and properties

We consider the set \(\mathcal {P}\) of real parameters associated to a fuzzy number, in a general form which includes the most important characteristics already introduced for fuzzy numbers. We find the set \(\mathcal {P}_{\mathrm{s}}\subset \mathcal {P}\) with the property that for any given fuzzy number there exists at least a symmetric triangular fuzzy number which preserves a fixed parameter \(p\in \mathcal {P}\). We compute the symmetric triangular approximation of a fuzzy number which preserves the parameter \(p\in \mathcal {P }_{\mathrm{s}}\). The uniqueness is an immediate consequence; therefore, an approximation operator is obtained. The properties of scale and translation invariance, additivity and continuity of this operator are studied. Some applications related with value and expected value, as important parameters, are given too.     

Hybridized Discontinuous Galerkin Method for Elliptic Interface Problems: Error Estimates Under Low Regularity Assumptions of Solutions

New hybridized discontinuous Galerkin (HDG) methods for the interface problem for elliptic equations are proposed. Unknown functions of our schemes are \(u_h\) in elements and \(\hat{u}_h\) on inter-element edges. That is, we formulate our schemes without introducing the flux variable. We assume that subdomains \(\Omega _1\) and \(\Omega _2\) are polyhedral domains and that the interface \(\Gamma =\partial \Omega _1\cap \partial \Omega _2\) is polyhedral surface or polygon. Moreover, \(\Gamma \) is assumed to be expressed as the union of edges of some elements. We deal with the case where the interface is transversely connected with the boundary of the whole domain \(\overline{\Omega }=\overline{\Omega _1\cap \Omega _2}\). Consequently, the solution u of the interface problem may not have a sufficient regularity, say \(u\in H^2(\Omega )\) or \(u|_{\Omega _1}\in H^2(\Omega _1)\), \(u|_{\Omega _2}\in H^2(\Omega _2)\). We succeed in deriving optimal order error estimates in an HDG norm and the \(L^2\) norm under low regularity assumptions of solutions, say \(u|_{\Omega _1}\in H^{1+s}(\Omega _1)\) and \(u|_{\Omega _2}\in H^{1+s}(\Omega _2)\) for some \(s\in (1/2,1]\), where \(H^{1+s}\) denotes the fractional order Sobolev space. Numerical examples to validate our results are also presented.     

Master Lovas–Andai and equivalent formulas verifying the $$\frac{8}{33}$$ two-qubit Hilbert–Schmidt separability probability and companion rational-valued conjectures

We begin by investigating relationships between two forms of Hilbert–Schmidt two-rebit and two-qubit “separability functions”—those recently advanced by Lovas and Andai (J Phys A Math Theor 50(29):295303, 2017), and those earlier presented by Slater (J Phys A 40(47):14279, 2007). In the Lovas–Andai framework, the independent variable \(\varepsilon \in [0,1]\) is the ratio \(\sigma (V)\) of the singular values of the \(2 \times 2\) matrix \(V=D_2^{1/2} D_1^{-1/2}\) formed from the two \(2 \times 2\) diagonal blocks (\(D_1, D_2\)) of a \(4 \times 4\) density matrix \(D= \left||\rho _{ij}\right||\). In the Slater setting, the independent variable \(\mu \) is the diagonal-entry ratio \(\sqrt{\frac{\rho _{11} \rho _ {44}}{\rho _ {22} \rho _ {33}}}\)—with, of central importance, \(\mu =\varepsilon \) or \(\mu =\frac{1}{\varepsilon }\) when both \(D_1\) and \(D_2\) are themselves diagonal. Lovas and Andai established that their two-rebit “separability function” \(\tilde{\chi }_1 (\varepsilon )\) (\(\approx \varepsilon \)) yields the previously conjectured Hilbert–Schmidt separability probability of \(\frac{29}{64}\). We are able, in the Slater framework (using cylindrical algebraic decompositions [CAD] to enforce positivity constraints), to reproduce this result. Further, we newly find its two-qubit, two-quater[nionic]-bit and “two-octo[nionic]-bit” counterparts, \(\tilde{\chi _2}(\varepsilon ) =\frac{1}{3} \varepsilon ^2 \left( 4-\varepsilon ^2\right) \), \(\tilde{\chi _4}(\varepsilon ) =\frac{1}{35} \varepsilon ^4 \left( 15 \varepsilon ^4-64 \varepsilon ^2+84\right) \) and \(\tilde{\chi _8} (\varepsilon )= \frac{1}{1287}\varepsilon ^8 \left( 1155 \varepsilon ^8-7680 \varepsilon ^6+20160 \varepsilon ^4-25088 \varepsilon ^2+12740\right) \). These immediately lead to predictions of Hilbert–Schmidt separability/PPT-probabilities of \(\frac{8}{33}\), \(\frac{26}{323}\) and \(\frac{44482}{4091349}\), in full agreement with those of the “concise formula” (Slater in J Phys A 46:445302, 2013), and, additionally, of a “specialized induced measure” formula. Then, we find a Lovas–Andai “master formula,” \(\tilde{\chi _d}(\varepsilon )= \frac{\varepsilon ^d \Gamma (d+1)^3 \, _3\tilde{F}_2\left( -\frac{d}{2},\frac{d}{2},d;\frac{d}{2}+1,\frac{3 d}{2}+1;\varepsilon ^2\right) }{\Gamma \left( \frac{d}{2}+1\right) ^2}\), encompassing both even and odd values of d. Remarkably, we are able to obtain the \(\tilde{\chi _d}(\varepsilon )\) formulas, \(d=1,2,4\), applicable to full (9-, 15-, 27-) dimensional sets of density matrices, by analyzing (6-, 9, 15-) dimensional sets, with not only diagonal \(D_1\) and \(D_2\), but also an additional pair of nullified entries. Nullification of a further pair still leads to X-matrices, for which a distinctly different, simple Dyson-index phenomenon is noted. C. Koutschan, then, using his HolonomicFunctions program, develops an order-4 recurrence satisfied by the predictions of the several formulas, establishing their equivalence. A two-qubit separability probability of \(1-\frac{256}{27 \pi ^2}\) is obtained based on the operator monotone function \(\sqrt{x}\), with the use of \(\tilde{\chi _2}(\varepsilon )\).     

The representations and computations of generalized inverses $$A^{(1)}_{T,S}$$, $$A^{(1,2)}_{T,S}$$AT,S(1,2) and the group inverse

In this paper, we derive novel representations of generalized inverses \(A^{(1)}_{T,S}\) and \(A^{(1,2)}_{T,S}\), which are much simpler than those introduced in Ben-Israel and Greville (Generalized inverses: theory and applications. Springer, New York, 2003). When \(A^{(1,2)}_{T,S}\) is applied to matrices of index one, a simple representation for the group inverse \(A_{g}\) is derived. Based on these representations, we derive various algorithms for computing \(A^{(1)}_{T,S}\), \(A^{(1,2)}_{T,S}\) and \(A_{g}\), respectively. Moreover, our methods can be achieved through Gauss–Jordan elimination and complexity analysis indicates that our method for computing the group inverse \(A_{g}\) is more efficient than the other existing methods in the literature for a large class of problems in the computational complexity sense. Finally, numerical experiments show that our method for the group inverse \(A_{g}\) has highest accuracy among all the existing methods in the literature and also has the lowest cost of CPU time when applied to symmetric matrices or matrices with high rank or small size matrices with low rank in practice.     

Optimal noise functions for location privacy on continuous regions

Users of location-based services are highly vulnerable to privacy risks since they need to disclose, at least partially, their locations to benefit from these services. One possibility to limit these risks is to obfuscate the location of a user by adding random noise drawn from a noise function. In this paper, we require the noise functions to satisfy a generic location privacy notion called \(\ell \)-privacy, which makes the position of the user in a given region \(\mathcal {X}\) relatively indistinguishable from other points in \(\mathcal {X}\). We also aim at minimizing the loss in the service utility due to such obfuscation. While existing optimization frameworks regard the region \(\mathcal {X}\) restrictively as a finite set of points, we consider the more realistic case in which the region is rather continuous with a nonzero area. In this situation, we demonstrate that circular noise functions are enough to satisfy \(\ell \)-privacy on \(\mathcal {X}\) and equivalently on the entire space without any penalty in the utility. Afterward, we describe a large parametric space of noise functions that satisfy \(\ell \)-privacy on \(\mathcal {X}\), and show that this space has always an optimal member, regardless of \(\ell \) and \(\mathcal {X}\). We also investigate the recent notion of \(\epsilon \)-geo-indistinguishability as an instance of \(\ell \)-privacy and prove in this case that with respect to any increasing loss function, the planar Laplace noise function is optimal for any region having a nonzero area.     

Characterizing the Existence of Potential Functions in Weighted Congestion Games

Since the pioneering paper of Rosenthal a lot of work has been done in order to determine classes of games that admit a potential. First, we study the existence of potential functions for weighted congestion games. Let \(\mathcal{C}\) be an arbitrary set of locally bounded functions and let \(\mathcal{G}(\mathcal{C})\) be the set of weighted congestion games with cost functions in \(\mathcal{C}\). We show that every weighted congestion game \(G\in\mathcal{G}(\mathcal{C})\) admits an exact potential if and only if \(\mathcal{C}\) contains only affine functions. We also give a similar characterization for w-potentials with the difference that here \(\mathcal{C}\) consists either of affine functions or of certain exponential functions. We finally extend our characterizations to weighted congestion games with facility-dependent demands and elastic demands, respectively.     

Two families of BCH codes and new quantum codes

In this paper, two families of non-narrow-sense (NNS) BCH codes of lengths \(n=\frac{q^{2m}-1}{q^2-1}\) and \(n=\frac{q^{2m}-1}{q+1}\) (\(m\ge 3)\) over the finite field \(\mathbf {F}_{q^2}\) are studied. The maximum designed distances \(\delta ^\mathrm{new}_\mathrm{max}\) of these dual-containing BCH codes are determined by a careful analysis of properties of the cyclotomic cosets. NNS BCH codes which achieve these maximum designed distances are presented, and a sequence of nested NNS BCH codes that contain these BCH codes with maximum designed distances are constructed and their parameters are computed. Consequently, new nonbinary quantum BCH codes are derived from these NNS BCH codes. The new quantum codes presented here include many classes of good quantum codes, which have parameters better than those constructed from narrow-sense BCH codes, negacyclic and constacyclic BCH codes in the literature.     

Subspace Learning by $$\ell ^{0}$$-Induced Sparsity

Subspace clustering methods partition the data that lie in or close to a union of subspaces in accordance with the subspace structure. Such methods with sparsity prior, such as sparse subspace clustering (SSC) (Elhamifar and Vidal in IEEE Trans Pattern Anal Mach Intell 35(11):2765–2781, 2013) with the sparsity induced by the \(\ell ^{1}\)-norm, are demonstrated to be effective in subspace clustering. Most of those methods require certain assumptions, e.g. independence or disjointness, on the subspaces. However, these assumptions are not guaranteed to hold in practice and they limit the application of existing sparse subspace clustering methods. In this paper, we propose \(\ell ^{0}\)-induced sparse subspace clustering (\(\ell ^{0}\)-SSC). In contrast to the required assumptions, such as independence or disjointness, on subspaces for most existing sparse subspace clustering methods, we prove that \(\ell ^{0}\)-SSC guarantees the subspace-sparse representation, a key element in subspace clustering, for arbitrary distinct underlying subspaces almost surely under the mild i.i.d. assumption on the data generation. We also present the “no free lunch” theorem which shows that obtaining the subspace representation under our general assumptions can not be much computationally cheaper than solving the corresponding \(\ell ^{0}\) sparse representation problem of \(\ell ^{0}\)-SSC. A novel approximate algorithm named Approximate \(\ell ^{0}\)-SSC (A\(\ell ^{0}\)-SSC) is developed which employs proximal gradient descent to obtain a sub-optimal solution to the optimization problem of \(\ell ^{0}\)-SSC with theoretical guarantee. The sub-optimal solution is used to build a sparse similarity matrix upon which spectral clustering is performed for the final clustering results. Extensive experimental results on various data sets demonstrate the superiority of A\(\ell ^{0}\)-SSC compared to other competing clustering methods. Furthermore, we extend \(\ell ^{0}\)-SSC to semi-supervised learning by performing label propagation on the sparse similarity matrix learnt by A\(\ell ^{0}\)-SSC and demonstrate the effectiveness of the resultant semi-supervised learning method termed \(\ell ^{0}\)-sparse subspace label propagation (\(\ell ^{0}\)-SSLP).     

On congruences of weak lattices

We characterize when an equivalence relation on the base set of a weak lattice \(\mathbf{L}=(L,\sqcup ,\sqcap )\) becomes a congruence on \(\mathbf{L}\) provided it has convex classes. We show that an equivalence relation on L is a congruence on \(\mathbf{L}\) if it satisfies the substitution property for comparable elements. Conditions under which congruence classes are convex are studied. If one fundamental operation of \(\mathbf{L}\) is commutative then \(\mathbf{L}\) is congruence distributive and all congruences of \(\mathbf{L}\) have convex classes.     

Shrinking one-way cellular automata

We investigate cellular automata as acceptors for formal languages. In particular, we consider real-time one-way cellular automata (\(\text{OCA}\)) with the additional property that during a computation any cell of the \(\text{OCA}\) has the ability to dissolve itself, so-called shrinking one-way cellular automata (\(\text{SOCA}\)). It turns out that real-time \(\text{SOCA}\) are more powerful than real-time \(\text{OCA}\), since they can accept certain linear-time \(\text{OCA}\) languages. On the other hand, linear-time \(\text{OCA}\) are more powerful than real-time \(\text{SOCA}\), which is witnessed even by a unary language. Additionally, a construction is provided that enables real-time \(\text{SOCA}\) to accept the reversal of real-time iterative array languages. Finally, restricted real-time \(\text{SOCA}\) are investigated. We distinguish two limitations for the dissolving of cells. One restriction is to bound the total number of cells that are allowed to dissolve by some function. In this case, an infinite strict hierarchy of language classes is obtained. The second restriction is inspired by an approach to limit the amount of nondeterminism in \(\text{OCA}\). Compared with the first restriction, the total number of cells that may dissolve is still unbounded, but the number of time steps at which a cell may dissolve is bounded. The possibility to dissolve is allowed only in the first k time steps, where \(k\ge 0\) is some constant. For this mode of operation an infinite, tight, and strict hierarchy of language classes is obtained as well.     

Generic construction of an $$\mathrm {}$$-secure key exchange protocol in the standard model

LaMacchia, Lauter and Mityagin presented a strong security model for authenticated key agreement, namely the \(\mathrm {eCK}\) model. They also constructed a protocol, namely the NAXOS protocol, that enjoys a simple security proof in the \(\mathrm {eCK}\) model. However, the NAXOS protocol uses a random oracle-based technique to combine the long-term secret key and the per session randomness, so-called NAXOS trick, in order to achieve the \(\mathrm {eCK}\) security definition. For NAXOS trick-based protocols, the leakage of per session randomness modeled in the \(\mathrm {eCK}\) model is somewhat unnatural, because the \(\mathrm {eCK}\) model leaks per session randomness, while the output of the NAXOS trick computation remains safe. In this work, we present a standard model \(\mathrm {eCK}\)-secure protocol construction, eliminating the NAXOS trick. Moreover, our protocol is a generic construction, which can be instantiated with arbitrary suitable cryptographic primitives. Thus, we present a generic \(\mathrm {eCK}\)-secure, NAXOS-free, standard model key exchange protocol. To the best of our knowledge this is the first paper on generic transformation of a \(\mathrm {CCA2}\)-secure public-key encryption scheme to an \(\mathrm {eCK}\)-secure key exchange protocol in the standard model.     

On topological systems

We establish the reflectivity of the subcategories of \(T_{0}\) and sober topological systems in the category \(\mathbf {TopSys}\) of topological systems. We also introduce a Sierpinski object in the category \(\mathbf {TopSys}\) and point out its connection with \(T_{0}\) and sober topological systems and also with injective \(T_{0}\)-topological systems.     

Flexible bandwidth assignment with application to optical networks

We introduce two scheduling problems, the flexible bandwidth allocation problem (\(\textsc {FBAP}\)) and the flexible storage allocation problem (\(\textsc {FSAP}\)). In both problems, we have an available resource, and a set of requests, each consists of a minimum and a maximum resource requirement, for the duration of its execution, as well as a profit accrued per allocated unit of the resource. In \(\textsc {FBAP}\), the goal is to assign the available resource to a feasible subset of requests, such that the total profit is maximized, while in \(\textsc {FSAP}\) we also require that each satisfied request is given a contiguous portion of the resource. Our problems generalize the classic bandwidth allocation problem (BAP) and storage allocation problem (SAP) and are therefore \(\text {NP-hard}\). Our main results are a 3-approximation algorithm for \(\textsc {FBAP}\) and a \((3+\epsilon )\)-approximation algorithm for \(\textsc {FSAP}\), for any fixed \(\epsilon >0 \). These algorithms make nonstandard use of the local ratio technique. Furthermore, we present a \((2+\epsilon )\)-approximation algorithm for \(\textsc {SAP}\), for any fixed \(\epsilon >0 \), thus improving the best known ratio of \(\frac{2e-1}{e-1} + \epsilon \). Our study is motivated also by critical resource allocation problems arising in all-optical networks.     

Quantum Query Complexity of Almost All Functions with Fixed On-set Size

This paper considers the quantum query complexity of almost all functions in the set \({\mathcal{F}}_{N,M}\) of \({N}\)-variable Boolean functions with on-set size \({M (1\le M \le 2^{N}/2)}\), where the on-set size is the number of inputs on which the function is true. The main result is that, for all functions in \({\mathcal{F}}_{N,M}\) except its polynomially small fraction, the quantum query complexity is \({ \Theta\left(\frac{\log{M}}{c + \log{N} - \log\log{M}} + \sqrt{N}\right)}\) for a constant \({c > 0}\). This is quite different from the quantum query complexity of the hardest function in \({\mathcal{F}}_{N,M}\): \({\Theta\left(\sqrt{N\frac{\log{M}}{c + \log{N} - \log\log{M}}} + \sqrt{N}\right)}\). In contrast, almost all functions in \({\mathcal{F}}_{N,M}\) have the same randomized query complexity \({\Theta(N)}\) as the hardest one, up to a constant factor.     

Data assimilation and sampling in Banach spaces

This paper studies the problem of approximating a function f in a Banach space \(\mathcal{X}\) from measurements \(l_j(f)\), \(j=1,\ldots ,m\), where the \(l_j\) are linear functionals from \(\mathcal{X}^*\). Quantitative results for such recovery problems require additional information about the sought after function f. These additional assumptions take the form of assuming that f is in a certain model class \(K\subset \mathcal{X}\). Since there are generally infinitely many functions in K which share these same measurements, the best approximation is the center of the smallest ball B, called the Chebyshev ball, which contains the set \(\bar{K}\) of all f in K with these measurements. Therefore, the problem is reduced to analytically or numerically approximating this Chebyshev ball. Most results study this problem for classical Banach spaces \(\mathcal{X}\) such as the \(L_p\) spaces, \(1\le p\le \infty \), and for K the unit ball of a smoothness space in \(\mathcal{X}\). Our interest in this paper is in the model classes \(K=\mathcal{K}(\varepsilon ,V)\), with \(\varepsilon >0\) and V a finite dimensional subspace of \(\mathcal{X}\), which consists of all \(f\in \mathcal{X}\) such that \(\mathrm{dist}(f,V)_\mathcal{X}\le \varepsilon \). These model classes, called approximation sets, arise naturally in application domains such as parametric partial differential equations, uncertainty quantification, and signal processing. A general theory for the recovery of approximation sets in a Banach space is given. This theory includes tight a priori bounds on optimal performance and algorithms for finding near optimal approximations. It builds on the initial analysis given in Maday et al. (Int J Numer Method Eng 102:933–965, 2015) for the case when \(\mathcal{X}\) is a Hilbert space, and further studied in Binev et al. (SIAM UQ, 2015). It is shown how the recovery problem for approximation sets is connected with well-studied concepts in Banach space theory such as liftings and the angle between spaces. Examples are given that show how this theory can be used to recover several recent results on sampling and data assimilation.