OpenRaiser/Intern-Atlas huggingface dataset:
Resolving Entanglements in Topological Interference Management with Alternating Connectivity
Venue: arXiv cs.IT 2014
Year: 2014

The sum-capacity of a three user interference wired network for time-varying channels is considered. Due to the channel variations, it is assumed that the transmitters are only able to track the connectivity between the individual nodes, thus only the (alternating) state of the network is known. By considering a special subset of all possible states, we show that state splitting combined with joint encoding over the alternating states is required to achieve the sum-capacity. Regarding upper bounds, we use a genie aided approach to show the optimality of this scheme. This highlights that more involved transmit strategies are required for characterizing the degrees of freedom even if the transmitters have heavily restricted channel state information.
LTLf and LDLf Monitoring: A Technical Report
Venue: arXiv cs.AI 2014
Year: 2014

Runtime monitoring is one of the central tasks to provide operational decision support to running business processes, and check on-the-fly whether they comply with constraints and rules. We study runtime monitoring of properties expressed in LTL on finite traces (LTLf) and in its extension LDLf. LDLf is a powerful logic that captures all monadic second order logic on finite traces, which is obtained by combining regular expressions and LTLf, adopting the syntax of propositional dynamic logic (PDL). Interestingly, in spite of its greater expressivity, LDLf has exactly the same computational complexity of LTLf. We show that LDLf is able to capture, in the logic itself, not only the constraints to be monitored, but also the de-facto standard RV-LTL monitors. This makes it possible to declaratively capture monitoring metaconstraints, and check them by relying on usual logical services instead of ad-hoc algorithms. This, in turn, enables to flexibly monitor constraints depending on the monitoring state of other constraints, e.g., "compensation" constraints that are only checked when others are detected to be violated. In addition, we devise a direct translation of LDLf formulas into nondeterministic automata, avoiding to detour to Buechi automata or alternating automata, and we use it to implement a monitoring plug-in for the PROM suite.
Performance Modeling of Next-Generation Wireless Networks
Venue: arXiv cs.NI 2014
Year: 2014

The industry is satisfying the increasing demand for wireless bandwidth by densely deploying a large number of access points which are centrally managed, e.g. enterprise WiFi networks deployed in university campuses, companies, airports etc. This small cell architecture is gaining traction in the cellular world as well, as witnessed by the direction in which 4G+ and 5G standardization is moving. Prior academic work in analyzing such large-scale wireless networks either uses oversimplified models for the physical layer, or ignores other important, real-world aspects of the problem, like MAC layer considerations, topology characteristics, and protocol overhead. On the other hand, the industry is using for deployment purposes on-site surveys and simulation tools which do not scale, cannot efficiently optimize the design of such a network, and do not explain why one design choice is better than another. In this paper we introduce a simple yet accurate analytical model which combines the realism and practicality of industrial simulation tools with the ability to scale, analyze the effect of various design parameters, and optimize the performance of real- world deployments. The model takes into account all central system parameters, including channelization, power allocation, user scheduling, load balancing, MAC, advanced PHY techniques (single and multi user MIMO as well as cooperative transmission from multiple access points), topological characteristics and protocol overhead. The accuracy of the model is verified via extensive simulations and the model is used to study a wide range of real world scenarios, providing design guidelines on the effect of various design parameters on performance.
Capacity estimation of two-dimensional channels using Sequential Monte Carlo
Venue: arXiv cs.IT 2014
Year: 2014

We derive a new Sequential-Monte-Carlo-based algorithm to estimate the capacity of two-dimensional channel models. The focus is on computing the noiseless capacity of the 2-D one-infinity run-length limited constrained channel, but the underlying idea is generally applicable. The proposed algorithm is profiled against a state-of-the-art method, yielding more than an order of magnitude improvement in estimation accuracy for a given computation time.
Coding Theoretic Construction of Quantum Ramp Secret Sharing
Venue: arXiv cs.IT 2014
Year: 2014

