OpenRaiser/Intern-Atlas huggingface dataset:
Symmetric Disjunctive List-Decoding Codes
Venue: arXiv cs.IT 2015
Year: 2015

A binary code is said to be a disjunctive list-decoding $s_L$-code (LD $s_L$-code), $s \ge 2$, $L \ge 1$, if the code is identified by the incidence matrix of a family of finite sets in which the union (or disjunctive sum) of any $s$ sets can cover not more than $L-1$ other sets of the family. In this paper, we consider a similar class of binary codes which are based on a {\em symmetric disjunctive sum} (SDS) of binary symbols. By definition, the symmetric disjunctive sum (SDS) takes values from the ternary alphabet $\{0, 1, *\}$, where the symbol~$*$ denotes "erasure". Namely: SDS is equal to $0$ ($1$) if all its binary symbols are equal to $0$ ($1$), otherwise SDS is equal to~$*$. List decoding codes for symmetric disjunctive sum are said to be {\em symmetric disjunctive list-decoding $s_L$-codes} (SLD $s_L$-codes). In the given paper, we remind some applications of SLD $s_L$-codes which motivate the concept of symmetric disjunctive sum. We refine the known relations between parameters of LD $s_L$-codes and SLD $s_L$-codes. For the ensemble of binary constant-weight codes we develop a random coding method to obtain lower bounds on the rate of these codes. Our lower bounds improve the known random coding bounds obtained up to now using the ensemble with independent symbols of codewords.
Note on paraconsistency and reasoning about fractions
Venue: arXiv cs.LO 2015
Year: 2015

We apply a paraconsistent logic to reason about fractions.
Behavioural equivalences for coalgebras with unobservable moves
Venue: arXiv cs.LO 2015
Year: 2015

We introduce a general categorical framework for the definition of weak behavioural equivalences, building on and extending recent results in the field. This framework is based on parametrized saturation categories, i.e. categories whose hom-sets are endowed with complete orders and a suitable iteration operators; this structure allows us to provide the abstract definitions of various (weak) behavioural equivalence. We show that the Kleisli categories of many common monads are categories of this kind. This allows us to readily instantiate the abstract definitions to a wide range of existing systems (weighted LTS, Segala systems, calculi with names, etc.), recovering the corresponding notions of weak behavioural equivalences. Moreover, we can provide neatly new weak behavioural equivalences for more complex behaviours, like those definable on topological spaces, measurable spaces, etc.
Polynomial mechanics and optimal control
Venue: arXiv cs.SY 2015
Year: 2015

We describe a new algorithm for trajectory optimization of mechanical systems. Our method combines pseudo-spectral methods for function approximation with variational discretization schemes that exactly preserve conserved mechanical quantities such as momentum. We thus obtain a global discretization of the Lagrange-d'Alembert variational principle using pseudo-spectral methods. Our proposed scheme inherits the numerical convergence characteristics of spectral methods, yet preserves momentum-conservation and symplecticity after discretization. We compare this algorithm against two other established methods for two examples of underactuated mechanical systems; minimum-effort swing-up of a two-link and a three-link acrobot.
Four-Dimensional Coded Modulation with Bit-wise Decoders for Future Optical Communications
Venue: arXiv cs.IT 2015
Year: 2015

Coded modulation (CM) is the combination of forward error correction (FEC) and multilevel constellations. Coherent optical communication systems result in a four-dimensional (4D) signal space, which naturally leads to 4D-CM transceivers. A practically attractive design paradigm is to use a bit-wise decoder, where the detection process is (suboptimally) separated into two steps: soft-decision demapping followed by binary decoding. In this paper, bit-wise decoders are studied from an information-theoretic viewpoint. 4D constellations with up to 4096 constellation points are considered. Metrics to predict the post-FEC bit-error rate (BER) of bit-wise decoders are analyzed. The mutual information is shown to fail at predicting the post-FEC BER of bit-wise decoders and the so-called generalized mutual information is shown to be a much more robust metric. For the suboptimal scheme under consideration, it is also shown that constellations that transmit and receive information in each polarization and quadrature independently (e.g., PM-QPSK, PM-16QAM, and PM-64QAM) outperform the best 4D constellations designed for uncoded transmission. Theoretical gains are as high as 4 dB, which are then validated via numerical simulations of low-density parity check codes.
Parametrised bar recursion: A unifying framework for realizability interpretations of classical dependent choice
Venue: arXiv cs.LO 2015
Year: 2015

