General Independence Sets in Random Strongly Sparse Hypergraphs

We analyze the asymptotic behavior of the j-independence number of a random k-uniform hypergraph H(n, k, p) in the binomial model. We prove that in the strongly sparse case, i.e., where \(p = c/\left( \begin{gathered} n - 1 \hfill \\ k - 1 \hfill \\ \end{gathered} \right)\) for a positive constant 0 < c ≤ 1/(k ? 1), there exists a constant γ(k, j, c) > 0 such that the j-independence number α _j (H(n, k, p)) obeys the law of large numbers \(\frac{{{\alpha _j}\left( {H\left( {n,k,p} \right)} \right)}}{n}\xrightarrow{P}\gamma \left( {k,j,c} \right)asn \to + \infty \) Moreover, we explicitly present γ(k, j, c) as a function of a solution of some transcendental equation.     

Expansion of Self-Similar Functions in the Faber–Schauder System

Let Ω = A^N be a space of right-sided infinite sequences drawn from a finite alphabet A = {0,1}, N = {1,2,…}. Let ρ(x, y)Σ_k=1^∞|x _k ? y _k |2^?k be a metric on Ω = AN, and μ the Bernoulli measure on Ω with probabilities p₀, p₁ > 0, p₀ + p₁ = 1. Denote by B(x,ω) an open ball of radius r centered at ω. The main result of this paper \(\mu (B(\omega ,r))r + \sum\nolimits_{n = 0}^\infty {\sum\nolimits_{j = 0}^{{2^n} - 1} {{\mu _{n,j}}} } (\omega )\tau ({2^n}r - j)\), where τ(x) = 2min {x,1 ? x}, 0 ≤ x ≤ 1, (τ(x) = 0, if x < 0 or x > 1 ), \({\mu _{n,j}}(\omega ) = (1 - {p_{{\omega _{n + 1}}}})\prod _{k = 1}^n{p_{{\omega _k}}} \oplus {j_k}\), \(j = {j_1}{2^{n - 1}} + {j_2}{2^{n - 2}} + ... + {j_n}\). The family of functions 1, x, τ(2 ⁿ r ? j), j = 0,1,…, 2 ⁿ ? 1, n = 0,1,…, is the Faber–Schauder system for the space C([0,1]) of continuous functions on [0, 1]. We also obtain the Faber–Schauder expansion for Lebesgue’s singular function, Cezaro curves, and Koch–Peano curves. Article is published in the author’s wording.     

The Outer-connected Domination Number of Sierpiński-like Graphs

An outer-connected dominating set in a graph G = (V, E) is a set of vertices D ? V satisfying the condition that, for each vertex v ? D, vertex v is adjacent to some vertex in D and the subgraph induced by V?D is connected. The outer-connected dominating set problem is to find an outer-connected dominating set with the minimum number of vertices which is denoted by \(\tilde {\gamma }_{c}(G)\). In this paper, we determine \(\tilde {\gamma }_{c}(S(n,k))\), \(\tilde {\gamma }_{c}(S^{+}(n,k))\), \(\tilde {\gamma }_{c}(S^{++}(n,k))\), and \(\tilde {\gamma }_{c}(S_{n})\), where S(n, k), S ⁺(n, k), S ⁺⁺(n, k), and S _n are Sierpi\(\acute {\mathrm {n}}\)ski-like graphs.     

Polylogarithms and the Asymptotic Formula for the Moments of Lebesgue’s Singular Function

