List decoding for a multiple access hyperchannel

We obtain bounds on the rate of (optimal) list-decoding codes with a fixed list size L ≥ 1 for a q-ary multiple access hyperchannel (MAHC) with s ≥ 2 inputs and one output. By definition, an output signal of this channel is the set of symbols of a q-ary alphabet that occur in at least one of the s input signals. For example, in the case of a binary MAHC, where q = 2, an output signal takes values in the ternary alphabet {0, 1, {0, 1}}; namely, it equals 0 (1) if all the s input signals are 0 (1) and equals {0, 1} otherwise. Previously, upper and lower bounds on the code rate for a q-ary MAHC were studied for L ≥ 1 and q = 2, and also for the nonbinary case q ≥ 3 for L = 1 only, i.e., for so-called frameproof codes. Constructing upper and lower bounds on the rate for the general case of L ≥ 1 and q ≥ 2 in the present paper is based on a substantial development of methods that we designed earlier for the classical binary disjunctive multiple access channel.     

On kernel engineering via Paley–Wiener

A radial basis function approximation takes the form

$s(x)=\sum_{k=1}^na_k\phi(x-b_k),\quad x\in {\mathbb{R}}^d,$

where the coefficients a ₁,…,a _n are real numbers, the centres b ₁,…,b _n are distinct points in ? ^d , and the function φ:? ^d →? is radially symmetric. Such functions are highly useful in practice and enjoy many beautiful theoretical properties. In particular, much work has been devoted to the polyharmonic radial basis functions, for which φ is the fundamental solution of some iterate of the Laplacian. In this note, we consider the construction of a rotation-invariant signed (Borel) measure μ for which the convolution ψ=μ φ is a function of compact support, and when φ is polyharmonic. The novelty of this construction is its use of the Paley–Wiener theorem to identify compact support via analysis of the Fourier transform of the new kernel ψ, so providing a new form of kernel engineering.

     

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.     

L-quantum spacesL-量子空间

In this paper, based on a complete residuated lattice L, we introduce the definitions of L-quantum spaces and continuous mappings. Then we establish an adjunction between the category of stratified L-quantum spaces and the opposite category of two-sided L-quantales. We also prove that the category of sober L-quantum spaces is dually equivalent to the category of spatial two-sided L-quantales.     

On the effect of the deployment setting on broadcasting in Euclidean radio networks

The paper studies broadcasting in radio networks whose stations are represented by points in the Euclidean plane (each station knows its own coordinates). In any given time step, a station can either receive or transmit. A message transmitted from station v is delivered to every station u at distance at most 1 from v, but u successfully hears the message if and only if v is the only station at distance at most 1 from u that transmitted in this time step. A designated source station has a message that should be disseminated throughout the network. All stations other than the source are initially idle and wake up upon the first time they hear the source message. It is shown in [17] that the time complexity of deterministic broadcasting algorithms depends on two parameters of the network, namely, its diameter (in hops) D and a lower bound d on the Euclidean distance between any two stations. The inverse of d is called the granularity of the network, denoted by g. Specifically, the authors of [17] present a deterministic broadcasting algorithm that works in time O (Dg) and prove that every broadcasting algorithm requires \(\varOmega \left( D \sqrt{g} \right) \) time. In this paper, we distinguish between the arbitrary deployment setting, originally studied in [17], in which stations can be placed everywhere in the plane, and the new grid deployment setting, in which stations are only allowed to be placed on a d-spaced grid. Does the latter (more restricted) setting provide any speedup in broadcasting time complexity? Although the O (Dg) broadcasting algorithm of [17] works under the (original) arbitrary deployment setting, it turns out that the \(\varOmega \left( D \sqrt{g} \right) \) lower bound remains valid under the grid deployment setting. Still, the above question is left unanswered. The current paper answers this question affirmatively by presenting a provable separation between the two deployment settings. We establish a tight lower bound on the time complexity of deterministic broadcasting algorithms under the arbitrary deployment setting proving that broadcasting cannot be completed in less than \(\varOmega (D g)\) time. For the grid deployment setting, we develop a deterministic broadcasting algorithm that runs in time \(O \left( D g^{5 / 6} \log g \right) \), thus breaking the linear dependency on g.     

A Polynomial-Time Approximation Algorithm for One Problem Simulating the Search in a Time Series for the Largest Subsequence of Similar Elements

