OpenRaiser/Intern-Atlas huggingface dataset:
Useful Results for Computing the Nuttall${-}Q$ and Incomplete Toronto Special Functions
Venue: arXiv cs.IT 2015
Year: 2015

This work is devoted to the derivation of novel analytic results for special functions which are particularly useful in wireless communication theory. Capitalizing on recently reported series representations for the Nuttall $Q{-}$function and the incomplete Toronto function, we derive closed-form upper bounds for the corresponding truncation error of these series as well as closed-form upper bounds that under certain cases become accurate approximations. The derived expressions are tight and their algebraic representation is rather convenient to handle analytically and numerically. Given that the Nuttall${-}Q$ and incomplete Toronto functions are not built-in in popular mathematical software packages, the proposed results are particularly useful in computing these functions when employed in applications relating to natural sciences and engineering, such as wireless communication over fading channels.
Exploring Strategy-Proofness, Uniqueness, and Pareto Optimality for the Stable Matching Problem with Couples
Venue: arXiv cs.GT 2015
Year: 2015

The Stable Matching Problem with Couples (SMP-C) is a ubiquitous real-world extension of the stable matching problem (SMP) involving complementarities. Although SMP can be solved in polynomial time, SMP-C is NP-Complete. Hence, it is not clear which, if any, of the theoretical results surrounding the canonical SMP problem apply in this setting. In this paper, we use a recently-developed SAT encoding to solve SMP-C exactly. This allows us to enumerate all stable matchings for any given instance of SMP-C. With this tool, we empirically evaluate some of the properties that have been hypothesized to hold for SMP-C. We take particular interest in investigating if, as the size of the market grows, the percentage of instances with unique stable matchings also grows. While we did not find this trend among the random problem instances we sampled, we did find that the percentage of instances with an resident optimal matching seems to more closely follow the trends predicted by previous conjectures. We also define and investigate resident Pareto optimal stable matchings, finding that, even though this is important desideratum for the deferred acceptance style algorithms previously designed to solve SMP-C, they do not always find one. We also investigate strategy-proofness for SMP-C, showing that even if only one stable matching exists, residents still have incentive to misreport their preferences. However, if a problem has a resident optimal stable matching, we show that residents cannot manipulate via truncation.
State complexity of catenation combined with a boolean operation: a unified approach
Venue: arXiv cs.FL 2015
Year: 2015

In this paper we study the state complexity of catenation combined with symmetric difference. First, an upper bound is computed using some combinatoric tools. Then, this bound is shown to be tight by giving a witness for it. Moreover, we relate this work with the study of state complexity for two other combinations: catenation with union and catenation with intersection. And we extract a unified approach which allows to obtain the state complexity of any combination involving catenation and a binary boolean operation.
Vanishing Point Attracts Eye Movements in Scene Free-viewing
Venue: arXiv cs.CV 2015
Year: 2015

Eye movements are crucial in understanding complex scenes. By predicting where humans look in natural scenes, we can understand how they percieve scenes and priotriaze information for further high-level processing. Here, we study the effect of a particular type of scene structural information known as vanishing point and show that human gaze is attracted to vanishing point regions. We then build a combined model of traditional saliency and vanishing point channel that outperforms state of the art saliency models.
Metric Reasoning about $λ$-Terms: the Affine Case (Long Version)
Venue: arXiv cs.LO 2015
Year: 2015

Terms of Church's $λ$-calculus can be considered equivalent along many different definitions, but context equivalence is certainly the most direct and universally accepted one. If the underlying calculus becomes probabilistic, however, equivalence is too discriminating: terms which have totally unrelated behaviours are treated the same as terms which behave very similarly. We study the problem of evaluating the distance between affine $λ$-terms. The most natural definition for it, namely a natural generalisation of context equivalence, is shown to be characterised by a notion of trace distance, and to be bounded from above by a coinductively defined distance based on the Kantorovich metric on distributions. A different, again fully-abstract, tuple-based notion of trace distance is shown to be able to handle nontrivial examples.
Sensing of Unknown Signals over Weibull Fading Conditions
Venue: arXiv cs.IT 2015
Year: 2015