We show a construction of a quantum ramp secret sharing scheme from a nested pair of linear codes. Necessary and sufficient conditions for qualified sets and forbidden sets are given in terms of combinatorial properties of nested linear codes. An algebraic geometric construction for quantum secret sharing is also given.
Towards a Modular Recommender System for Research Papers written in Albanian
Venue: arXiv cs.IR 2014
Year: 2014

In the recent years there has been an increase in scientific papers publications in Albania and its neighboring countries that have large communities of Albanian speaking researchers. Many of these papers are written in Albanian. It is a very time consuming task to find papers related to the researchers' work, because there is no concrete system that facilitates this process. In this paper we present the design of a modular intelligent search system for articles written in Albanian. The main part of it is the recommender module that facilitates searching by providing relevant articles to the users (in comparison with a given one). We used a cosine similarity based heuristics that differentiates the importance of term frequencies based on their location in the article. We did not notice big differences on the recommendation results when using different combinations of the importance factors of the keywords, title, abstract and body. We got similar results when using only the title and abstract in comparison with the other combinations. Because we got fairly good results in this initial approach, we believe that similar recommender systems for documents written in Albanian can be build also in contexts not related to scientific publishing.
Analysis of Digital Knapsack Based Sealed Bid Auction
Venue: arXiv cs.CR 2014
Year: 2014

The need of totally secure online auction has led to the invention of many auction protocols. But as new attacks are developed, auction protocols also require corresponding strengthening. We analyze the auction protocol based on the well-known mathematical public-key knapsack problem for the design of asymmetric public-key knapsack trapdoor cryptosystem. Even though the knapsack system is not cryptographically secure, it can be used in certain auction situations. We describe the limitations of the protocol like detecting and solving the tie between bidders, malicious behavior of participants and also selection of price set by the seller and offer solutions.
Performance of PZF and MMSE Receivers in Cellular Networks with Multi-User Spatial Multiplexing
Venue: arXiv cs.IT 2014
Year: 2014

This paper characterizes the performance of cellular networks employing multiple antenna open-loop spatial multiplexing techniques. We use a stochastic geometric framework to model distance depended inter cell interference. Using this framework, we analyze the coverage and rate using two linear receivers, namely, partial zero-forcing (PZF) and minimum-mean-square-estimation (MMSE) receivers. Analytical expressions are obtained for coverage and rate distribution that are suitable for fast numerical computation. In the case of the PZF receiver, we show that it is not optimal to utilize all the receive antenna for canceling interference. With $α$ as the path loss exponent, $N_t$ transmit antenna, $N_r$ receive antenna, we show that it is optimal to use $N_t\left\lceil\left(1-\frac{2}α\right) \left( \frac{N_r}{N_t} -\frac{1}{2}\right)\right\rceil$ receive antennas for interference cancellation and the remaining antennas for signal enhancement (array gain). For both PZF and MMSE receivers, we observe that increasing the number of data streams provides an improvement in the mean data rate with diminishing returns. Also transmitting $N_r$ streams is not optimal in terms of the mean sum rate. We observe that increasing the SM rate with a PZF receiver always degrades the cell edge data rate while the performance with MMSE receiver is nearly independent of the SM rate.
An RIP-based approach to $ΣΔ$ quantization for compressed sensing
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we provide a new approach to estimating the error of reconstruction from $ΣΔ$ quantized compressed sensing measurements. Our method is based on the restricted isometry property (RIP) of a certain projection of the measurement matrix. Our result yields simple proofs and a slight generalization of the best-known reconstruction error bounds for Gaussian and subgaussian measurement matrices.
Map-Reduce Parallelization of Motif Discovery
Venue: arXiv cs.DC 2014
Year: 2014

