OpenRaiser/Intern-Atlas huggingface dataset:
What is NP? - Interpretation of a Chinese paradox "white horse is not horse"
Venue: arXiv cs.CC 2015
Year: 2015

The notion of nondeterminism has disappeared from the current definition of NP, which has led to ambiguities in understanding NP, and caused fundamental difficulties in studying the relation P versus NP. In this paper, we question the equivalence of the two definitions of NP, the one defining NP as the class of problems solvable by a nondeterministic Turing machine in polynomial time, and the other defining NP as the class of problems verifiable by a deterministic Turing machine in polynomial time, and reveal cognitive biases in this equivalence. Inspired from a famous Chinese paradox white horse is not horse, we further analyze these cognitive biases. The work shows that these cognitive biases arise from the confusion between different levels of nondeterminism and determinism, due to the lack of understanding about the essence of nondeterminism. Therefore, we argue that fundamental difficulties in understanding P versus NP lie firstly at cognition level, then logic level.
What is Cook's theorem?
Venue: arXiv cs.CC 2015
Year: 2015

In this paper, we make a preliminary interpretation of Cook's theorem presented in [1]. This interpretation reveals cognitive biases in the proof of Cook's theorem that arise from the attempt of constructing a formula in CNF to represent a computation of a nondeterministic Turing machine. Such cognitive biases are due to the lack of understanding about the essence of nondeterminism, and lead to the confusion between different levels of nondeterminism and determinism, thus cause the loss of nondeterminism from the NP-completeness theory. The work shows that Cook's theorem is the origin of the loss of nondeterminism in terms of the equivalence of the two definitions of NP, the one defining NP as the class of problems solvable by a nondeterministic Turing machine in polynomial time, and the other defining NP as the class of problems verifiable by a deterministic Turing machine in polynomial time. Therefore, we argue that fundamental difficulties in understanding P versus NP lie firstly at cognition level, then logic level.
Finite-SNR Bounds on the Sum-Rate Capacity of Rayleigh Block-Fading Multiple-Access Channels with no a Priori CSI
Venue: arXiv cs.IT 2015
Year: 2015

We provide nonasymptotic upper and lower bounds on the sum-rate capacity of Rayleigh block-fading multiple-access channels for the setup where a priori channel state information is not available. The upper bound relies on a dual formula for channel capacity and on the assumption that the users can cooperate perfectly. The lower bound is derived assuming a noncooperative scenario, where each user employs unitary space-time modulation (independently from the other users). Numerical results show that the gap between the upper and the lower bound is small already at moderate SNR values. This suggests that the sum-rate capacity gains obtainable through user cooperation are minimal.
SpecSatisfiabilityTool: A tool for testing the satisfiability of specifications on XML documents
Venue: arXiv cs.LO 2015
Year: 2015

We present a prototype that implements a set of logical rules to prove the satisfiability for a class of specifications on XML documents. Specifications are given by means of constrains built on Boolean XPath patterns. The main goal of this tool is to test whether a given specification is satisfiable or not, and justify the decision showing the execution history. It can also be used to test whether a given document is a model of a given specification and, as a by-product, it permits to look for all the relations (monomorphisms) between two patterns and to combine patterns in different ways. The results of these operations are visually shown and therefore the tool makes these operations more understandable. The implementation of the algorithm has been written in Prolog but the prototype has a Java interface for an easy and friendly use. In this paper we show how to use this interface in order to test all the desired properties.
Interval Selection in the Streaming Model
Venue: arXiv cs.DS 2015
Year: 2015

