OpenRaiser/Intern-Atlas huggingface dataset:
Achieving Delay Rate-function Optimality in OFDM Downlink with Time-correlated Channels
Venue: arXiv cs.IT 2016
Year: 2016

There have been recent attempts to develop scheduling schemes for downlink transmission in a single cell of a multi-channel (e.g., OFDM-based) cellular network. These works have been quite promising in that they have developed low-complexity index scheduling policies that are delay-optimal (in a large deviation rate-function sense). However, these policies require that the channel is ON or OFF in each time-slot with a fixed probability (i.e., there is no memory in the system), while the reality is that due to channel fading and doppler shift, channels are often time-correlated in these cellular systems. Thus, an important open question is whether one can find simple index scheduling policies that are delay-optimal even when the channels are time-correlated. In this paper, we attempt to answer this question for time-correlated ON/OFF channels. In particular, we show that the class of oldest packets first (OPF) policies that give a higher priority to packets with a large delay is delay rate-function optimal under two conditions: 1) The channel is non-negatively correlated, and 2) The distribution of the OFF period is geometric. We use simulations to further elucidate the theoretical results.
Buffer Occupancy and Delivery Reliability Tradeoffs for Epidemic Routing
Venue: arXiv cs.NI 2016
Year: 2016

To achieve end-to-end delivery in intermittently connected networks, epidemic routing is proposed for data delivery at the price of excessive buffer occupancy due to its store-and-forward nature. The ultimate goal of epidemic routing protocol design is to reduce system resource usage (e.g., buffer occupancy) while simultaneously providing data delivery with statistical guarantee. Therefore the tradeoffs between buffer occupancy and data delivery reliability are of utmost importance. In this paper we investigate the tradeoffs for two representative schemes: the global timeout scheme and the antipacket dissemination scheme that are proposed for lossy and lossless data delivery, respectively. For lossy data delivery, we show that with the suggested global timeout value, the per-node buffer occupancy only depends on the maximum tolerable packet loss rate and pairwise meeting rate. For lossless data delivery, we show that the buffer occupancy can be significantly reduced via fully antipacket dissemination. The developed tools therefore offer new insights for epidemic routing protocol designs and performance evaluations.
Splitting schemes with respect to physical processes for double-porosity poroelasticity problems
Venue: arXiv cs.CE 2016
Year: 2016

We consider unsteady poroelasticity problem in fractured porous medium within the classical Barenblatt double-porosity model. For numerical solution of double-porosity poroelasticity problems we construct splitting schemes with respect to physical processes, where transition to a new time level is associated with solving separate problem for the displacements and fluid pressures in pores and fractures. The stability of schemes is achieved by switching to three-level explicit-implicit difference scheme with some of the terms in the system of equations taken from the lower time level and by choosing a weight parameter used as a regularization parameter. The computational algorithm is based on the finite element approximation in space. The investigation of stability of splitting schemes is based on the general stability (well-posedness) theory of operator-difference schemes. A priori estimates for proposed splitting schemes and the standard two-level scheme are provided. The accuracy and stability of considered schemes are demonstrated by numerical experiments.
Linear code derived from the primage of quadratic function
Venue: arXiv cs.IT 2016
Year: 2016

Linear codes have been an interesting topic in both theory and practice for many years. In this paper, for an odd prime power $q$, we construct some class of linear code over finite field $\mathbb{F}_q$ with defining set be the preimage of general quadratic form function and determine the explicit complete weight enumerators of the linear codes. Our construction cover all the corresponding result with quadratic form function and they may have applications in cryptography and secret sharing schemes.
An overview of low-rank matrix recovery from incomplete observations
Venue: arXiv cs.IT 2016
Year: 2016