Recall that Lebesgue’s singular function L(t) is defined as the unique solution to the equation L(t) = qL(2t) + pL(2t ? 1), where p, q > 0, q = 1 ? p, p ≠ q. The variables M _n = ∫₀¹t ⁿ dL(t), n = 0,1,… are called the moments of the function The principal result of this work is \({M_n} = {n^{{{\log }_2}p}}{e^{ - \tau (n)}}(1 + O({n^{ - 0.99}}))\), where the function τ(x) is periodic in log₂x with the period 1 and is given as \(\tau (x) = \frac{1}{2}1np + \Gamma '(1)lo{g_2}p + \frac{1}{{1n2}}\frac{\partial }{{\partial z}}L{i_z}( - \frac{q}{p}){|_{z = 1}} + \frac{1}{{1n2}}\sum\nolimits_{k \ne 0} {\Gamma ({z_k})L{i_{{z_k} + 1}}( - \frac{q}{p})} {x^{ - {z_k}}}\), \({z_k} = \frac{{2\pi ik}}{{1n2}}\), k ≠ 0. The proof is based on poissonization and the Mellin transform.     

Greatest Lower Bound of System Failure Probability on a Special Time Interval Under Incomplete Information About the Distribution Function of the Time to Failure of the System

The author solves the problem of finding greatest lower bounds for the probability F (??) – F (u),0 < u <, ?? < ∞, where \( u= m-{\upsigma}_{\mu}3\sqrt{3},\kern0.5em \upupsilon = m+{\upsigma}_{\mu}3\sqrt{3},\kern0.5em \mathrm{and}\kern0.5em {\upsigma}_{\mu} \) is a fixed dispersion in the set of distribution functions F (x) of non-negative random variables with unimodal differentiable density with mode m and two first fixed moments μ ₁ and μ ₂. The case is considered where the mode coincides with the first moment: m = μ ₁. The greatest lower bound of all possible greatest lower bounds for this problem is obtained and it is nearly one, namely, 0.98430.     

Parallel Multi-Block ADMM with <Emphasis Type="Italic">o</Emphasis>(1 / <Emphasis Type="Italic">k</Emphasis>) Convergence

This paper introduces a parallel and distributed algorithm for solving the following minimization problem with linear constraints:

$$\begin{aligned} \text {minimize} ~~&f_1(\mathbf{x}_1) + \cdots + f_N(\mathbf{x}_N)\\ \text {subject to}~~&A_1 \mathbf{x}_1 ~+ \cdots + A_N\mathbf{x}_N =c,\\&\mathbf{x}_1\in {\mathcal {X}}_1,~\ldots , ~\mathbf{x}_N\in {\mathcal {X}}_N, \end{aligned}$$

where \(N \ge 2\), \(f_i\) are convex functions, \(A_i\) are matrices, and \({\mathcal {X}}_i\) are feasible sets for variable \(\mathbf{x}_i\). Our algorithm extends the alternating direction method of multipliers (ADMM) and decomposes the original problem into N smaller subproblems and solves them in parallel at each iteration. This paper shows that the classic ADMM can be extended to the N-block Jacobi fashion and preserve convergence in the following two cases: (i) matrices \(A_i\) are mutually near-orthogonal and have full column-rank, or (ii) proximal terms are added to the N subproblems (but without any assumption on matrices \(A_i\)). In the latter case, certain proximal terms can let the subproblem be solved in more flexible and efficient ways. We show that \(\Vert {\mathbf {x}}^{k+1} - {\mathbf {x}}^k\Vert _M^2\) converges at a rate of o(1 / k) where M is a symmetric positive semi-definte matrix. Since the parameters used in the convergence analysis are conservative, we introduce a strategy for automatically tuning the parameters to substantially accelerate our algorithm in practice. We implemented our algorithm (for the case ii above) on Amazon EC2 and tested it on basis pursuit problems with >300 GB of distributed data. This is the first time that successfully solving a compressive sensing problem of such a large scale is reported.

     

Mutually independent Hamiltonian cycles in dual-cubes

The hypercube family Q _n is one of the most well-known interconnection networks in parallel computers. With Q _n , dual-cube networks, denoted by DC _n , was introduced and shown to be a (n+1)-regular, vertex symmetric graph with some fault-tolerant Hamiltonian properties. In addition, DC _n ’s are shown to be superior to Q _n ’s in many aspects. In this article, we will prove that the n-dimensional dual-cube DC _n contains n+1 mutually independent Hamiltonian cycles for n≥2. More specifically, let v _i ∈V(DC _n ) for 0≤i≤|V(DC _n )|?1 and let \(\langle v_{0},v_{1},\ldots ,v_{|V(\mathit{DC}_{n})|-1},v_{0}\rangle\) be a Hamiltonian cycle of DC _n . We prove that DC _n contains n+1 Hamiltonian cycles of the form \(\langle v_{0},v_{1}^{k},\ldots,v_{|V(\mathit{DC}_{n})|-1}^{k},v_{0}\rangle\) for 0≤k≤n, in which v _i ^k ≠v _i ^k′ whenever k≠k′. The result is optimal since each vertex of DC _n has only n+1 neighbors.     

Ambiguity and Communication

The ambiguity of a nondeterministic finite automaton (NFA) N for input size n is the maximal number of accepting computations of N for inputs of size n. For every natural number k we construct a family \((L_{r}^{k}\;|\;r\in \mathbb{N})\) of languages which can be recognized by NFA’s with size k?poly(r) and ambiguity O(n ^k ), but \(L_{r}^{k}\) has only NFA’s with size exponential in r, if ambiguity o(n ^k ) is required. In particular, a hierarchy for polynomial ambiguity is obtained, solving a long standing open problem (Ravikumar and Ibarra, SIAM J. Comput. 19:1263–1282, 1989, Leung, SIAM J. Comput. 27:1073–1082, 1998).     

Accelerated image factorization based on improved NMF algorithm

Non-negative matrix factorization (NMF) is widely used in feature extraction and dimension reduction fields. Essentially, it is an optimization problem to determine two non-negative low rank matrices \(W_{m \times k}\) and \(H_{k \times n}\) for a given matrix \(A_{m \times n}\), satisfying \(A_{m \times n} \approx W_{m \times k}H_{k \times n}\). In this paper, a novel approach to improve the image decomposing and reconstruction effects by introducing the Singular Value Decomposing (SVD)-based initialization scheme of factor matrices W and H, and another measure called choosing rule to determine the optimum value of factor rank k, are proposed. The input image is first decomposed using SVD to get its singular values and corresponding eigenvectors. Then, the number of main components as the rank value k is extracted. Then, the singular values and corresponding eigenvectors are used to initialize W and H based on selected rank k. Finally, convergent results are obtained using multiplicative and additive update rules. However, iterative NMF algorithms’ convergence is very slow on most platforms limiting its practicality. To this end, a parallel implementation frame of described improved NMF algorithm using CUDA, a tool for algorithms parallelization on massively parallel processors, i.e., many-core graphics processors, is presented. Experimental results show that our approach can get better decomposing effect than traditional NMF implementations and dramatic accelerate rate comparing to serial schemes as well as existing distributed-system implementations.     

Knowledge State Algorithms

We introduce the novel concept of knowledge states. The knowledge state approach can be used to construct competitive randomized online algorithms and study the trade-off between competitiveness and memory. Many well-known algorithms can be viewed as knowledge state algorithms. A knowledge state consists of a distribution of states for the algorithm, together with a work function which approximates the conditional obligations of the adversary. When a knowledge state algorithm receives a request, it then calculates one or more “subsequent” knowledge states, together with a probability of transition to each. The algorithm uses randomization to select one of those subsequents to be the new knowledge state. We apply this method to randomized k-paging. The optimal minimum competitiveness of any randomized online algorithm for the k-paging problem is the kth harmonic number, \(H_{k}=\sum^{k}_{i=1}\frac{1}{i}\). Existing algorithms which achieve that optimal competitiveness must keep bookmarks, i.e., memory of the names of pages not in the cache. An H _k -competitive randomized algorithm for that problem which uses O(k) bookmarks is presented, settling an open question by Borodin and El-Yaniv. In the special cases where k=2 and k=3, solutions are given using only one and two bookmarks, respectively.     

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.     

Tracking frequent items over distributed probabilistic data

Tracking frequent items (also called heavy hitters) is one of the most fundamental queries in real-time data due to its wide applications, such as logistics monitoring, association rule based analysis, etc. Recently, with the growing popularity of Internet of Things (IoT) and pervasive computing, a large amount of real-time data is usually collected from multiple sources in a distributed environment. Unfortunately, data collected from each source is often uncertain due to various factors: imprecise reading, data integration from multiple sources (or versions), transmission errors, etc. In addition, due to network delay and limited by the economic budget associated with large-scale data communication over a distributed network, an essential problem is to track the global frequent items from all distributed uncertain data sites with the minimum communication cost. In this paper, we focus on the problem of tracking distributed probabilistic frequent items (TDPF). Specifically, given k distributed sites S = {S ₁, … , S _k }, each of which is associated with an uncertain database \(\mathcal {D}_{i}\) of size n _i , a centralized server (or called a coordinator) H, a minimum support ratio r, and a probabilistic threshold t, we are required to find a set of items with minimum communication cost, each item X of which satisfies P r(s u p(X) ≥ r × N) > t, where s u p(X) is a random variable to describe the support of X and \(N={\sum }_{i=1}^{k}n_{i}\). In order to reduce the communication cost, we propose a local threshold-based deterministic algorithm and a sketch-based sampling approximate algorithm, respectively. The effectiveness and efficiency of the proposed algorithms are verified with extensive experiments on both real and synthetic uncertain datasets.     

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

On Fixed Cost k-Flow Problems

In the Fixed Cost k-Flow problem, we are given a graph G = (V, E) with edge-capacities {u _e ∣e ∈ E} and edge-costs {c _e ∣e ∈ E}, source-sink pair s, t ∈ V, and an integer k. The goal is to find a minimum cost subgraph H of G such that the minimum capacity of an st-cut in H is at least k. By an approximation-preserving reduction from Group Steiner Tree problem to Fixed Cost k-Flow, we obtain the first polylogarithmic lower bound for the problem; this also implies the first non-constant lower bounds for the Capacitated Steiner Network and Capacitated Multicommodity Flow problems. We then consider two special cases of Fixed Cost k-Flow. In the Bipartite Fixed-Cost k-Flow problem, we are given a bipartite graph G = (A ∪ B, E) and an integer k > 0. The goal is to find a node subset S ? A ∪ B of minimum size |S| such G has k pairwise edge-disjoint paths between S ∩ A and S ∩ B. We give an \(O(\sqrt {k\log k})\) approximation for this problem. We also show that we can compute a solution of optimum size with Ω(k/polylog(n)) paths, where n = |A| + |B|. In the Generalized-P2P problem we are given an undirected graph G = (V, E) with edge-costs and integer charges {b _v : v ∈ V}. The goal is to find a minimum-cost spanning subgraph H of G such that every connected component of H has non-negative charge. This problem originated in a practical project for shift design [11]. Besides that, it generalizes many problems such as Steiner Forest, k-Steiner Tree, and Point to Point Connection. We give a logarithmic approximation algorithm for this problem. Finally, we consider a related problem called Connected Rent or Buy Multicommodity Flow and give a log^3+?? n approximation scheme for it using Group Steiner Tree techniques.     

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.     

Faster Parameterized Algorithms for <Emphasis Type="SmallCaps">Minimum Fill-in</Emphasis>

We present two parameterized algorithms for the Minimum Fill-in problem, also known as Chordal Completion: given an arbitrary graph G and integer k, can we add at most k edges to G to obtain a chordal graph? Our first algorithm has running time \(\mathcal {O}(k^{2}nm+3.0793^{k})\), and requires polynomial space. This improves the base of the exponential part of the best known parameterized algorithm time for this problem so far. We are able to improve this running time even further, at the cost of more space. Our second algorithm has running time \(\mathcal {O}(k^{2}nm+2.35965^{k})\) and requires \(\mathcal {O}^{\ast}(1.7549^{k})\) space. To achieve these results, we present a new lemma describing the edges that can safely be added to achieve a chordal completion with the minimum number of edges, regardless of k.     

Formule di quadratura di tipo gaussiano con valori delle derivate dell'integrando

The coefficientsA _hi (m,s) and the nodesx _i (m,s) for Gaussian-type quadrature formulae

$$\int\limits_{ - 1}^1 {f(x)dx = \mathop \sum \limits_{h = 0}^{2s} \mathop \sum \limits_{i = 1}^m } A_{hi} \cdot f^{(h)} (x_i )$$     

Generation and distillation of non-Gaussian entanglement from nonclassical photon statistics

With a product state of the form \({{\rho}_{\rm in} = {\rho}_{a} \otimes |0 \rangle_b {_b} \langle 0|}\) as input to a beam splitter, the output two-mode state ρ _out is shown to be negative under partial transpose (NPT) whenever the photon number distribution (PND) statistics { p(n _a ) } associated with the possibly mixed state ρ _a of the input a-mode is antibunched or otherwise nonclassical, i.e., whenever { p(n _a ) } fails to respect any one of an infinite sequence of necessary and sufficient classicality conditions. Negativity under partial transpose turns out to be a necessary and sufficient test for entanglement of ρ _out which is generically non-Gaussian. The output of a PND distribution is further shown to be distillable if any one of an infinite sequence of three term classicality conditions is violated.     

A Nyström method for a class of Fredholm integral equations on the real semiaxis

A class of Fredholm integral equations of the second kind, with respect to the exponential weight function \(w(x)=\exp (-(x^{-\alpha }+x^\beta ))\), \(\alpha >0\), \(\beta >1\), on \((0,+\infty )\), is considered. The kernel k(x, y) and the function g(x) in such kind of equations,

$$\begin{aligned} f(x)-\mu \int _0^{+\infty }k(x,y)f(y)w(y)\mathrm {d}y =g(x),\quad x\in (0,+\infty ), \end{aligned}$$

can grow exponentially with respect to their arguments, when they approach to \(0^+\) and/or \(+\infty \). We propose a simple and suitable Nyström-type method for solving these equations. The study of the stability and the convergence of this numerical method in based on our results on weighted polynomial approximation and “truncated” Gaussian rules, recently published in Mastroianni and Notarangelo (Acta Math Hung, 142:167–198, 2014), and Mastroianni, Milovanovi? and Notarangelo (IMA J Numer Anal 34:1654–1685, 2014) respectively. Moreover, we prove a priori error estimates and give some numerical examples. A comparison with other Nyström methods is also included.

     

An uncertainty relation in terms of generalized metric adjusted skew information and correlation measure

The uncertainty principle in quantum mechanics is a fundamental relation with different forms, including Heisenberg’s uncertainty relation and Schrödinger’s uncertainty relation. In this paper, we prove a Schrödinger-type uncertainty relation in terms of generalized metric adjusted skew information and correlation measure by using operator monotone functions, which reads,

$$\begin{aligned} U_\rho ^{(g,f)}(A)U_\rho ^{(g,f)}(B)\ge \frac{f(0)^2l}{k}\left| \mathrm {Corr}_\rho ^{s(g,f)}(A,B)\right| ^2 \end{aligned}$$

for some operator monotone functions f and g, all n-dimensional observables A, B and a non-singular density matrix \(\rho \). As applications, we derive some new uncertainty relations for Wigner–Yanase skew information and Wigner–Yanase–Dyson skew information.