Energy detection is a widely used method of spectrum sensing in cognitive radio and Radio Detection And Ranging (RADAR) systems. This paper is devoted to the analytical evaluation of the performance of an energy detector over Weibull fading channels. This is a flexible fading model that has been shown capable of providing accurate characterization of multipath fading in, e.g., typical cellular radio frequency range of 800${/}$900 MHz. A novel analytic expression for the corresponding average probability of detection is derived in a simple algebraic representation which renders it convenient to handle both analytically and numerically. As expected, the performance of the detector is highly dependent upon the severity of fading as even small variation of the fading parameters affect significantly the value of the average probability of detection. This appears to be particularly the case in severe fading conditions. The offered results are useful in evaluating the effect of multipath fading in energy detection-based cognitive radio communication systems and therefore they can be used in quantifying the associated trade-offs between sensing performance and energy efficiency in cognitive radio networks.
Isomorphism Testing for Graphs of Bounded Rank Width
Venue: arXiv cs.DM 2015
Year: 2015

We give an algorithm that, for every fixed k, decides isomorphism of graphs of rank width at most k in polynomial time. As the clique width of a graph is bounded in terms of its rank width, we also obtain a polynomial time isomorphism test for graph classes of bounded clique width.
A domain-level DNA strand displacement reaction enumerator allowing arbitrary non-pseudoknotted secondary structures
Venue: arXiv cs.CE 2015
Year: 2015

DNA strand displacement systems have proven themselves to be fertile substrates for the design of programmable molecular machinery and circuitry. Domain-level reaction enumerators provide the foundations for molecular programming languages by formalizing DNA strand displacement mechanisms and modeling interactions at the "domain" level - one level of abstraction above models that explicitly describe DNA strand sequences. Unfortunately, the most-developed models currently only treat pseudo-linear DNA structures, while many systems being experimentally and theoretically pursued exploit a much broader range of secondary structure configurations. Here, we describe a new domain-level reaction enumerator that can handle arbitrary non-pseudoknotted secondary structures and reaction mechanisms including association and dissociation, 3-way and 4-way branch migration, and direct as well as remote toehold activation. To avoid polymerization that is inherent when considering general structures, we employ a time-scale separation technique that holds in the limit of low concentrations. This also allows us to "condense" the detailed reactions by eliminating fast transients, with provable guarantees of correctness for the set of reactions and their kinetics. We hope that the new reaction enumerator will be used in new molecular programming languages, compilers, and tools for analysis and verification that treat a wider variety of mechanisms of interest to experimental and theoretical work. We have implemented this enumerator in Python, and it is included in the DyNAMiC Workbench Integrated Development Environment.
An Approach to Data Prefetching Using 2-Dimensional Selection Criteria
Venue: arXiv cs.AR 2015
Year: 2015

We propose an approach to data memory prefetching which augments the standard prefetch buffer with selection criteria based on performance and usage pattern of a given instruction. This approach is built on top of a pattern matching based prefetcher, specifically one which can choose between a stream, a stride, or a stream followed by a stride. We track the most recently called instructions to make a decision on the quantity of data to prefetch next. The decision is based on the frequency with which these instructions are called and the hit/miss rate of the prefetcher. In our approach, we separate the amount of data to prefetch into three categories: a high degree, a standard degree and a low degree. We ran tests on different values for the high prefetch degree, standard prefetch degree and low prefetch degree to determine that the most optimal combination was 1, 4, 8 lines respectively. The 2 dimensional selection criteria improved the performance of the prefetcher by up to 9.5% over the first data prefetching championship winner. Unfortunately performance also fell by as much as 14%, but remained similar on average across all of the benchmarks we tested.
Block Markov Superposition Transmission of RUN Codes
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we propose a simple procedure to construct (decodable) good codes with any given alphabet (of moderate size) for any given (rational) code rate to achieve any given target error performance (of interest) over additive white Gaussian noise (AWGN) channels. We start with constructing codes over groups for any given code rates. This can be done in an extremely simple way if we ignore the error performance requirement for the time being. Actually, this can be satisfied by repetition (R) codes and uncoded (UN) transmission along with time-sharing technique. The resulting codes are simply referred to as RUN codes for convenience. The encoding/decoding algorithms for RUN codes are almost trivial. In addition, the performance can be easily analyzed. It is not difficult to imagine that a RUN code usually performs far away from the corresponding Shannon limit. Fortunately, the performance can be improved as required by spatially coupling the RUN codes via block Markov superposition transmission (BMST), resulting in the BMST-RUN codes. Simulation results show that the BMST-RUN codes perform well (within one dB away from Shannon limits) for a wide range of code rates and outperform the BMST with bit-interleaved coded modulation (BMST-BICM) scheme.
Linear-Time Superbubble Identification Algorithm for Genome Assembly
Venue: arXiv cs.DS 2015
Year: 2015

