Truss decomposition of uncertain graphs

The k-truss of a graph is the largest edge-induced subgraph such that every edge is contained in at least k triangles within the subgraph, where a triangle is a cycle consisting of three vertices. As a new notion of cohesive subgraphs, truss has recently attracted a lot of research attentions in the database and data mining fields. At the same time, uncertainty is an intrinsic property of massive graph data, and truss decomposition (i.e., finding all k-trusses of a graph) has become a key primitive on uncertain graphs. In this paper, we study the truss decomposition problem on uncertain graphs, that is, finding all highly probable k-trusses of an uncertain graph. We first give an formal statement of the truss decomposition problem on uncertain graphs. Then, we prove that the truss decomposition of an uncertain graph attains two elegant properties, namely uniqueness and hierarchy. We show that the truss decomposition of an uncertain graph can be found in \(O(m^{1.5}Q)\) time by proposing an in-memory algorithm called \(\mathtt {TD_{mem}}\), where m is the number of edges of the uncertain graph, and Q is at most the maximum number of common neighbors of the endpoints of an edge. When an uncertain graph is too large to fit into main memory, we propose an external-memory algorithm \(\mathtt {TD_{I/O}}\) to find the truss decomposition of the uncertain graph. Extensive experiments have been carried out to evaluate the practical performance of the proposed algorithms. The experimental results verify that both \(\mathtt {TD_{mem}}\) and \(\mathtt {TD_{I/O}}\) are efficient when an uncertain graph is small enough to fit into main memory, and that \(\mathtt {TD_{I/O}}\) is much faster than \(\mathtt {TD_{mem}}\) when the graph is too large to fit into main memory.     

Entanglement witness criteria of strong-<Emphasis Type="Italic">k</Emphasis>-separability for multipartite quantum states

Let \(H_{1}, H_{2},\ldots ,H_{n}\) be separable complex Hilbert spaces with \(\dim H_{i}\ge 2\) and \(n\ge 2\). Assume that \(\rho \) is a state in \(H=H_1\otimes H_2\otimes \cdots \otimes H_n\). \(\rho \) is called strong-k-separable \((2\le k\le n)\) if \(\rho \) is separable for any k-partite division of H. In this paper, an entanglement witnesses criterion of strong-k-separability is obtained, which says that \(\rho \) is not strong-k-separable if and only if there exist a k-division space \(H_{m_{1}}\otimes \cdots \otimes H_{m_{k}}\) of H, a finite-rank linear elementary operator positive on product states \(\Lambda :\mathcal {B}(H_{m_{2}}\otimes \cdots \otimes H_{m_{k}})\rightarrow \mathcal {B}(H_{m_{1}})\) and a state \(\rho _{0}\in \mathcal {S}(H_{m_{1}}\otimes H_{m_{1}})\), such that \(\mathrm {Tr}(W\rho )<0\), where \(W=(\mathrm{Id}\otimes \Lambda ^{\dagger })\rho _{0}\) is an entanglement witness. In addition, several different methods of constructing entanglement witnesses for multipartite states are also given.     

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^?.     

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.     

Mutually unbiased maximally entangled bases in $$\mathbb {C}^d\otimes \mathbb {C}^d$$

We study mutually unbiased maximally entangled bases (MUMEB’s) in bipartite system \(\mathbb {C}^d\otimes \mathbb {C}^d (d \ge 3)\). We generalize the method to construct MUMEB’s given in Tao et al. (Quantum Inf Process 14:2291–2300, 2015), by using any commutative ring R with d elements and generic character of \((R,+)\) instead of \(\mathbb {Z}_d=\mathbb {Z}/d\mathbb {Z}\). Particularly, if \(d=p_1^{a_1}p_2^{a_2}\ldots p_s^{a_s}\) where \(p_1, \ldots , p_s\) are distinct primes and \(3\le p_1^{a_1}\le \cdots \le p_s^{a_s}\), we present \(p_1^{a_1}-1\) MUMEB’s in \(\mathbb {C}^d\otimes \mathbb {C}^d\) by taking \(R=\mathbb {F}_{p_1^{a_1}}\oplus \cdots \oplus \mathbb {F}_{p_s^{a_s}}\), direct sum of finite fields (Theorem 3.3).     

Two Mixed Finite Element Methods for Time-Fractional Diffusion Equations