A set of intervals is independent when the intervals are pairwise disjoint. In the interval selection problem we are given a set $\mathbb{I}$ of intervals and we want to find an independent subset of intervals of largest cardinality. Let $α(\mathbb{I})$ denote the cardinality of an optimal solution. We discuss the estimation of $α(\mathbb{I})$ in the streaming model, where we only have one-time, sequential access to the input intervals, the endpoints of the intervals lie in $\{1,...,n \}$, and the amount of the memory is constrained. For intervals of different sizes, we provide an algorithm in the data stream model that computes an estimate $\hatα$ of $α(\mathbb{I})$ that, with probability at least $2/3$, satisfies $\tfrac 12(1-\varepsilon) α(\mathbb{I}) \le \hatα\le α(\mathbb{I})$. For same-length intervals, we provide another algorithm in the data stream model that computes an estimate $\hatα$ of $α(\mathbb{I})$ that, with probability at least $2/3$, satisfies $\tfrac 23(1-\varepsilon) α(\mathbb{I}) \le \hatα\le α(\mathbb{I})$. The space used by our algorithms is bounded by a polynomial in $\varepsilon^{-1}$ and $\log n$. We also show that no better estimations can be achieved using $o(n)$ bits of storage. We also develop new, approximate solutions to the interval selection problem, where we want to report a feasible solution, that use $O(α(\mathbb{I}))$ space. Our algorithms for the interval selection problem match the optimal results by Emek, Halld{ó}rsson and Ros{é}n [Space-Constrained Interval Selection, ICALP 2012], but are much simpler.
Immersed boundary-finite element model of fluid-structure interaction in the aortic root
Venue: arXiv cs.CE 2015
Year: 2015

It has long been recognized that aortic root elasticity helps to ensure efficient aortic valve closure, but our understanding of the functional importance of the elasticity and geometry of the aortic root continues to evolve as increasingly detailed in vivo imaging data become available. Herein, we describe fluid-structure interaction models of the aortic root, including the aortic valve leaflets, the sinuses of Valsalva, the aortic annulus, and the sinotubular junction, that employ a version of Peskin's immersed boundary (IB) method with a finite element (FE) description of the structural elasticity. We develop both an idealized model of the root with three-fold symmetry of the aortic sinuses and valve leaflets, and a more realistic model that accounts for the differences in the sizes of the left, right, and noncoronary sinuses and corresponding valve cusps. As in earlier work, we use fiber-based models of the valve leaflets, but this study extends earlier IB models of the aortic root by employing incompressible hyperelastic models of the mechanics of the sinuses and ascending aorta using a constitutive law fit to experimental data from human aortic root tissue. In vivo pressure loading is accounted for by a backwards displacement method that determines the unloaded configurations of the root models. Our models yield realistic cardiac output at physiological pressures, with low transvalvular pressure differences during forward flow, minimal regurgitation during valve closure, and realistic pressure loads when the valve is closed during diastole. Further, results from high-resolution computations demonstrate that IB models of the aortic valve are able to produce essentially grid-converged dynamics at practical grid spacings for the high-Reynolds number flows of the aortic root.
Covariance-Based OFDM Spectrum Sensing with Sub-Nyquist Samples
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we propose a feature-based method for spectrum sensing of OFDM signals from sub-Nyquist samples over a single band. We exploit the structure of the covariance matrix of OFDM signals to convert an underdetermined set of covariance-based equations to an overdetermined one. The statistical properties of sample covariance matrix are analyzed and then based on that an approximate Generalized Likelihood Ratio Test (GLRT) for detection of OFDM signals from sub-Nyquist samples is derived. The method is also extended to the frequency-selective channels.
Epidemic Threshold of an SIS Model in Dynamic Switching Networks
Venue: arXiv cs.SI 2015
Year: 2015