DNA sequencing is the process of determining the exact order of the nucleotide bases of an individual's genome in order to catalogue sequence variation and understand its biological implications. Whole-genome sequencing techniques produce masses of data in the form of short sequences known as reads. Assembling these reads into a whole genome constitutes a major algorithmic challenge. Most assembly algorithms utilize de Bruijn graphs constructed from reads for this purpose. A critical step of these algorithms is to detect typical motif structures in the graph caused by sequencing errors and genome repeats, and filter them out; one such complex subgraph class is a so-called superbubble. In this paper, we propose an O(n+m)-time algorithm to detect all superbubbles in a directed acyclic graph with n nodes and m (directed) edges, improving the best-known O(m log m)-time algorithm by Sung et al.
Biometric Matching and Fusion System for Fingerprints from Non-Distal Phalanges
Venue: arXiv cs.CV 2015
Year: 2015

Market research indicates that fingerprints are still the most popular biometric modality for personal authentication. Even with the onset of new modalities (e.g. vein matching), many applications within different domains (e-ID, banking, border control...) and geographies rely on fingerprints obtained from the distal phalanges (a.k.a. sections, digits) of the human hand structure. Motivated by the problem of poor quality distal fingerprint images affecting a non-trivial portion of the population (which decreases associated authentication accuracy), we designed and tested a multifinger, multiphalanx fusion scheme, that combines minutiae matching scores originating from non-distal (ie. middle and proximal) phalanges based on (i) simple sum fusion, (ii) NFIQ image-quality-based fusion, and (iii) phalanx-type-based fusion. Utilizing a medium-size (50 individuals, 400 unique fingers, 1600 distinct images) database collected in our laboratory with a commercial optical fingerprint sensor, and a commercial minutiae extractor & matcher (without any modification), allowed us to simulate a real-world fingerprint authentication setting. Detailed analyses including ROC curves with statistical confidence intervals show that the proposed system can be a viable alternative for cases where (i) distal phalanx images are not usable (e.g. due to missing digits, or low quality finger surface due to manual labor), and (ii) switching to a new biometric modality (e.g. iris) is not possible due to economical or infrastructure limits. Further, we show that when distal phalanx images are in fact usable, combining them with images from other phalanges increases accuracy as well.
Robust Facial Expression Classification Using Shape and Appearance Features
Venue: arXiv cs.CV 2015
Year: 2015

Facial expression recognition has many potential applications which has attracted the attention of researchers in the last decade. Feature extraction is one important step in expression analysis which contributes toward fast and accurate expression recognition. This paper represents an approach of combining the shape and appearance features to form a hybrid feature vector. We have extracted Pyramid of Histogram of Gradients (PHOG) as shape descriptors and Local Binary Patterns (LBP) as appearance features. The proposed framework involves a novel approach of extracting hybrid features from active facial patches. The active facial patches are located on the face regions which undergo a major change during different expressions. After detection of facial landmarks, the active patches are localized and hybrid features are calculated from these patches. The use of small parts of face instead of the whole face for extracting features reduces the computational cost and prevents the over-fitting of the features for classification. By using linear discriminant analysis, the dimensionality of the feature is reduced which is further classified by using the support vector machine (SVM). The experimental results on two publicly available databases show promising accuracy in recognizing all expression classes.
A Prioritised Traffic Embedding Mechanism enabling a Public Safety Virtual Operator
Venue: arXiv cs.NI 2015
Year: 2015