We analyze the mathematical aspects of the data analysis problem consisting in the search (selection) for a subset of similar elements in a group of objects. The problem arises, in particular, in connection with the analysis of data in the form of time series (discrete signals). One of the problems in modeling this challenge is considered, namely, the problem of searching in a finite sequence of points from the Euclidean space for the subsequence with the greatest number of terms such that the quadratic spread of the elements of this subsequence with respect to its unknown centroid does not exceed a given percentage of the quadratic spread of elements of the input sequence with respect to its centroid. It is shown that the problem is strongly NP-hard. A polynomial-time approximation algorithm is proposed. This algorithm either establishes that the problem has no solution or finds a 1/2-approximate solution if the length M^* of the optimal subsequence is even, or it yields a \(\frac{1}{2}\left(\begin{array}{c}1-\frac{1}{M^*}\\ \end{array}\right)\)-approximate solution if M* is odd. The time complexity of the algorithm is O(N³(N²+q)), where N is the number of points in the input sequence and q is the space dimension. The results of numerical simulation that demonstrate the effectiveness of the algorithm are presented.     

Resource allocation in cooperative cognitive radio networks towards secure communications for maritime big data systems

In this paper, an innovative framework labeled as cooperative cognitive maritime big data systems (CCMBDSs) on the sea is developed to provide opportunistic channel access and secure communication. A two-phase frame structure is applied to let Secondary users (SUs) entirely utilize the transmission opportunities for a portion of time as the reward by cooperation with Primary users (PUs). Amplify-and-forward (AF) relaying mode is exploited in SU nodes, and Backward induction method based Stackelberg game is employed to achieve optimal determination of SU, power consumption and time portion of cooperation both for non-secure communication scenario and secure communication. Specifically, a jammer-based secure communications scheme is developed to maximize the secure utility of PU, to confront of the situation that the eavesdropper could overheard the signals from SU _i and the jammer. Close-form solutions for the best access time portion as well as the power for SU _i and jammer are derived to realize the Nash Equilibrium. Simulation results validate the effectiveness of our proposed strategy.     

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.     

Towards scalable synthesis of stochastic control systems

Formal synthesis approaches over stochastic systems have received significant attention in the past few years, in view of their ability to provide provably correct controllers for complex logical specifications in an automated fashion. Examples of complex specifications include properties expressed as formulae in linear temporal logic (LTL) or as automata on infinite strings. A general methodology to synthesize controllers for such properties resorts to symbolic models of the given stochastic systems. Symbolic models are finite abstractions of the given concrete systems with the property that a controller designed on the abstraction can be refined (or implemented) into a controller on the original system. Although the recent development of techniques for the construction of symbolic models has been quite encouraging, the general goal of formal synthesis over stochastic control systems is by no means solved. A fundamental issue with the existing techniques is the known “curse of dimensionality,” which is due to the need to discretize state and input sets. Such discretization generally results in an exponential complexity over the number of state and input variables in the concrete system. In this work we propose a novel abstraction technique for incrementally stable stochastic control systems, which does not require state-space discretization but only input set discretization, and that can be potentially more efficient (and thus scalable) than existing approaches. We elucidate the effectiveness of the proposed approach by synthesizing a schedule for the coordination of two traffic lights under some safety and fairness requirements for a road traffic model. Further we argue that this 5-dimensional linear stochastic control system cannot be studied with existing approaches based on state-space discretization due to the very large number of generated discrete states.     

Perceptrons of large weight

A threshold gate is a linear combination of input variables with integer coefficients (weights). It outputs 1 if the sum is positive. The maximum absolute value of the coefficients of a threshold gate is called its weight. A degree-d perceptron is a Boolean circuit of depth 2 with a threshold gate at the top and any Boolean elements of fan-in at most d at the bottom level. The weight of a perceptron is the weight of its threshold gate.For any constant d ≥ 2 independent of the number of input variables n, we construct a degree-d perceptron that requires weights of at least \(n^{\Omega (n^d )} \); i.e., the weight of any degree-d perceptron that computes the same Boolean function must be at least \(n^{\Omega (n^d )} \). This bound is tight: any degree-d perceptron is equivalent to a degree-d perceptron of weight \(n^{O(n^d )} \). For the case of threshold gates (i.e., d = 1), the result was proved by Håstad in [2]; we use Håstad’s technique.     

Symmetric Masks for In-fill Pixel Interpolation on Discrete <Emphasis Type="Italic">p</Emphasis>:<Emphasis Type="Italic">q</Emphasis> Lattices