During the last twenty years or so a wide range of realizability interpretations of classical analysis have been developed. In many cases, these are achieved by extending the base interpreting system of primitive recursive functionals with some form of bar recursion, which realizes the negative translation of either countable or countable dependent choice. In this work we present the many variants of bar recursion used in this context as instantiations of a general, parametrised recursor, and give a uniform proof that under certain conditions this recursor realizes a corresponding family of parametrised dependent choice principles. From this proof, the soundness of most of the existing bar recursive realizability interpretations of choice, including those based on the Berardi-Bezem-Coquand functional, modified realizability and the more recent products of selection functions of Escardó and Oliva, follows as a simple corollary. We achieve not only a uniform framework in which familiar realizability interpretations of choice can be compared, but show that these represent just simple instances of a large family of potential interpretations of dependent choice principles.
Modelling MAC-Layer Communications in Wireless Systems
Venue: arXiv cs.LO 2015
Year: 2015

We present a timed process calculus for modelling wireless networks in which individual stations broadcast and receive messages; moreover the broadcasts are subject to collisions. Based on a reduction semantics for the calculus we define a contextual equivalence to compare the external behaviour of such wireless networks. Further, we construct an extensional LTS (labelled transition system) which models the activities of stations that can be directly observed by the external environment. Standard bisimulations in this LTS provide a sound proof method for proving systems contextually equivalence. We illustrate the usefulness of the proof methodology by a series of examples. Finally we show that this proof method is also complete, for a large class of systems.
Electronic Health Records and Cloud based Generic Medical Equipment Interface
Venue: arXiv cs.CY 2015
Year: 2015

Now-a-days Health Care industry is well equipped with Medical Equipments to provide accurate and timely reports of investigation and examination results. Medical Equipments available in market are made for specific tests suited for a particular laboratory leading to a wide variety of devices. The result viewing experience on console of these devices is not only cumborsome for medical staff but inefficient. Therefore, Medical Equipment Interfaces act as backbone of any Hospital Management Information System assisting in better management and delivery of test results. It also acts as a mode to collect data for further research and analysis. These equipments communicate via a fixed data format but compatibility among these formats is a major issue being faced in modern and legacy medical equipments. In this paper, we present a case study of designing and implementing a cloud based Generic Medical Equipment Interface(GMEI) along with the state of the art in such systems. This solution removes the burden of reentry of patient details into the Electronic Health Record(EHR) and thrives for accelerating EMR initiative in the country
Introduction to the R package TDA
Venue: arXiv cs.MS 2015
Year: 2015

We present a short tutorial and introduction to using the R package TDA, which provides some tools for Topological Data Analysis. In particular, it includes implementations of functions that, given some data, provide topological information about the underlying space, such as the distance function, the distance to a measure, the kNN density estimator, the kernel density estimator, and the kernel distance. The salient topological features of the sublevel sets (or superlevel sets) of these functions can be quantified with persistent homology. We provide an R interface for the efficient algorithms of the C++ libraries GUDHI, Dionysus and PHAT, including a function for the persistent homology of the Rips filtration, and one for the persistent homology of sublevel sets (or superlevel sets) of arbitrary functions evaluated over a grid of points. The significance of the features in the resulting persistence diagrams can be analyzed with functions that implement recently developed statistical methods. The R package TDA also includes the implementation of an algorithm for density clustering, which allows us to identify the spatial organization of the probability mass associated to a density function and visualize it by means of a dendrogram, the cluster tree.
A Strongly Exponential Separation of DNNFs from CNF Formulas
Venue: arXiv cs.CC 2015
Year: 2015