Motif discovery is one of the most challenging problems in bioinformatics today. DNA sequence motifs are becoming increasingly important in analysis of gene regulation. Motifs are short, recurring patterns in DNA that have a biological function. For example, they indicate binding sites for Transcription Factors (TFs) and nucleases. There are a number of Motif Discovery algorithms that run sequentially. The sequential nature stops these algorithms from being parallelized. HOMER is one such Motif discovery tool, that we have decided to use to overcome this limitation. To overcome this limitation, we propose a new methodology for Motif Discovery, using HOMER, that parallelizes the task. Parallelized version can potentially yield better scalability and performance. To achieve this, we have decided to use sub-sampling and the Map Reduce model. At each Map node, a sub-sampled version of the input DNA sequences is used as input to HOMER. Subsampling at each map node is performed with different parameters to ensure that no two HOMER instances receive identical inputs. The output of the map phase and the input of the reduce phase is a list of Motifs discovered using the sub-sampled sequences. The reduce phase calculates the mode, most frequent Motifs, and outputs them as the final discovered Motifs. We found marginal speed gains with this model of execution and substantial amount of quality loss in discovered Motifs.
Solving the undirected feedback vertex set problem by local search
Venue: arXiv cs.AI 2014
Year: 2014

An undirected graph consists of a set of vertices and a set of undirected edges between vertices. Such a graph may contain an abundant number of cycles, then a feedback vertex set (FVS) is a set of vertices intersecting with each of these cycles. Constructing a FVS of cardinality approaching the global minimum value is a optimization problem in the nondeterministic polynomial-complete complexity class, therefore it might be extremely difficult for some large graph instances. In this paper we develop a simulated annealing local search algorithm for the undirected FVS problem. By defining an order for the vertices outside the FVS, we replace the global cycle constraints by a set of local vertex constraints on this order. Under these local constraints the cardinality of the focal FVS is then gradually reduced by the simulated annealing dynamical process. We test this heuristic algorithm on large instances of Erödos-Renyi random graph and regular random graph, and find that this algorithm is comparable in performance to the belief propagation-guided decimation algorithm.
How many times do we need and assumption ?
Venue: arXiv cs.LO 2014
Year: 2014

In this article we present a class of formulas Fn, n in Nat, that need at least 2^n assumptions to be proved in a normal proof in Natural Deduction for purely implicational minimal propositional logic. In purely implicational classical propositional logic, with Peirce's rule, each Fn is proved with only one assumption in Natural Deduction in a normal proof. Hence, the formulas Fn have exponentially sized proofs in cut-free Sequent Calculus and Tableaux. In fact 2^n is the lower-bound for normal proofs in ND, cut-free Sequent proofs and Tableaux. We discuss the consequences of the existence of this class of formulas for designing automatic proof-procedures based on these deductive systems.
Optimal measurement of visual motion across spatial and temporal scales
Venue: arXiv cs.CV 2014
Year: 2014

Sensory systems use limited resources to mediate the perception of a great variety of objects and events. Here a normative framework is presented for exploring how the problem of efficient allocation of resources can be solved in visual perception. Starting with a basic property of every measurement, captured by Gabor's uncertainty relation about the location and frequency content of signals, prescriptions are developed for optimal allocation of sensors for reliable perception of visual motion. This study reveals that a large-scale characteristic of human vision (the spatiotemporal contrast sensitivity function) is similar to the optimal prescription, and it suggests that some previously puzzling phenomena of visual sensitivity, adaptation, and perceptual organization have simple principled explanations.
Spatial Neural Networks and their Functional Samples: Similarities and Differences
Venue: arXiv cs.NE 2014
Year: 2014