Based on spatial conforming and nonconforming mixed finite element methods combined with classical L1 time stepping method, two fully-discrete approximate schemes with unconditional stability are first established for the time-fractional diffusion equation with Caputo derivative of order \(0<\alpha <1\). As to the conforming scheme, the spatial global superconvergence and temporal convergence order of \(O(h^2+\tau ^{2-\alpha })\) for both the original variable u in \(H^1\)-norm and the flux \(\vec {p}=\nabla u\) in \(L^2\)-norm are derived by virtue of properties of bilinear element and interpolation postprocessing operator, where h and \(\tau \) are the step sizes in space and time, respectively. At the same time, the optimal convergence rates in time and space for the nonconforming scheme are also investigated by some special characters of \(\textit{EQ}_1^{\textit{rot}}\) nonconforming element, which manifests that convergence orders of \(O(h+\tau ^{2-\alpha })\) and \(O(h^2+\tau ^{2-\alpha })\) for the original variable u in broken \(H^1\)-norm and \(L^2\)-norm, respectively, and approximation for the flux \(\vec {p}\) converging with order \(O(h+\tau ^{2-\alpha })\) in \(L^2\)-norm. Numerical examples are provided to demonstrate the theoretical analysis.     

Counter machines and crystallographic structures

One way to depict a crystallographic structure is by a periodic (di)graph, i.e., a graph whose group of automorphisms has a translational subgroup of finite index acting freely on the structure. We establish a relationship between periodic graphs representing crystallographic structures and an infinite hierarchy of intersection languages \(\mathcal {DCL}_d,\,d=0,1,2,\ldots \), within the intersection classes of deterministic context-free languages. We introduce a class of counter machines that accept these languages, where the machines with d counters recognize the class \(\mathcal {DCL}_d\). An intersection of d languages in \(\mathcal {DCL}_1\) defines \(\mathcal {DCL}_d\). We prove that there is a one-to-one correspondence between sets of walks starting and ending in the same unit of a d-dimensional periodic (di)graph and the class of languages in \(\mathcal {DCL}_d\). The proof uses the following result: given a digraph \(\Delta \) and a group G, there is a unique digraph \(\Gamma \) such that \(G\le \mathrm{Aut}\,\Gamma ,\,G\) acts freely on the structure, and \(\Gamma /G \cong \Delta \).     

About the Decidability of Polyhedral Separability in the Lattice $$\mathbb {Z}^d$$

The recognition of primitives in digital geometry is deeply linked with separability problems. This framework leads us to consider the following problem of pattern recognition : given a finite lattice set \(S\subset \mathbb {Z}^d\) and a positive integer n, is it possible to separate S from \(\mathbb {Z}^d \setminus S\) by n half-spaces? In other words, does there exist a polyhedron P defined by at most n half-spaces satisfying \(P\cap \mathbb {Z}^d = S\)? The difficulty comes from the infinite number of constraints generated by all the points of \(\mathbb {Z}^d\setminus S\). It makes the decidability of the problem non-straightforward since the classical algorithms of polyhedral separability can not be applied in this framework. We conjecture that the problem is nevertheless decidable and prove it under some assumptions: in arbitrary dimension, if the interior of the convex hull of S contains at least one lattice point or if the dimension d is 2 or if the dimension \(d=3\) and S is not in a specific configuration of lattice width 0 or 1. The proof strategy is to reduce the set of outliers \(\mathbb {Z}^d\setminus S\) to its minimal elements according to a partial order “is in the shadow of.” These minimal elements are called the lattice jewels of S. We prove that under some assumptions, the set S admits only a finite number of lattice jewels. The result about the decidability of the problem is a corollary of this fundamental property.     

Partially Ordered Connectives and Monadic Monotone Strict NP

Motivated by constraint satisfaction problems, Feder and Vardi (SIAM Journal of Computing, 28, 57–104, 1998) set out to search for fragments \({\mathcal{L}}\) of \(\Sigma_1^1\) satisfying the dichotomy property: every problem definable in \({\mathcal{L}}\) is either in P or else NP-complete. Feder and Vardi considered in this connection two logics, strict NP (or SNP) and monadic, monotone, strict NP without inequalities (or MMSNP). The former consists of formulas of the form \(\exists \vec{X}\forall \vec{x} \phi\), where \(\phi\) is a quantifier-free formula in a relational vocabulary; and the latter is the fragment of SNP whose formulas involve only negative occurrences of relation symbols, only monadic second-order quantifiers, and no occurrences of the equality symbol. It remains an open problem whether MMSNP enjoys the dichotomy property. In the present paper, SNP and MMSNP are characterized in terms of partially ordered connectives. More specifically, SNP is characterized using the logic D of partially ordered connectives introduced in Blass and Gurevich (Annals of Pure and Applied Logic, 32, 1–16, 1986), Sandu and Väänänen (Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 38, 361–372 1992), and MMSNP employing a generalization C of D introduced in the present paper.     

New quantum codes from dual-containing cyclic codes over finite rings