Low-rank matrices play a fundamental role in modeling and computational methods for signal processing and machine learning. In many applications where low-rank matrices arise, these matrices cannot be fully sampled or directly observed, and one encounters the problem of recovering the matrix given only incomplete and indirect observations. This paper provides an overview of modern techniques for exploiting low-rank structure to perform matrix recovery in these settings, providing a survey of recent advances in this rapidly-developing field. Specific attention is paid to the algorithms most commonly used in practice, the existing theoretical guarantees for these algorithms, and representative practical applications of these techniques.
Towards a Constant-Gap Sum-Capacity Result for the Gaussian Wiretap Channel with a Helper
Venue: arXiv cs.IT 2016
Year: 2016

Recent investigations have shown that the sum secure degrees of freedom of the Gaussian wiretap channel with a helper is $\tfrac{1}{2}$. The achievable scheme for this result is based on the real interference alignment approach. While providing a good way to show degrees of freedom results, this technique has the disadvantage of relying on the Khintchine-Groshev theorem and is therefore limited to {\it almost all channel gains}. This means that there are infinitely many channel gains, where the scheme fails. Furthermore, the real interference alignment approach cannot be used to yield stronger constant-gap results. We approach this topic from a signal-scale alignment perspective and use the linear deterministic model as a first approximation. Here we can show a constant-gap sum capacity for certain channel gain parameters. We transfer these results to the Gaussian model and discuss the results.
A Theoretical Framework for Understanding Mutation-Based Testing Methods
Venue: arXiv cs.SE 2016
Year: 2016

In the field of mutation analysis, mutation is the systematic generation of mutated programs (i.e., mutants) from an original program. The concept of mutation has been widely applied to various testing problems, including test set selection, fault localization, and program repair. However, surprisingly little focus has been given to the theoretical foundation of mutation-based testing methods, making it difficult to understand, organize, and describe various mutation-based testing methods. This paper aims to consider a theoretical framework for understanding mutation-based testing methods. While there is a solid testing framework for general testing, this is incongruent with mutation-based testing methods, because it focuses on the correctness of a program for a test, while the essence of mutation-based testing concerns the differences between programs (including mutants) for a test. In this paper, we begin the construction of our framework by defining a novel testing factor, called a test differentiator, to transform the paradigm of testing from the notion of correctness to the notion of difference. We formally define behavioral differences of programs for a set of tests as a mathematical vector, called a d-vector. We explore the multi-dimensional space represented by d-vectors, and provide a graphical model for describing the space. Based on our framework and formalization, we interpret existing mutation-based fault localization methods and mutant set minimization as applications, and identify novel implications for future work.
Quantitative Model Checking of Linear-Time Properties Based on Generalized Possibility Measures
Venue: arXiv cs.LO 2016
Year: 2016

Model checking of linear-time properties based on possibility measures was studied in previous work (Y. Li and L. Li, Model checking of linear-time properties based on possibility measure, IEEE Transactions on Fuzzy Systems, 21(5)(2013), 842-854). However, the linear-time properties considered in the previous work was classical and qualitative, possibility information of the systems was not considered at all. We shall study quantitative model checking of fuzzy linear-time properties based on generalized possibility measures in the paper. Both the model of the system, as well as the properties the system needs to adhere to, are described using possibility information to identify the uncertainty in the model/properties. The systems are modeled by {\sl generalized possibilistic Kripke structures} (GPKS, in short), and the properties are described by fuzzy linear-time properties. Concretely, fuzzy linear-time properties about reachability, always reachability, constrain reachability, repeated reachability and persitence in GPKSs are introduced and studied. Fuzzy regular safety properties and fuzzy $ω-$regular properties in GPKSs are introduced, the verification of fuzzy regular safety properties and fuzzy $ω-$regular properties using fuzzy finite automata are thoroughly studied. It has been shown that the verification of fuzzy regular safety properties and fuzzy $ω-$regular properties in a finite GPKS can be transformed into the verification of (always) reachability properties and repeated reachability (persistence) properties in the product GPKS introduced in this paper. Several examples are given to illustrate the methods presented in the paper.
Constructing Sub-exponentially Large Optical Priority Queues with Switches and Fiber Delay Lines
Venue: arXiv cs.IT 2016
Year: 2016