Models of neural networks have proven their utility in the development of learning algorithms in computer science and in the theoretical study of brain dynamics in computational neuroscience. We propose in this paper a spatial neural network model to analyze the important class of functional networks, which are commonly employed in computational studies of clinical brain imaging time series. We developed a simulation framework inspired by multichannel brain surface recordings (more specifically, EEG -- electroencephalogram) in order to link the mesoscopic network dynamics (represented by sampled functional networks) and the microscopic network structure (represented by an integrate-and-fire neural network located in a 3D space -- hence the term spatial neural network). Functional networks are obtained by computing pairwise correlations between time-series of mesoscopic electric potential dynamics, which allows the construction of a graph where each node represents one time-series. The spatial neural network model is central in this study in the sense that it allowed us to characterize sampled functional networks in terms of what features they are able to reproduce from the underlying spatial network. Our modeling approach shows that, in specific conditions of sample size and edge density, it is possible to precisely estimate several network measurements of spatial networks by just observing functional samples.
DOA Estimation in Partially Correlated Noise Using Low-Rank/Sparse Matrix Decomposition
Venue: arXiv cs.IT 2014
Year: 2014

We consider the problem of direction-of-arrival (DOA) estimation in unknown partially correlated noise environments where the noise covariance matrix is sparse. A sparse noise covariance matrix is a common model for a sparse array of sensors consisted of several widely separated subarrays. Since interelement spacing among sensors in a subarray is small, the noise in the subarray is in general spatially correlated, while, due to large distances between subarrays, the noise between them is uncorrelated. Consequently, the noise covariance matrix of such an array has a block diagonal structure which is indeed sparse. Moreover, in an ordinary nonsparse array, because of small distance between adjacent sensors, there is noise coupling between neighboring sensors, whereas one can assume that nonadjacent sensors have spatially uncorrelated noise which makes again the array noise covariance matrix sparse. Utilizing some recently available tools in low-rank/sparse matrix decomposition, matrix completion, and sparse representation, we propose a novel method which can resolve possibly correlated or even coherent sources in the aforementioned partly correlated noise. In particular, when the sources are uncorrelated, our approach involves solving a second-order cone programming (SOCP), and if they are correlated or coherent, one needs to solve a computationally harder convex program. We demonstrate the effectiveness of the proposed algorithm by numerical simulations and comparison to the Cramer-Rao bound (CRB).
Probabilistic Inductive Logic Programming Based on Answer Set Programming
Venue: arXiv cs.AI 2014
Year: 2014

We propose a new formal language for the expressive representation of probabilistic knowledge based on Answer Set Programming (ASP). It allows for the annotation of first-order formulas as well as ASP rules and facts with probabilities and for learning of such weights from data (parameter estimation). Weighted formulas are given a semantics in terms of soft and hard constraints which determine a probability distribution over answer sets. In contrast to related approaches, we approach inference by optionally utilizing so-called streamlining XOR constraints, in order to reduce the number of computed answer sets. Our approach is prototypically implemented. Examples illustrate the introduced concepts and point at issues and topics for future research.
Belief revision in the propositional closure of a qualitative algebra (extended version)
Venue: arXiv cs.AI 2014
Year: 2014

Belief revision is an operation that aims at modifying old beliefs so that they become consistent with new ones. The issue of belief revision has been studied in various formalisms, in particular, in qualitative algebras (QAs) in which the result is a disjunction of belief bases that is not necessarily representable in a QA. This motivates the study of belief revision in formalisms extending QAs, namely, their propositional closures: in such a closure, the result of belief revision belongs to the formalism. Moreover, this makes it possible to define a contraction operator thanks to the Harper identity. Belief revision in the propositional closure of QAs is studied, an algorithm for a family of revision operators is designed, and an open-source implementation is made freely available on the web. (This is the extended version of an article originally presented at the 14th International Conference on Principles of Knowledge Representation and Reasoning.)
Design of a capacitor-less low-dropout voltage regulator
Venue: arXiv cs.SY 2014
Year: 2014

A solution to the stability of capacitor-less low-dropout regulators with a 4pF Miller capacitor in Multi-level current amplifier is proposed. With the Miller compensation, a more than 50°phase margin is guaranteed in full load. An extra fast transient circuit is adopted to reduce stable time and peak voltage. When the load changes from light to heavy, the peak voltage is 40mV and chip quiescent current is only 45uA.
Multi-Path Routing and Wavelength Assignment (RWA) Algorithm for WDM Based Optical Networks
Venue: arXiv cs.NI 2014
Year: 2014