Let \(R=\mathbb {F}_{2^{m}}+u\mathbb {F}_{2^{m}}+\cdots +u^{k}\mathbb {F}_{2^{m}}\), where \(\mathbb {F}_{2^{m}}\) is the finite field with \(2^{m}\) elements, m is a positive integer, and u is an indeterminate with \(u^{k+1}=0.\) In this paper, we propose the constructions of two new families of quantum codes obtained from dual-containing cyclic codes of odd length over R. A new Gray map over R is defined, and a sufficient and necessary condition for the existence of dual-containing cyclic codes over R is given. A new family of \(2^{m}\)-ary quantum codes is obtained via the Gray map and the Calderbank–Shor–Steane construction from dual-containing cyclic codes over R. In particular, a new family of binary quantum codes is obtained via the Gray map, the trace map and the Calderbank–Shor–Steane construction from dual-containing cyclic codes over R.     

A general framework for architecture composability

Architectures depict design principles: paradigms that can be understood by all, allow thinking on a higher plane and avoiding low-level mistakes. They provide means for ensuring correctness by construction by enforcing global properties characterizing the coordination between components. An architecture can be considered as an operator A that, applied to a set of components \({\mathcal{B}}\), builds a composite component \({A(\mathcal{B})}\) meeting a characteristic property \({\Phi}\). Architecture composability is a basic and common problem faced by system designers. In this paper, we propose a formal and general framework for architecture composability based on an associative, commutative and idempotent architecture composition operator \({\oplus}\). The main result is that if two architectures A ₁ and A ₂ enforce respectively safety properties \({\Phi_{1}}\) and \({\Phi_{2}}\), the architecture \({A_{1} \oplus A_{2}}\) enforces the property \({\Phi_{1} \land \Phi_{2}}\), that is both properties are preserved by architecture composition. We also establish preservation of liveness properties by architecture composition. The presented results are illustrated by a running example and a case study.     

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.     

The remote set problem on lattices

We initiate studying the Remote Set Problem (\({\mathsf{RSP}}\)) on lattices, which given a lattice asks to find a set of points containing a point which is far from the lattice. We show a polynomial-time deterministic algorithm that on rank n lattice \({\mathcal{L}}\) outputs a set of points, at least one of which is \({\sqrt{\log n / n} \cdot \rho(\mathcal{L})}\) -far from \({\mathcal{L}}\) , where \({\rho(\mathcal{L})}\) stands for the covering radius of \({\mathcal{L}}\) (i.e., the maximum possible distance of a point in space from \({\mathcal{L}}\)). As an application, we show that the covering radius problem with approximation factor \({\sqrt{n / \log n}}\) lies in the complexity class \({\mathsf{NP}}\) , improving a result of Guruswami et al. (Comput Complex 14(2): 90–121, 2005) by a factor of \({\sqrt{\log n}}\) .Our results apply to any \({\ell_p}\) norm for \({2 \leq p \leq \infty}\) with the same approximation factors (except a loss of \({\sqrt{\log \log n}}\) for \({p = \infty}\)). In addition, we show that the output of our algorithm for \({\mathsf{RSP}}\) contains a point whose \({\ell_2}\) distance from \({\mathcal{L}}\) is at least \({(\log n/n)^{1/p} \cdot \rho^{(p)}(\mathcal{L})}\) , where \({\rho^{(p)}(\mathcal{L})}\) is the covering radius of \({\mathcal{L}}\) measured with respect to the \({\ell_p}\) norm. The proof technique involves a theorem on balancing vectors due to Banaszczyk (Random Struct Algorithms 12(4):351–360, 1998) and the “six standard deviations” theorem of Spencer (Trans Am Math Soc 289(2):679–706, 1985).     

In All But Finitely Many Possible Worlds: Model-Theoretic Investigations on ‘<Emphasis Type="Italic">Overwhelming Majority</Emphasis>’ Default Conditionals

Defeasible conditionals are statements of the form ‘if A then normally B’. One plausible interpretation introduced in nonmonotonic reasoning dictates that (\(A\Rightarrow B\)) is true iff B is true in ‘most’ A-worlds. In this paper, we investigate defeasible conditionals constructed upon a notion of ‘overwhelming majority’, defined as ‘truth in a cofinite subset of \(\omega \)’, the first infinite ordinal. One approach employs the modal logic of the frame \((\omega , <)\), used in the temporal logic of discrete linear time. We introduce and investigate conditionals, defined modally over \((\omega , <)\); several modal definitions of the conditional connective are examined, with an emphasis on the nonmonotonic ones. An alternative interpretation of ‘majority’ as sets cofinal (in \(\omega \)) rather than cofinite (subsets of \(\omega \)) is examined. For these modal approaches over \((\omega , <)\), a decision procedure readily emerges, as the modal logic \({\mathbf {K4DLZ}}\) of this frame is well-known and a translation of the conditional sentences can be mechanically checked for validity; this allows also for a quick proof of \(\mathsf {NP}\)-completeness of the satisfiability problem for these logics. A second approach employs the conditional version of Scott-Montague semantics, in the form of \(\omega \)-many possible worlds, endowed with neighborhoods populated by collections of cofinite subsets of \(\omega \). This approach gives rise to weak conditional logics, as expected. The relative strength of the conditionals introduced is compared to (the conditional logic ‘equivalent’ of) KLM logics and other conditional logics in the literature.     