A 2D p:q lattice contains image intensity entries at pixels located at regular, staggered intervals that are spaced p rows and q columns apart. Zero values appear at all other intermediate grid locations. We consider here the construction, for any given p:q, of convolution masks to smoothly and uniformly interpolate values across all of the intermediate grid positions. The conventional pixel-filling approach is to allocate intensities proportional to the fractional area that each grid pixel occupies inside the boundaries formed by the p:q lines. However, these area-based masks have asymmetric boundaries, flat interior values and may be odd or even in size. Where edges, lines or points are in-filled, area-based p:q masks imprint intensity patterns that recall p:q because the shape of those masks is asymmetric and depends on p:q. We aim to remove these “memory” artefacts by building symmetric p:q masks. We show here that smoother, symmetric versions of such convolution masks exist. The coefficients of the masks constructed here have simple integer values whose distribution is derived purely from symmetry considerations. We have application for these symmetric interpolation masks as part of a precise image rotation algorithm which disguises the rotation angle, as well as to smooth back-projected values when performing discrete tomographic image reconstruction.     

The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number

In the framework of parameterized complexity, exploring how one parameter affects the complexity of a different parameterized (or unparameterized problem) is of general interest. A well-developed example is the investigation of how the parameter treewidth influences the complexity of (other) graph problems. The reason why such investigations are of general interest is that real-world input distributions for computational problems often inherit structure from the natural computational processes that produce the problem instances (not necessarily in obvious, or well-understood ways). The max leaf number ml(G) of a connected graph G is the maximum number of leaves in a spanning tree for G. Exploring questions analogous to the well-studied case of treewidth, we can ask: how hard is it to solve 3-Coloring, Hamilton Path, Minimum Dominating Set, Minimum Bandwidth or many other problems, for graphs of bounded max leaf number? What optimization problems are W[1]-hard under this parameterization? We do two things:

1. (1)
   We describe much improved FPT algorithms for a large number of graph problems, for input graphs G for which ml(G)≤k, based on the polynomial-time extremal structure theory canonically associated to this parameter. We consider improved algorithms both from the point of view of kernelization bounds, and in terms of improved fixed-parameter tractable (FPT) runtimes O ^*(f(k)).
    
2. (2)
   The way that we obtain these concrete algorithmic results is general and systematic. We describe the approach, and raise programmatic questions.
    

     

Bionic knowledge and information reuse methodology for uncertainty minimization in product design

Given two spatial point sets R and B in the plane, with cardinalities m and n, respectively, and stored in two separate R-trees, we propose an efficient algorithm to verify whether R and B are linearly separable. The sets R and B are linearly separable if there exists a line that splits the plane into to halfplanes, one containing all R and the other one containing all B. This is the first algorithm that answers the separability question in the context of the spatial data bases. That is, it considers as input big spatial data stored in secondary storage data structures (e.g., the R-tree) which are not allowed to be completely stored in the main memory of the computer to run a classic algorithm. The algorithms designed in this context aim to minimize as much as possible the number of blocks read from the secondary storage data structures to the main memory. Studied problems in this setting are the k-nearest neighbor problem and the spatial range query problem. Our algorithm explicitly exploits the geometric and spatial properties of the R-trees to access only the nodes relevant to decide the linear separability of the given sets. Our experimental results show the efficiency of the algorithm, since it accesses between the 0.34 and 2.79% of the nodes of the R-trees. We also analyze the asymptotic running time of the algorithm, showing that it runs in \(O(m\log m + n\log n)\) time in the worst case.     

Design of optimal and robust control with <Emphasis Type="Italic">H</Emphasis> <Subscript>∞</Subscript>/<Emphasis Type="Italic">γ</Emphasis> <Subscript>0</Subscript> performance criterion

For a double-input single-output system, this paper defines a disturbance attenuation level (called H_∞/γ₀ norm) as the maximum-value L₂ norm of the output under an unknown disturbance with a bounded L₂ norm supplied to the first input and an impulsive disturbance in the form of the product of an unknown vector and the delta function supplied the second input, where the squared L₂ norm of the former disturbance plus the quadratic form of the impulsive disturbance vector does not exceed 1. Weight matrix choice in the H_∞/γ₀ norm yields a trade-off between the attenuation level of the L₂ disturbance and the attenuation level of the impulsive disturbance in corresponding channels. For the uncertain systems with dynamic or parametric uncertainty in the feedback loop, a robust H_∞/γ₀ norm is introduced that includes the robust H_∞ and γ₀ norms as special cases. All these characteristics or their upper bounds in the uncertain system are expressed via solutions of linear matrix inequalities. This gives a uniform approach for designing optimal and robust control laws with the H_∞/γ₀, H_∞ and γ₀ performance criteria.     