Public Protection and Distaster Relief (PPDR) services can benefit greatly from the availability of mobile broadband communications in disaster and emergency scenarios. While undoubtedly offering full control and reliability, dedicated networks for PPDR have resulted in high operating costs and a lack of innovation in comparison to the commercial domain. Driven by the many benefits of broadband communications, PPDR operators are increasingly interested in adopting mainstream commercial technologies such as Long Term Evolution (LTE) in favour of expensive, dedicated narrow-band networks. In addition, the emergence of virtualization for wireless networks offers a new model for sharing infrastructure between several operators in a flexible and customizable manner. In this context, we propose a virtual Public Safety (PS) operator that relies on shared infrastructure of commercial LTE networks to deliver services to its users. We compare several methods of allocating spectrum resources between virtual operators at peak times and examine how this influences differing traffic services. We show that it is possible to provide services to the PS users reliably during both normal and emergency operation, and examine the impact on the commercial operators.
Reinforcement Learning applied to Single Neuron
Venue: arXiv cs.AI 2015
Year: 2015

This paper extends the reinforcement learning ideas into the multi-agents system, which is far more complicated than the previously studied single-agent system. We studied two different multi-agents systems. One is the fully-connected neural network consists of multiple single neurons. Another one is the simplified mechanical arm system which is controlled by multiple neurons. We suppose that each neuron is like an agent and it can do Gibbs sampling of the posterior probability of stimulus features. The policy is optimized in a way that the cumulative global rewards are maximized. The algorithm for the second system is based on the same idea but we incorporate the physics model into the constraints. The simulation results show that for the first system our algorithm converges well. For the second system it does not converge well in a reasonable simulation time length. In summary, we took the initial endeavor to study the reinforcement learning for multi-agents system. The computational complexity is always an issue and significant amount of works have to be done in order to better understand the problem.
Arabic Inquiry-Answer Dialogue Acts Annotation Schema
Venue: arXiv cs.CL 2015
Year: 2015

We present an annotation schema as part of an effort to create a manually annotated corpus for Arabic dialogue language understanding including spoken dialogue and written "chat" dialogue for inquiry-answer domain. The proposed schema handles mainly the request and response acts that occurs frequently in inquiry-answer debate conversations expressing request services, suggests, and offers. We applied the proposed schema on 83 Arabic inquiry-answer dialogues.
Finite Open-World Query Answering with Number Restrictions (Extended Version)
Venue: arXiv cs.LO 2015
Year: 2015

Open-world query answering is the problem of deciding, given a set of facts, conjunction of constraints, and query, whether the facts and constraints imply the query. This amounts to reasoning over all instances that include the facts and satisfy the constraints. We study finite open-world query answering (FQA), which assumes that the underlying world is finite and thus only considers the finite completions of the instance. The major known decidable cases of FQA derive from the following: the guarded fragment of first-order logic, which can express referential constraints (data in one place points to data in another) but cannot express number restrictions such as functional dependencies; and the guarded fragment with number restrictions but on a signature of arity only two. In this paper, we give the first decidability results for FQA that combine both referential constraints and number restrictions for arbitrary signatures: we show that, for unary inclusion dependencies and functional dependencies, the finiteness assumption of FQA can be lifted up to taking the finite implication closure of the dependencies. Our result relies on new techniques to construct finite universal models of such constraints, for any bound on the maximal query size.
Triangulating planar graphs while keeping the pathwidth small
Venue: arXiv cs.DM 2015
Year: 2015