In this paper, we analyze dynamic switching networks, wherein the networks switch arbitrarily among a set of topologies. For this class of dynamic networks, we derive an epidemic threshold, considering the SIS epidemic model. First, an epidemic probabilistic model is developed assuming independence between states of nodes. We identify the conditions under which the epidemic dies out by linearizing the underlying dynamical system and analyzing its asymptotic stability around the origin. The concept of joint spectral radius is then used to derive the epidemic threshold, which is later validated using several networks (Watts-Strogatz, Barabasi-Albert, MIT reality mining graphs, Regular, and Gilbert). A simplified version of the epidemic threshold is proposed for undirected networks. Moreover, in the case of static networks, the derived epidemic threshold is shown to match conventional analytical results. Then, analytical results for the epidemic threshold of dynamic networksare proved to be applicable to periodic networks. For dynamic regular networks, we demonstrate that the epidemic threshold is identical to the epidemic threshold for static regular networks. An upper bound for the epidemic spread probability in dynamic Gilbert networks is also derived and verified using simulation.
Teleoperando Robôs Pioneer Utilizando Android
Venue: arXiv cs.RO 2015
Year: 2015

This paper presents an application with ROS, Aria and RosAria to control a ModelSim simulated Pioneer 3-DX robot. The navigation applies a simple autonomous algorithm and a teleoperation control using an Android device sending the gyroscope generated information.
Crafting a Systematic Literature Review on Open-Source Platforms
Venue: arXiv cs.SE 2015
Year: 2015

This working paper unveils the crafting of a systematic literature review on open-source platforms. The high-competitive mobile devices market, where several players such as Apple, Google, Nokia and Microsoft run a platforms- war with constant shifts in their technological strategies, is gaining increasing attention from scholars. It matters, then, to review previous literature on past platforms-wars, such as the ones from the PC and game-console industries, and assess its implications to the current mobile devices platforms-war. The paper starts by justifying the purpose and rationale behind this literature review on open-source platforms. The concepts of open-source software and computer-based platforms were then discussed both individually and in unison, in order to clarify the core-concept of 'open-source platform' that guides this literature review. The detailed design of the employed methodological strategy is then presented as the central part of this paper. The paper concludes with preliminary findings organizing previous literature on open-source platforms for the purpose of guiding future research in this area.
A Unified Analysis Approach for LMS-based Variable Step-Size Algorithms
Venue: arXiv cs.DS 2015
Year: 2015

The least-mean-squares (LMS) algorithm is the most popular algorithm in adaptive filtering. Several variable step-size strategies have been suggested to improve the performance of the LMS algorithm. These strategies enhance the performance of the algorithm but a major drawback is the complexity in the theoretical analysis of the resultant algorithms. Researchers use several assumptions to find closed-form analytical solutions. This work presents a unified approach for the analysis of variable step-size LMS algorithms. The approach is then applied to several variable step-size strategies and theoretical and simulation results are compared.
On the Complexity of Hub Labeling
Venue: arXiv cs.DS 2015
Year: 2015

Hub Labeling (HL) is a data structure for distance oracles. Hierarchical HL (HHL) is a special type of HL, that received a lot of attention from a practical point of view. However, theoretical questions such as NP-hardness and approximation guarantee for HHL algorithms have been left aside. In this paper we study HL and HHL from the complexity theory point of view. We prove that both HL and HHL are NP-hard, and present upper and lower bounds for the approximation ratios of greedy HHL algorithms used in practice. We also introduce a new variant of the greedy HHL algorithm and a proof that it produces small labels for graphs with small highway dimension.
Beam-searching and Transmission Scheduling in Millimeter Wave Communications
Venue: arXiv cs.IT 2015
Year: 2015

Millimeter wave (mmW) wireless networks are capable to support multi-gigabit data rates, by using directional communications with narrow beams. However, existing mmW communications standards are hindered by two problems: deafness and single link scheduling. The deafness problem, that is, a misalignment between transmitter and receiver beams, demands a time consuming beam-searching operation, which leads to an alignment-throughput tradeoff. Moreover, the existing mmW standards schedule a single link in each time slot and hence do not fully exploit the potential of mmW communications, where directional communications allow multiple concurrent transmissions. These two problems are addressed in this paper, where a joint beamwidth selection and power allocation problem is formulated by an optimization problem for short range mmW networks with the objective of maximizing effective network throughput. This optimization problem allows establishing the fundamental alignment-throughput tradeoff, however it is computationally complex and requires exact knowledge of network topology, which may not be available in practice. Therefore, two standard-compliant approximation solution algorithms are developed, which rely on underestimation and overestimation of interference. The first one exploits directionality to maximize the reuse of available spectrum and thereby increases the network throughput, while imposing almost no computational complexity. The second one is a more conservative approach that protects all active links from harmful interference, yet enhances the network throughput by 100% compared to the existing standards. Extensive performance analysis provides useful insights on the directionality level and the number of concurrent transmissions that should be pursued. Interestingly, extremely narrow beams are in general not optimal.
Traffic Convexity Aware Cellular Networks: A Vehicular Heavy User Perspective
Venue: arXiv cs.NI 2015
Year: 2015