Optical switching has been considered as a natural choice to keep pace with growing fiber link capacity. One key research issue of all-optical switching is the design of optical queues by using optical crossbar switches and fiber delay lines (SDL). In this paper, we focus on the construction of an optical priority queue with a single $(M+2)\times (M+2)$ crossbar switch and $M$ fiber delay lines, and evaluate it in terms of the buffer size of the priority queue. Currently, the best known upper bound of the buffer size is $O(2^M)$, while existing methods can only construct a priority queue with buffer $O(M^3)$. In this paper, we make a great step towards closing the above huge gap. We propose a very efficient construction of priority queues with buffer $2^{Θ(\sqrt{M})}$. We use 4-to-1 multiplexers with different buffer sizes, which can be constructed efficiently with SDL, as intermediate building blocks to simplify the design. The key idea in our construction is to route each packet entering the switch to some group of four 4-to-1 multiplexers according to its current priority, which is shown to be collision-free.
A Kernel Independence Test for Geographical Language Variation
Venue: arXiv cs.CL 2016
Year: 2016

Quantifying the degree of spatial dependence for linguistic variables is a key task for analyzing dialectal variation. However, existing approaches have important drawbacks. First, they are based on parametric models of dependence, which limits their power in cases where the underlying parametric assumptions are violated. Second, they are not applicable to all types of linguistic data: some approaches apply only to frequencies, others to boolean indicators of whether a linguistic variable is present. We present a new method for measuring geographical language variation, which solves both of these problems. Our approach builds on Reproducing Kernel Hilbert space (RKHS) representations for nonparametric statistics, and takes the form of a test statistic that is computed from pairs of individual geotagged observations without aggregation into predefined geographical bins. We compare this test with prior work using synthetic data as well as a diverse set of real datasets: a corpus of Dutch tweets, a Dutch syntactic atlas, and a dataset of letters to the editor in North American newspapers. Our proposed test is shown to support robust inferences across a broad range of scenarios and types of data.
On Multistage Learning a Hidden Hypergraph
Venue: arXiv cs.IT 2016
Year: 2016

Learning a hidden hypergraph is a natural generalization of the classical group testing problem that consists in detecting unknown hypergraph $H_{un}=H(V,E)$ by carrying out edge-detecting tests. In the given paper we focus our attention only on a specific family $F(t,s,\ell)$ of localized hypergraphs for which the total number of vertices $|V| = t$, the number of edges $|E|\le s$, $s\ll t$, and the cardinality of any edge $|e|\le\ell$, $\ell\ll t$. Our goal is to identify all edges of $H_{un}\in F(t,s,\ell)$ by using the minimal number of tests. We develop an adaptive algorithm that matches the information theory bound, i.e., the total number of tests of the algorithm in the worst case is at most $s\ell\log_2 t(1+o(1))$. We also discuss a probabilistic generalization of the problem.
A Label Semantics Approach to Linguistic Hedges
Venue: arXiv cs.AI 2016
Year: 2016

We introduce a model for the linguistic hedges `very' and `quite' within the label semantics framework, and combined with the prototype and conceptual spaces theories of concepts. The proposed model emerges naturally from the representational framework we use and as such, has a clear semantic grounding. We give generalisations of these hedge models and show that they can be composed with themselves and with other functions, going on to examine their behaviour in the limit of composition.
Energy-Aware Optimization and Mechanism Design for Cellular Device-to-Device Local Area Networks
Venue: arXiv cs.IT 2016
Year: 2016