Decomposable Negation Normal Forms (DNNFs) are Boolean circuits in negation normal form where the subcircuits leading into each AND gate are defined on disjoint sets of variables. We prove a strongly exponential lower bound on the size of DNNFs for a class of CNF formulas built from expander graphs. As a corollary, we obtain a strongly exponential separation between DNNFs and CNF formulas in prime implicates form. This settles an open problem in the area of knowledge compilation (Darwiche and Marquis, 2002).
A Primer on IPv4 Scarcity
Venue: arXiv cs.NI 2015
Year: 2015

With the ongoing exhaustion of free address pools at the registries serving the global demand for IPv4 address space, scarcity has become reality. Networks in need of address space can no longer get more address allocations from their respective registries. In this work we frame the fundamentals of the IPv4 address exhaustion phenomena and connected issues. We elaborate on how the current ecosystem of IPv4 address space has evolved since the standardization of IPv4, leading to the rather complex and opaque scenario we face today. We outline the evolution in address space management as well as address space use patterns, identifying key factors of the scarcity issues. We characterize the possible solution space to overcome these issues and open the perspective of address blocks as virtual resources, which involves issues such as differentiation between address blocks, the need for resource certification, and issues arising when transferring address space between networks.
Avoiding the Global Sort: A Faster Contour Tree Algorithm
Venue: arXiv cs.CG 2015
Year: 2015

We revisit the classical problem of computing the \emph{contour tree} of a scalar field $f:\mathbb{M} \to \mathbb{R}$, where $\mathbb{M}$ is a triangulated simplicial mesh in $\mathbb{R}^d$. The contour tree is a fundamental topological structure that tracks the evolution of level sets of $f$ and has numerous applications in data analysis and visualization. All existing algorithms begin with a global sort of at least all critical values of $f$, which can require (roughly) $Ω(n\log n)$ time. Existing lower bounds show that there are pathological instances where this sort is required. We present the first algorithm whose time complexity depends on the contour tree structure, and avoids the global sort for non-pathological inputs. If $C$ denotes the set of critical points in $\mathbb{M}$, the running time is roughly $O(\sum_{v \in C} \log \ell_v)$, where $\ell_v$ is the depth of $v$ in the contour tree. This matches all existing upper bounds, but is a significant improvement when the contour tree is short and fat. Specifically, our approach ensures that any comparison made is between nodes in the same descending path in the contour tree, allowing us to argue strong optimality properties of our algorithm. Our algorithm requires several novel ideas: partitioning $\mathbb{M}$ in well-behaved portions, a local growing procedure to iteratively build contour trees, and the use of heavy path decompositions for the time complexity analysis.
Publishing without Publishers: a Decentralized Approach to Dissemination, Retrieval, and Archiving of Data
Venue: arXiv cs.DL 2015
Year: 2015

Making available and archiving scientific results is for the most part still considered the task of classical publishing companies, despite the fact that classical forms of publishing centered around printed narrative articles no longer seem well-suited in the digital age. In particular, there exist currently no efficient, reliable, and agreed-upon methods for publishing scientific datasets, which have become increasingly important for science. Here we propose to design scientific data publishing as a Web-based bottom-up process, without top-down control of central authorities such as publishing companies. Based on a novel combination of existing concepts and technologies, we present a server network to decentrally store and archive data in the form of nanopublications, an RDF-based format to represent scientific data. We show how this approach allows researchers to publish, retrieve, verify, and recombine datasets of nanopublications in a reliable and trustworthy manner, and we argue that this architecture could be used for the Semantic Web in general. Evaluation of the current small network shows that this system is efficient and reliable.
Computational Baby Learning
Venue: arXiv cs.CV 2015
Year: 2015