Any simple planar graph can be triangulated, i.e., we can add edges to it, without adding multi-edges, such that the result is planar and all faces are triangles. In this paper, we study the problem of triangulating a planar graph without increasing the pathwidth by much. We show that if a planar graph has pathwidth $k$, then we can triangulate it so that the resulting graph has pathwidth $O(k)$ (where the factors are 1, 8 and 16 for 3-connected, 2-connected and arbitrary graphs). With similar techniques, we also show that any outer-planar graph of pathwidth $k$ can be turned into a maximal outer-planar graph of pathwidth at most $4k+4$. The previously best known result here was $16k+15$.
How to refute a random CSP
Venue: arXiv cs.CC 2015
Year: 2015

Let $P$ be a $k$-ary predicate over a finite alphabet. Consider a random CSP$(P)$ instance $I$ over $n$ variables with $m$ constraints. When $m \gg n$ the instance $I$ will be unsatisfiable with high probability, and we want to find a refutation - i.e., a certificate of unsatisfiability. When $P$ is the $3$-ary OR predicate, this is the well studied problem of refuting random $3$-SAT formulas, and an efficient algorithm is known only when $m \gg n^{3/2}$. Understanding the density required for refutation of other predicates is important in cryptography, proof complexity, and learning theory. Previously, it was known that for a $k$-ary predicate, having $m \gg n^{\lceil k/2 \rceil}$ constraints suffices for refutation. We give a criterion for predicates that often yields efficient refutation algorithms at much lower densities. Specifically, if $P$ fails to support a $t$-wise uniform distribution, then there is an efficient algorithm that refutes random CSP$(P)$ instances $I$ whp when $m \gg n^{t/2}$. Indeed, our algorithm will "somewhat strongly" refute $I$, certifying $\mathrm{Opt}(I) \leq 1-Ω_k(1)$, if $t = k$ then we get the strongest possible refutation, certifying $\mathrm{Opt}(I) \leq \mathrm{E}[P] + o(1)$. This last result is new even in the context of random $k$-SAT. Regarding the optimality of our $m \gg n^{t/2}$ requirement, prior work on SDP hierarchies has given some evidence that efficient refutation of random CSP$(P)$ may be impossible when $m \ll n^{t/2}$. Thus there is an indication our algorithm's dependence on $m$ is optimal for every $P$, at least in the context of SDP hierarchies. Along these lines, we show that our refutation algorithm can be carried out by the $O(1)$-round SOS SDP hierarchy. Finally, as an application of our result, we falsify assumptions used to show hardness-of-learning results in recent work of Daniely, Linial, and Shalev-Shwartz.
A Time-parallel Approach to Strong-constraint Four-dimensional Variational Data Assimilation
Venue: arXiv cs.NA 2015
Year: 2015

A parallel-in-time algorithm based on an augmented Lagrangian approach is proposed to solve four-dimensional variational (4D-Var) data assimilation problems. The assimilation window is divided into multiple sub-intervals that allows to parallelize cost function and gradient computations. Solution continuity equations across interval boundaries are added as constraints. The augmented Lagrangian approach leads to a different formulation of the variational data assimilation problem than weakly constrained 4D-Var. A combination of serial and parallel 4D-Vars to increase performance is also explored. The methodology is illustrated on data assimilation problems with Lorenz-96 and the shallow water models.
Semantic Service Substitution in Pervasive Environments
Venue: arXiv cs.SE 2015
Year: 2015

A computing infrastructure where everything is a service offers many new system and application possibilities. Among the main challenges, however, is the issue of service substitution for the application execution in such heterogeneous environments. An application would like to continue to execute even when a service disappears, or it would like to benefit from the environment by using better services with better QoS when possible. In this article, we define a generic service model and describe the equivalence relations between services considering the functionalities they propose and their non functional QoS properties. We define semantic equivalence relations between services and equivalence degree between non functional QoS properties. Using these relations we propose semantic substitution mechanisms upon the appearance and disappearance of services that fits the application needs. We developed a prototype as a proof of concept and evaluated its efficiency over a real use case.