In a device-to-device (D2D) local area network (LAN), mobile users (MUs) must cooperate to download common real-time content from a wireless cellular network. However, sustaining such D2D LANs over cellular networks requires the introduction of mechanisms that will incentivize the MUs to cooperate. In this paper, the problem of energy-aware D2D LAN formation over cellular networks is studied. The problem is formulated using a game-theoretic framework in which each MU seeks to minimize its energy consumption while actively participating in the D2D LAN. To account for the selfish behavior of the MUs, a punishment and incentive protocol is proposed in order to ensure cooperation among MUs. Within this protocol, an estimation algorithm is proposed to simulate the process of D2D LAN formation and, then, adjust the mechanism parameters to maintain cooperation. Simulation results show that the proposed framework can improve energy efficiency up to 36% relative to the traditional multicast scenario.
Emerging Dimension Weights in a Conceptual Spaces Model of Concept Combination
Venue: arXiv cs.AI 2016
Year: 2016

We investigate the generation of new concepts from combinations of properties as an artificial language develops. To do so, we have developed a new framework for conjunctive concept combination. This framework gives a semantic grounding to the weighted sum approach to concept combination seen in the literature. We implement the framework in a multi-agent simulation of language evolution and show that shared combination weights emerge. The expected value and the variance of these weights across agents may be predicted from the distribution of elements in the conceptual space, as determined by the underlying environment, together with the rate at which agents adopt others' concepts. When this rate is smaller, the agents are able to converge to weights with lower variance. However, the time taken to converge to a steady state distribution of weights is longer.
Survey on the attention based RNN model and its applications in computer vision
Venue: arXiv cs.CV 2016
Year: 2016

The recurrent neural networks (RNN) can be used to solve the sequence to sequence problem, where both the input and the output have sequential structures. Usually there are some implicit relations between the structures. However, it is hard for the common RNN model to fully explore the relations between the sequences. In this survey, we introduce some attention based RNN models which can focus on different parts of the input for each output item, in order to explore and take advantage of the implicit relations between the input and the output items. The different attention mechanisms are described in detail. We then introduce some applications in computer vision which apply the attention based RNN models. The superiority of the attention based RNN model is shown by the experimental results. At last some future research directions are given.
Chernoff Information of Bottleneck Gaussian Trees
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, our objective is to find out the determining factors of Chernoff information in distinguishing a set of Gaussian trees. In this set, each tree can be attained via an edge removal and grafting operation from another tree. This is equivalent to asking for the Chernoff information between the most-likely confused, i.e. "bottleneck", Gaussian trees, as shown to be the case in ML estimated Gaussian tree graphs lately. We prove that the Chernoff information between two Gaussian trees related through an edge removal and a grafting operation is the same as that between two three-node Gaussian trees, whose topologies and edge weights are subject to the underlying graph operation. In addition, such Chernoff information is shown to be determined only by the maximum generalized eigenvalue of the two Gaussian covariance matrices. The Chernoff information of scalar Gaussian variables as a result of linear transformation (LT) of the original Gaussian vectors is also uniquely determined by the same maximum generalized eigenvalue. What is even more interesting is that after incorporating the cost of measurements into a normalized Chernoff information, Gaussian variables from LT have larger normalized Chernoff information than the one based on the original Gaussian vectors, as shown in our proved bounds
Tiered-Latency DRAM (TL-DRAM)
Venue: arXiv cs.AR 2016
Year: 2016

This paper summarizes the idea of Tiered-Latency DRAM, which was published in HPCA 2013. The key goal of TL-DRAM is to provide low DRAM latency at low cost, a critical problem in modern memory systems. To this end, TL-DRAM introduces heterogeneity into the design of a DRAM subarray by segmenting the bitlines, thereby creating a low-latency, low-energy, low-capacity portion in the subarray (called the near segment), which is close to the sense amplifiers, and a high-latency, high-energy, high-capacity portion, which is farther away from the sense amplifiers. Thus, DRAM becomes heterogeneous with a small portion having lower latency and a large portion having higher latency. Various techniques can be employed to take advantage of the low-latency near segment and this new heterogeneous DRAM substrate, including hardware-based caching and software based caching and memory allocation of frequently used data in the near segment. Evaluations with simple such techniques show significant performance and energy-efficiency benefits.
Fisher Motion Descriptor for Multiview Gait Recognition
Venue: arXiv cs.CV 2016
Year: 2016