In optical WDM networks, transmission of information along optical lines is advantageous since it has high transmission capacity, scalability, feasibility and also high reliability. But large amount of information is being carried; any problem during transmission can lead to severe damage to the data being carried. Hence it is essential to consider the routing as well as the wavelength assignment problems and then develop a combined solution for both the problems. In this paper, we propose to develop a routing and wavelength assignment algorithm for selecting the suitable alternate path for the data packets transmission. Two stages are based on the available bandwidth and the number of wavelength used in the link as construction of alternate paths, route and wavelength selection. In proposed work, Adaptive Routing and First-Fit Wavelength Assignment (AR-FFWA) algorithm to be used. For each pair of source and destination, the path with the minimum granularity values are selected as the primary path for data transmission, allocating the sufficient wavelength and the performances will be evaluated by using ns-2 simulation models. When we compared to existing system the overall blocking probability will be reduced to too low.
Reconfiguration in bounded bandwidth and treedepth
Venue: arXiv cs.CC 2014
Year: 2014

We show that several reconfiguration problems known to be PSPACE-complete remain so even when limited to graphs of bounded bandwidth. The essential step is noticing the similarity to very limited string rewriting systems, whose ability to directly simulate Turing Machines is classically known. This resolves a question posed open in [Bonsma P., 2012]. On the other hand, we show that a large class of reconfiguration problems becomes tractable on graphs of bounded treedepth, and that this result is in some sense tight.
The Multi-engine ASP Solver ME-ASP: Progress Report
Venue: arXiv cs.AI 2014
Year: 2014

MEASP is a multi-engine solver for ground ASP programs. It exploits algorithm selection techniques based on classification to select one among a set of out-of-the-box heterogeneous ASP solvers used as black-box engines. In this paper we report on (i) a new optimized implementation of MEASP; and (ii) an attempt of applying algorithm selection to non-ground programs. An experimental analysis reported in the paper shows that (i) the new implementation of \measp is substantially faster than the previous version; and (ii) the multi-engine recipe can be applied to the evaluation of non-ground programs with some benefits.
Unequal Message Protection: Asymptotic and Non-Asymptotic Tradeoffs
Venue: arXiv cs.IT 2014
Year: 2014

We study a form of unequal error protection that we term "unequal message protection" (UMP). The message set of a UMP code is a union of $m$ disjoint message classes. Each class has its own error protection requirement, with some classes needing better error protection than others. We analyze the tradeoff between rates of message classes and the levels of error protection of these codes. We demonstrate that there is a clear performance loss compared to homogeneous (classical) codes with equivalent parameters. This is in sharp contrast to previous literature that considers UMP codes. To obtain our results we generalize finite block length achievability and converse bounds due to Polyanskiy-Poor-Verdú. We evaluate our bounds for the binary symmetric and binary erasure channels, and analyze the asymptotic characteristic of the bounds in the fixed error and moderate deviations regimes. In addition, we consider two questions related to the practical construction of UMP codes. First, we study a "header" construction that prefixes the message class into a header followed by data protection using a standard homogeneous code. We show that, in general, this construction is not optimal at finite block lengths. We further demonstrate that our main UMP achievability bound can be obtained using coset codes, which suggests a path to implementation of tractable UMP codes.
A Continuous Max-Flow Approach to Multi-Labeling Problems under Arbitrary Region Regularization
Venue: arXiv cs.CV 2014
Year: 2014

The incorporation of region regularization into max-flow segmentation has traditionally focused on ordering and part-whole relationships. A side effect of the development of such models is that it constrained regularization only to those cases, rather than allowing for arbitrary region regularization. Directed Acyclic Graphical Max-Flow (DAGMF) segmentation overcomes these limitations by allowing for the algorithm designer to specify an arbitrary directed acyclic graph to structure a max-flow segmentation. This allows for individual 'parts' to be a member of multiple distinct 'wholes.'