Monogamy and polygamy for multi-qubit W-class states using convex-roof extended negativity of assistance and Rényi-$$\alpha $$ entropy

We present some new analytical polygamy inequalities satisfied by the x-th power of convex-roof extended negativity of assistance with \(x\ge 2\) and \(x\le 0\) for multi-qubit generalized W-class states. Using Rényi-\(\alpha \) entropy (R\(\alpha \)E) with \(\alpha \in [(\sqrt{7}-1)/2, (\sqrt{13}-1)/2]\), we prove new monogamy and polygamy relations. We further show that the monogamy inequality also holds for the \(\mu \)th power of Rényi-\(\alpha \) entanglement. Moreover, we study two examples in multipartite higher-dimensional system for those new inequalities.     

Connecting unextendible maximally entangled base with partial Hadamard matrices

We study the unextendible maximally entangled bases (UMEB) in \(\mathbb {C}^{d}\bigotimes \mathbb {C}^{d}\) and connect the problem to the partial Hadamard matrices. We show that for a given special UMEB in \(\mathbb {C}^{d}\bigotimes \mathbb {C}^{d}\), there is a partial Hadamard matrix which cannot be extended to a Hadamard matrix in \(\mathbb {C}^{d}\). As a corollary, any \((d-1)\times d\) partial Hadamard matrix can be extended to a Hadamard matrix, which answers a conjecture about \(d=5\). We obtain that for any d there is a UMEB except for \(d=p\ \text {or}\ 2p\), where \(p\equiv 3\mod 4\) and p is a prime. The existence of different kinds of constructions of UMEBs in \(\mathbb {C}^{nd}\bigotimes \mathbb {C}^{nd}\) for any \(n\in \mathbb {N}\) and \(d=3\times 5 \times 7\) is also discussed.     

Tighter entanglement monogamy relations of qubit systems

Monogamy relations characterize the distributions of entanglement in multipartite systems. We investigate monogamy relations related to the concurrence C and the entanglement of formation E. We present new entanglement monogamy relations satisfied by the \(\alpha \)-th power of concurrence for all \(\alpha \ge 2\), and the \(\alpha \)-th power of the entanglement of formation for all \(\alpha \ge \sqrt{2}\). These monogamy relations are shown to be tighter than the existing ones.     

Actions Arising from Intersection and Union

An action is a pair of sets, C and S, and a function \(f:C\times S \rightarrow C\). Rothschild and Yalcin gave a simple axiomatic characterization of those actions arising from set intersection, i.e. for which the elements of C and S can be identified with sets in such a way that elements of S act on elements of C by intersection. We introduce and axiomatically characterize two natural classes of actions which arise from set intersection and union. In the first class, the \(\uparrow \!\!\downarrow \)-actions, each element of S is identified with a pair of sets \((s^\downarrow ,s^\uparrow )\), which act on a set c by intersection with \(s^\downarrow \) and union with \(s^\uparrow \). In the second class, the \(\uparrow \!\!\downarrow \)-biactions, each element of S is labeled as an intersection or a union, and acts accordingly on C. We give intuitive examples of these actions, one involving conversations and another a university’s changing student body. The examples give some motivation for considering these actions, and also help give intuitive readings of the axioms. The class of \(\uparrow \!\!\downarrow \)-actions is closely related to a class of single-sorted algebras, which was previously treated by Margolis et al., albeit in another guise (hyperplane arrangements), and we note this connection. Along the way, we make some useful, though very general, observations about axiomatization and representation problems for classes of algebras.     

A Neumann series of Bessel functions representation for solutions of Sturm–Liouville equations

A Neumann series of Bessel functions (NSBF) representation for solutions of Sturm–Liouville equations and for their derivatives is obtained. The representation possesses an attractive feature for applications: for all real values of the spectral parameter \(\omega \) the estimate of the difference between the exact solution and the approximate one (the truncated NSBF) depends on N (the truncation parameter) and the coefficients of the equation and does not depend on \(\omega \). A similar result is valid when \(\omega \in {\mathbb {C}}\) belongs to a strip \(\left| \hbox {Im }\omega \right| <C\). This feature makes the NSBF representation especially useful for applications requiring computation of solutions for large intervals of \(\omega \). Error and decay rate estimates are obtained. An algorithm for solving initial value, boundary value or spectral problems for the Sturm–Liouville equation is developed and illustrated on a test problem.