The goal of this paper is to identify individuals by analyzing their gait. Instead of using binary silhouettes as input data (as done in many previous works) we propose and evaluate the use of motion descriptors based on densely sampled short-term trajectories. We take advantage of state-of-the-art people detectors to define custom spatial configurations of the descriptors around the target person, obtaining a rich representation of the gait motion. The local motion features (described by the Divergence-Curl-Shear descriptor) extracted on the different spatial areas of the person are combined into a single high-level gait descriptor by using the Fisher Vector encoding. The proposed approach, coined Pyramidal Fisher Motion, is experimentally validated on `CASIA' dataset (parts B and C), `TUM GAID' dataset, `CMU MoBo' dataset and the recent `AVA Multiview Gait' dataset. The results show that this new approach achieves state-of-the-art results in the problem of gait recognition, allowing to recognize walking people from diverse viewpoints on single and multiple camera setups, wearing different clothes, carrying bags, walking at diverse speeds and not limited to straight walking paths.
Virtual Rephotography: Novel View Prediction Error for 3D Reconstruction
Venue: arXiv cs.CV 2016
Year: 2016

The ultimate goal of many image-based modeling systems is to render photo-realistic novel views of a scene without visible artifacts. Existing evaluation metrics and benchmarks focus mainly on the geometric accuracy of the reconstructed model, which is, however, a poor predictor of visual accuracy. Furthermore, using only geometric accuracy by itself does not allow evaluating systems that either lack a geometric scene representation or utilize coarse proxy geometry. Examples include light field or image-based rendering systems. We propose a unified evaluation approach based on novel view prediction error that is able to analyze the visual quality of any method that can render novel views from input images. One of the key advantages of this approach is that it does not require ground truth geometry. This dramatically simplifies the creation of test datasets and benchmarks. It also allows us to evaluate the quality of an unknown scene during the acquisition and reconstruction process, which is useful for acquisition planning. We evaluate our approach on a range of methods including standard geometry-plus-texture pipelines as well as image-based rendering techniques, compare it to existing geometry-based benchmarks, and demonstrate its utility for a range of use cases.
Forwarding Tables Verification through Representative Header Sets
Venue: arXiv cs.NI 2016
Year: 2016

Forwarding table verification consists in checking the distributed data-structure resulting from the forwarding tables of a network. A classical concern is the detection of loops. We study this problem in the context of software-defined networking (SDN) where forwarding rules can be arbitrary bitmasks (generalizing prefix matching) and where tables are updated by a centralized controller. Basic verification problems such as loop detection are NP-hard and most previous work solves them with heuristics or SAT solvers. We follow a different approach based on computing a representation of the header classes, i.e. the sets of headers that match the same rules. This representation consists in a collection of representative header sets, at least one for each class, and can be computed centrally in time which is polynomial in the number of classes. Classical verification tasks can then be trivially solved by checking each representative header set. In general, the number of header classes can increase exponentially with header length, but it remains polynomial in the number of rules in the practical case where rules are constituted with predefined fields where exact, prefix matching or range matching is applied in each field (e.g., IP/MAC addresses, TCP/UDP ports). We propose general techniques that work in polynomial time as long as the number of classes of headers is polynomial and that do not make specific assumptions about the structure of the sets associated to rules. The efficiency of our method rely on the fact that the data-structure representing rules allows efficient computation of intersection, cardinal and inclusion. Finally, we propose an algorithm to maintain such representation in presence of updates (i.e., rule insert/update/removal). We also provide a local distributed algorithm for checking the absence of black-holes and a proof labeling scheme for locally checking the absence of loops.