Rampant mobile traffic increase in modern cellular networks is mostly caused by large-sized multimedia contents. Recent advancements in smart devices as well as radio access technologies promote the consumption of bulky content, even for people in moving vehicles, referred to as vehicular heavy users. In this article the emergence of vehicular heavy user traffic is observed by field experiments conducted in 2012 and 2015 in Seoul, Korea. The experiments reveal that such traffic is becoming dominant, captured by the 8.62 times increase in vehicular heavy user traffic while the total traffic increased 3.04 times. To resolve this so-called vehicular heavy user problem (VHP), we propose a cell association algorithm that exploits user demand diversity for different velocities. This user traffic pattern is discovered first by our field trials, which is convex-shaped over velocity, i.e. walking user traffic is less than stationary or vehicular user traffic. As the VHP becomes severe, numerical evaluation verifies the proposed user convexity aware association outperforms a well-known load balancing association in practice, cell range expansion (CRE). In addition to the cell association, several complementary techniques are suggested in line with the technical trend toward 5G.
A fast numerical method for max-convolution and the application to efficient max-product inference in Bayesian networks
Venue: arXiv cs.NA 2015
Year: 2015

Observations depending on sums of random variables are common throughout many fields; however, no efficient solution is currently known for performing max-product inference on these sums of general discrete distributions (max-product inference can be used to obtain maximum a posteriori estimates). The limiting step to max-product inference is the max-convolution problem (sometimes presented in log-transformed form and denoted as "infimal convolution", "min-convolution", or "convolution on the tropical semiring"), for which no O(k log(k)) method is currently known. Here I present a O(k log(k)) numerical method for estimating the max-convolution of two nonnegative vectors (e.g., two probability mass functions), where k is the length of the larger vector. This numerical max-convolution method is then demonstrated by performing fast max-product inference on a convolution tree, a data structure for performing fast inference given information on the sum of n discrete random variables in O(n k log(n k) log(n) ) steps (where each random variable has an arbitrary prior distribution on k contiguous possible states). The numerical max-convolution method can be applied to specialized classes of hidden Markov models to reduce the runtime of computing the Viterbi path from n k^2 to n k log(k), and has potential application to the all-pairs shortest paths problem.
Bridge Consensus: Ignoring Initial Inessentials
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, the problem of bridge consensus is presented and solved. Bridge consensus consists of a network of nodes, some of whom are participating and others are non-participating. The objective is for all the agents to reach average consensus of the participating nodes initial values in a distributed and scalable manner. To do this, the nodes must use the network connections of the non-participating nodes, which act as bridges for information and ignore the initial values of the non-participating nodes. The solution to this problem is made by merging the ideas from estimation theory and consensus theory. By considering the participating nodes has having equal information and the non-participating nodes as having no information, the nodes initial values are transformed into information space. Two consensus filters are run in parallel on the information state and information matrix. Conditions ensuring that the product of the inverse information matrix and the information state of each agent reaches average consensus of the participating agents' initial values is given.
Scanning and Parsing Languages with Ambiguities and Constraints: The Lamb and Fence Algorithms
Venue: arXiv cs.FL 2015
Year: 2015