Intuitive observations show that a baby may inherently possess the capability of recognizing a new visual concept (e.g., chair, dog) by learning from only very few positive instances taught by parent(s) or others, and this recognition capability can be gradually further improved by exploring and/or interacting with the real instances in the physical world. Inspired by these observations, we propose a computational model for slightly-supervised object detection, based on prior knowledge modelling, exemplar learning and learning with video contexts. The prior knowledge is modeled with a pre-trained Convolutional Neural Network (CNN). When very few instances of a new concept are given, an initial concept detector is built by exemplar learning over the deep features from the pre-trained CNN. Simulating the baby's interaction with physical world, the well-designed tracking solution is then used to discover more diverse instances from the massive online unlabeled videos. Once a positive instance is detected/identified with high score in each video, more variable instances possibly from different view-angles and/or different distances are tracked and accumulated. Then the concept detector can be fine-tuned based on these new instances. This process can be repeated again and again till we obtain a very mature concept detector. Extensive experiments on Pascal VOC-07/10/12 object detection datasets well demonstrate the effectiveness of our framework. It can beat the state-of-the-art full-training based performances by learning from very few samples for each object category, along with about 20,000 unlabeled videos.
The Cyclic-Routing UAV Problem is PSPACE-Complete
Venue: arXiv cs.LO 2015
Year: 2015

Consider a finite set of targets, with each target assigned a relative deadline, and each pair of targets assigned a fixed transit flight time. Given a flock of identical UAVs, can one ensure that every target is repeatedly visited by some UAV at intervals of duration at most the target's relative deadline? The Cyclic-Routing UAV Problem (CR-UAV) is the question of whether this task has a solution. This problem can straightforwardly be solved in PSPACE by modelling it as a network of timed automata. The special case of there being a single UAV is claimed to be NP-complete in the literature. In this paper, we show that the CR-UAV Problem is in fact PSPACE-complete even in the single-UAV case.
Enhancing Satellite System Throughput Using Adaptive HARQ for Delay Tolerant Services in Mobile Communications
Venue: arXiv cs.NI 2015
Year: 2015

In this paper we propose the introduction of adaptive hybrid automatic repeat request (HARQ) in the context of mobile satellite communications. HARQ schemes which are commonly used in terrestrial links, can be adapted to improve the throughput for delay tolerant services. The proposed method uses the estimation of the mutual information between the received and the sent symbols, in order to estimate the number of bits necessary to decode the message at next transmission. We evaluate the performance of our method by simulating a land mobile satellite (LMS) channel. We compare our results with the static HARQ scheme, showing that our adaptive retransmission technique has better efficiency while keeping an acceptable delay for services.
Simultaneous Velocity and Position Estimation via Distance-only Measurements with Application to Multi-Agent System Control
Venue: arXiv cs.SY 2015
Year: 2015

This paper proposes a strategy to estimate the velocity and position of neighbor agents using distance measurements only. Since with agents executing arbitrary motions, instantaneous distance-only measurements cannot provide enough information for our objectives, we postulate that agents engage in a combination of circular motion and linear motion. The proposed estimator can be used to develop control algorithms where only distance measurements are available to each agent. As an example, we show how this estimation method can be used to control the formation shape and velocity of the agents in a multi agent system. Simulation results are provided to illustrate the performance of the proposed algorithm.
Routing Diverse Crowds in Emergency with Dynamic Grouping
Venue: arXiv cs.OH 2015
Year: 2015