Rough approximations via ideal on a complete completely distributive lattice

The rough approximations on a complete completely distributive lattice L based on binary relation were introduced by Zhou and Hu (Inf Sci 269:378–387, 2014), where the binary relation was defined on the set of non-zero join-irreducible elements. This paper extends Zhou and Hu’s rough set model by defining new approximation operators via ideal. When I is the least ideal of L and R is a reflexive binary relation, these two approximations coincide. We present the essential properties of new approximations and also discuss how the new one relates to the old one. Finally, the topological and lattice structures of the approximations are given.     

Cache-Oblivious R-Trees

We develop a cache-oblivious data structure for storing a set S of N axis-aligned rectangles in the plane, such that all rectangles in S intersecting a query rectangle or point can be found efficiently. Our structure is an axis-aligned bounding-box hierarchy and as such it is the first cache-oblivious R-tree with provable performance guarantees. If no point in the plane is contained in more than a constant number of rectangles in S, we can construct, for any constant ε, a structure that answers a rectangle query using \(O(\sqrt{N/B}+T/B)\) memory transfers and a point query using O((N/B) ^ε ) memory transfers, where T is the number of reported rectangles and B is the block size of memory transfers between any two levels of a multilevel memory hierarchy. We also develop a variant of our structure that achieves the same performance on input sets with arbitrary overlap among the rectangles. The rectangle query bound matches the bound of the best known linear-space cache-aware structure.     

Fast Regulation Control of a Class of Input-delayed Linear Systems with Pre-feedback

A control problem of a class of input-delayed linear systems is considered in this paper. Due to the delay τ in the input, any designed feedback controller can only be engaged after t ≥ τ. Then, this can become the cause of slow regulation since any feedback information cannot be available during the delay. So, the initial function defined for -τ ≤ t ≤ 0 is engaged as an ‘initial non-feedback input’ for 0 ≤ t ≤ τ, which governs the system behavior during this initial time period. There have been numerous research results on the control of input-delayed linear systems by far. Yet, there have been no results on the examination and design of this initial function. Utilizing a time optimal control in the existing results, we show that if some pre-feedback as the initial function is engaged, the system response of the input-delayed linear system can be much improved, and a bang-bang input function is a good candidate as a pre-feedback which can provide better starting state values for the state feedback controller in order to perform the fast regulation. Two examples are given for the illustration of our results.     

On <Emphasis Type="Italic">L</Emphasis>-soft merotopies

The goal of this paper is to focus on the notions of merotopy and also merotopology in the soft universe. First of all, we propose L-soft merotopic (nearness) spaces and L-soft guild. Then, we study binary, contigual, regular merotopic spaces and also relations between them. We show that the category of binary L-soft nearness spaces is bireflective in the category of L-soft nearness spaces. Later, we define L-approach soft merotopological (nearness) spaces by giving several examples. Finally, we define a simpler characterization of L-approach soft grill merotopological space called grill-determined L-approach soft merotopological space. We investigate the categorical structures of these notions such as we prove that the category of grill-determined L-approach soft merotopological spaces is a topological category over the category of L-soft topological spaces. At the end, we define a partial order on the family of all L-approach soft grill merotopologies and show that this family is a completely distributive complete lattice with respect to the defined partial order.     

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).     

Efficient hierarchical identity based encryption scheme in the standard model over lattices

Using lattice basis delegation in a fixed dimension, we propose an efficient lattice-based hierarchical identity based encryption (HIBE) scheme in the standard model whose public key size is only (dm² + mn) log q bits and whose message-ciphertext expansion factor is only log q, where d is the maximum hierarchical depth and (n, m, q) are public parameters. In our construction, a novel public key assignment rule is used to averagely assign one random and public matrix to two identity bits, which implies that d random public matrices are enough to build the proposed HIBE scheme in the standard model, compared with the case in which 2d such public matrices are needed in the scheme proposed at Crypto 2010 whose public key size is (2dm² + mn +m) log q. To reduce the message-ciphertext expansion factor of the proposed scheme to log q, the encryption algorithm of this scheme is built based on Gentry’s encryption scheme, by which m² bits of plaintext are encrypted into m² log q bits of ciphertext by a one time encryption operation. Hence, the presented scheme has some advantages with respect to not only the public key size but also the message-ciphertext expansion factor. Based on the hardness of the learning with errors problem, we demonstrate that the scheme is secure under selective identity and chosen plaintext attacks.