Traditional language processing tools constrain language designers to specific kinds of grammars. In contrast, model-based language processing tools decouple language design from language processing. These tools allow the occurrence of lexical and syntactic ambiguities in language specifications and the declarative specification of constraints for resolving them. As a result, these techniques require scanners and parsers able to parse context-free grammars, handle ambiguities, and enforce constraints for disambiguation. In this paper, we present Lamb and Fence. Lamb is a scanning algorithm that supports ambiguous token definitions and the specification of custom pattern matchers and constraints. Fence is a chart parsing algorithm that supports ambiguous context-free grammars and the definition of constraints on associativity, composition, and precedence, as well as custom constraints. Lamb and Fence, in conjunction, enable the implementation of the ModelCC model-based language processing tool.
A Survey on Recent Advances of Computer Vision Algorithms for Egocentric Video
Venue: arXiv cs.CV 2015
Year: 2015

Recent technological advances have made lightweight, head mounted cameras both practical and affordable and products like Google Glass show first approaches to introduce the idea of egocentric (first-person) video to the mainstream. Interestingly, the computer vision community has only recently started to explore this new domain of egocentric vision, where research can roughly be categorized into three areas: Object recognition, activity detection/recognition, video summarization. In this paper, we try to give a broad overview about the different problems that have been addressed and collect and compare evaluation results. Moreover, along with the emergence of this new domain came the introduction of numerous new and versatile benchmark datasets, which we summarize and compare as well.
Degrees of Freedom of Full-Duplex Multiantenna Cellular Networks
Venue: arXiv cs.IT 2015
Year: 2015

We study the degrees of freedom (DoF) of cellular networks in which a full duplex (FD) base station (BS) equipped with multiple transmit and receive antennas communicates with multiple mobile users. We consider two different scenarios. In the first scenario, we study the case when half duplex (HD) users, partitioned to either the uplink (UL) set or the downlink (DL) set, simultaneously communicate with the FD BS. In the second scenario, we study the case when FD users simultaneously communicate UL and DL data with the FD BS. Unlike conventional HD only systems, inter-user interference (within the cell) may severely limit the DoF, and must be carefully taken into account. With the goal of providing theoretical guidelines for designing such FD systems, we completely characterize the sum DoF of each of the two different FD cellular networks by developing an achievable scheme and obtaining a matching upper bound. The key idea of the proposed scheme is to carefully allocate UL and DL information streams using interference alignment and beamforming techniques. By comparing the DoFs of the considered FD systems with those of the conventional HD systems, we establish the DoF gain by enabling FD operation in various configurations. As a consequence of the result, we show that the DoF can approach the two-fold gain over the HD systems when the number of users becomes large enough as compared to the number of antennas at the BS.
ACO-OFDM-Specified Recoverable Upper Clipping With Efficient Detection for Optical Wireless Communications
Venue: arXiv cs.IT 2015
Year: 2015

The high peak-to-average-power ratio (PAPR) of orthogonal frequency-division multiplexing (OFDM) degrades the performance in optical wireless communication systems. This paper proposes a modified asymmetrically clipped optical OFDM (ACOOFDM) with low PAPR via introducing a recoverable upper-clipping (RoC) procedure. Although some information is clipped by a predetermined peak threshold, the clipped error information is kept and repositioned in our proposed scheme, which is named RoC-ACO-OFDM, instead of simply being dropped in conventional schemes. The proposed method makes full use of the specific structure of ACO-OFDM signals in the time domain, where half of the positions are forced to zeros within an OFDM symbol. The zero-valued positions are utilized to carry the clipped error information. Moreover, we accordingly present an optimal maximum a posteriori (MAP) detection for the RoC-ACO-OFDM system. To facilitate the usage of RoC-ACO-OFDM in practical applications, an efficient detection method is further developed with near-optimal performance. Simulation results show that the proposed RoC-ACO-OFDM achieves a significant PAPR reduction, while maintaining a competitive bit-error rate performance compared with the conventional schemes.