Evacuee routing algorithms in emergency typically adopt one single criterion to compute desired paths and ignore the specific requirements of users caused by different physical strength, mobility and level of resistance to hazard. In this paper, we present a quality of service (QoS) driven multi-path routing algorithm to provide diverse paths for different categories of evacuees. This algorithm borrows the concept of Cognitive Packet Network (CPN), which is a flexible protocol that can rapidly solve optimal solution for any user-defined goal function. Spatial information regarding the location and spread of hazards is taken into consideration to avoid that evacuees be directed towards hazardous zones. Furthermore, since previous emergency navigation algorithms are normally insensitive to sudden changes in the hazard environment such as abrupt congestion or injury of civilians, evacuees are dynamically assigned to several groups to adapt their course of action with regard to their on-going physical condition and environments. Simulation results indicate that the proposed algorithm which is sensitive to the needs of evacuees produces better results than the use of a single metric. Simulations also show that the use of dynamic grouping to adjust the evacuees' category and routing algorithms with regard for their on-going health conditions and mobility, can achieve higher survival rates.
Relatively Complete Counterexamples for Higher-Order Programs
Venue: arXiv cs.PL 2015
Year: 2015

In this paper, we study the problem of generating inputs to a higher-order program causing it to error. We first study the problem in the setting of PCF, a typed, core functional language and contribute the first relatively complete method for constructing counterexamples for PCF programs. The method is relatively complete in the sense of Hoare logic; completeness is reduced to the completeness of a first-order solver over the base types of PCF. In practice, this means an SMT solver can be used for the effective, automated generation of higher-order counterexamples for a large class of programs. We achieve this result by employing a novel form of symbolic execution for higher-order programs. The remarkable aspect of this symbolic execution is that even though symbolic higher-order inputs and values are considered, the path condition remains a first-order formula. Our handling of symbolic function application enables the reconstruction of higher-order counterexamples from this first-order formula. After establishing our main theoretical results, we sketch how to apply the approach to untyped, higher-order, stateful languages with first-class contracts and show how counterexample generation can be used to detect contract violations in this setting. To validate our approach, we implement a tool generating counterexamples for erroneous modules written in Racket.
An Improved Hazard Rate Twisting Approach for the Statistic of the Sum of Subexponential Variates (Extended Version)
Venue: arXiv cs.IT 2015
Year: 2015

In this letter, we present an improved hazard rate twisting technique for the estimation of the probability that a sum of independent but not necessarily identically distributed subexponential Random Variables (RVs) exceeds a given threshold. Instead of twisting all the components in the summation, we propose to twist only the RVs which have the biggest impact on the right-tail of the sum distribution and keep the other RVs unchanged. A minmax approach is performed to determine the optimal twisting parameter which leads to an asymptotic optimality criterion. Moreover, we show through some selected simulation results that our proposed approach results in a variance reduction compared to the technique where all the components are twisted.
"You're Mr. Lebowski, I'm the Dude": Inducing Address Term Formality in Signed Social Networks
Venue: arXiv cs.SI 2015
Year: 2015

We present an unsupervised model for inducing signed social networks from the content exchanged across network edges. Inference in this model solves three problems simultaneously: (1) identifying the sign of each edge; (2) characterizing the distribution over content for each edge type; (3) estimating weights for triadic features that map to theoretical models such as structural balance. We apply this model to the problem of inducing the social function of address terms, such as 'Madame', 'comrade', and 'dude'. On a dataset of movie scripts, our system obtains a coherent clustering of address terms, while at the same time making intuitively plausible judgments of the formality of social relations in each film. As an additional contribution, we provide a bootstrapping technique for identifying and tagging address terms in dialogue.
Mining cross-cultural relations from Wikipedia - A study of 31 European food cultures
Venue: arXiv cs.SI 2015
Year: 2015

For many people, Wikipedia represents one of the primary sources of knowledge about foreign cultures. Yet, different Wikipedia language editions offer different descriptions of cultural practices. Unveiling diverging representations of cultures provides an important insight, since they may foster the formation of cross-cultural stereotypes, misunderstandings and potentially even conflict. In this work, we explore to what extent the descriptions of cultural practices in various European language editions of Wikipedia differ on the example of culinary practices and propose an approach to mine cultural relations between different language communities trough their description of and interest in their own and other communities' food culture. We assess the validity of the extracted relations using 1) various external reference data sources (i.e., the European Social Survey, migration statistics), 2) crowdsourcing methods and 3) simulations.