OpenRaiser/Intern-Atlas huggingface dataset:
Flowgen: Flowchart-Based Documentation for C++ Codes
Venue: arXiv cs.SE 2014
Year: 2014

We present the Flowgen tool, which generates flowcharts from annotated C++ source code. The tool generates a set of interconnected high-level UML activity diagrams, one for each function or method in the C++ sources. It provides a simple and visual overview of complex implementations of numerical algorithms. Flowgen is complementary to the widely-used Doxygen documentation tool. The ultimate aim is to render complex C++ computer codes accessible, and to enhance collaboration between programmers and algorithm or science specialists. We describe the tool and a proof-of-concept application to the VINCIA plug-in for simulating collisions at CERN's Large Hadron Collider.
Self-dual codes and quadratic residue codes over the ring $\mathbb{Z}_9+u\mathbb{Z}_9$
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we introduce a new definitions of the Gray weight and the Gray map for linear codes over $\mathbb{Z}_9+u\mathbb{Z}_9$ with $u^2=u$. Some results on self-dual codes over this ring are investigated. Further, the structural properties of quadratic residue codes are also considered. Two self-dual codes with parameters $[22,11,5]$ and $[24,12,9]$ over $\mathbb{Z}_9$ are obtained.
A Well-Founded Semantics for FOL-Programs
Venue: arXiv cs.PL 2014
Year: 2014

An FOL-program consists of a background theory in a decidable fragment of first-order logic and a collection of rules possibly containing first-order formulas. The formalism stems from recent approaches to tight integrations of ASP with description logics. In this paper, we define a well-founded semantics for FOL-programs based on a new notion of unfounded sets on consistent as well as inconsistent sets of literals, and study some of its properties. The semantics is defined for all FOL-programs, including those where it is necessary to represent inconsistencies explicitly. The semantics supports a form of combined reasoning by rules under closed world as well as open world assumptions, and it is a generalization of the standard well-founded semantics for normal logic programs. We also show that the well-founded semantics defined here approximates the well-supported answer set semantics for normal DL programs.
Bound Founded Answer Set Programming
Venue: arXiv cs.AI 2014
Year: 2014

Answer Set Programming (ASP) is a powerful modelling formalism that is very efficient in solving combinatorial problems. ASP solvers implement the stable model semantics that eliminates circular derivations between Boolean variables from the solutions of a logic program. Due to this, ASP solvers are better suited than propositional satisfiability (SAT) and Constraint Programming (CP) solvers to solve a certain class of problems whose specification includes inductive definitions such as reachability in a graph. On the other hand, ASP solvers suffer from the grounding bottleneck that occurs due to their inability to model finite domain variables. Furthermore, the existing stable model semantics are not sufficient to disallow circular reasoning on the bounds of numeric variables. An example where this is required is in modelling shortest paths between nodes in a graph. Just as reachability can be encoded as an inductive definition with one or more base cases and recursive rules, shortest paths between nodes can also be modelled with similar base cases and recursive rules for their upper bounds. This deficiency of stable model semantics introduces another type of grounding bottleneck in ASP systems that cannot be removed by naively merging ASP with CP solvers, but requires a theoretical extension of the semantics from Booleans and normal rules to bounds over numeric variables and more general rules. In this work, we propose Bound Founded Answer Set Programming (BFASP) that resolves this issue and consequently, removes all types of grounding bottleneck inherent in ASP systems.
A Scale-Free Topology Construction Model for Wireless Sensor Networks
Venue: arXiv cs.NI 2014
Year: 2014

A local-area and energy-efficient (LAEE) evolution model for wireless sensor networks is proposed. The process of topology evolution is divided into two phases. In the first phase, nodes are distributed randomly in a fixed region. In the second phase, according to the spatial structure of wireless sensor networks, topology evolution starts from the sink, grows with an energy-efficient preferential attachment rule in the new node's local-area, and stops until all nodes are connected into network. Both analysis and simulation results show that the degree distribution of LAEE follows the power law. This topology construction model has better tolerance against energy depletion or random failure than other non-scale-free WSN topologies.
Formulating problems for real algebraic geometry
Venue: arXiv cs.SC 2014
Year: 2014

We discuss issues of problem formulation for algorithms in real algebraic geometry, focussing on quantifier elimination by cylindrical algebraic decomposition. We recall how the variable ordering used can have a profound effect on both performance and output and summarise what may be done to assist with this choice. We then survey other questions of problem formulation and algorithm optimisation that have become pertinent following advances in CAD theory, including both work that is already published and work that is currently underway. With implementations now in reach of real world applications and new theory meaning algorithms are far more sensitive to the input, our thesis is that intelligently formulating problems for algorithms, and indeed choosing the correct algorithm variant for a problem, is key to improving the practical use of both quantifier elimination and symbolic real algebraic geometry in general.
Energy-efficiency in Decentralized Wireless Networks: A Game-theoretic Approach inspired by Evolutionary Biology
Venue: arXiv cs.NI 2014
Year: 2014

Energy efficiency is gaining importance in wireless communication networks which have nodes with limited energy supply and signal processing capabilities. We present a numerical study of cooperative communication scenarios based on simple local rules. This is in contrast to most of the approaches in the literature which enforce cooperation by using complex algorithms and require strategic complexity of the network nodes. The approach is motivated by recent results in evolutionary biology which suggest that, if certain mechanism is at work, cooperation can be favoured by natural selection, i. e. even selfish actions of the individual nodes can lead to emergence of cooperative behaviour in the network. The results of the simulations in the context of wireless communication networks verify these observations and indicate that uncomplicated local rules, followed by simple fitness evaluation, can generate network behaviour which yields global energy efficiency.
Return of the Devil in the Details: Delving Deep into Convolutional Nets
Venue: arXiv cs.CV 2014
Year: 2014

The latest generation of Convolutional Neural Networks (CNN) have achieved impressive results in challenging benchmarks on image recognition and object detection, significantly raising the interest of the community in these methods. Nevertheless, it is still unclear how different CNN methods compare with each other and with previous state-of-the-art shallow representations such as the Bag-of-Visual-Words and the Improved Fisher Vector. This paper conducts a rigorous evaluation of these new techniques, exploring different deep architectures and comparing them on a common ground, identifying and disclosing important implementation details. We identify several useful properties of CNN-based representations, including the fact that the dimensionality of the CNN output layer can be reduced significantly without having an adverse effect on performance. We also identify aspects of deep and shallow methods that can be successfully shared. In particular, we show that the data augmentation techniques commonly applied to CNN-based methods can also be applied to shallow methods, and result in an analogous performance boost. Source code and models to reproduce the experiments in the paper is made publicly available.
Aspects of Statistical Physics in Computational Complexity
Venue: arXiv cs.CC 2014
Year: 2014

The aim of this review paper is to give a panoramic of the impact of spin glass theory and statistical physics in the study of the K-sat problem. The introduction of spin glass theory in the study of the random K-sat problem has indeed left a mark on the field, leading to some groundbreaking descriptions of the geometry of its solution space, and helping to shed light on why it seems to be so hard to solve. Most of the geometrical intuitions have their roots in the Sherrington-Kirkpatrick model of spin glass. We'll start Chapter 2 by introducing the model from a mathematical perspective, presenting a selection of rigorous results and giving a first intuition about the cavity method. We'll then switch to a physical perspective, to explore concepts like pure states, hierarchical clustering and replica symmetry breaking. Chapter 3 will be devoted to the spin glass formulation of K-sat, while the most important phase transitions of K-sat (clustering, condensation, freezing and SAT/UNSAT) will be extensively discussed in Chapter 4, with respect their complexity, free-entropy density and the Parisi 1RSB parameter. The concept of algorithmic barrier will be presented in Chapter 5 and exemplified in detail on the Belief Propagation (BP) algorithm. The BP algorithm will be introduced and motivated, and numerical analysis of a BP-guided decimation algorithm will be used to show the role of the clustering, condensation and freezing phase transitions in creating an algorithmic barrier for BP. Taking from the failure of BP in the clustered and condensed phases, Chapter 6 will finally introduce the Cavity Method to deal with the shattering of the solution space, and present its application to the development of the Survey Propagation algorithm.
Application of lattice reduction block Korkin-Zolotarev method to MIMO-decoding
Venue: arXiv cs.DM 2014
Year: 2014

This article present a application of Block Korkin---Zolotarev lattice reduction method for Lattice Reduction---Aided decoding under MIMO---channel. We give a upper bound estimate on the lattice reduced by block Korkin---Zolotarev method (BKZ) for different value of the block size and detecting by SIC.
Mining State-Based Models from Proof Corpora
Venue: arXiv cs.LO 2014
Year: 2014

Interactive theorem provers have been used extensively to reason about various software/hardware systems and mathematical theorems. The key challenge when using an interactive prover is finding a suitable sequence of proof steps that will lead to a successful proof requires a significant amount of human intervention. This paper presents an automated technique that takes as input examples of successful proofs and infers an Extended Finite State Machine as output. This can in turn be used to generate proofs of new conjectures. Our preliminary experiments show that the inferred models are generally accurate (contain few false-positive sequences) and that representing existing proofs in such a way can be very useful when guiding new ones.
Throughput-Smoothness Trade-offs in Multicasting of an Ordered Packet Stream
Venue: arXiv cs.IT 2014
Year: 2014

An increasing number of streaming applications need packets to be strictly in-order at the receiver. This paper provides a framework for analyzing in-order packet delivery in such applications. We consider the problem of multicasting an ordered stream of packets to two users over independent erasure channels with instantaneous feedback to the source. Depending upon the channel erasures, a packet which is in-order for one user, may be redundant for the other. Thus there is an inter-dependence between throughput and the smoothness of in-order packet delivery to the two users. We use a Markov chain model of packet decoding to analyze these throughput-smoothness trade-offs of the users, and propose coding schemes that can span different points on each trade-off.
Who Will Retweet This? Automatically Identifying and Engaging Strangers on Twitter to Spread Information
Venue: arXiv cs.SI 2014
Year: 2014

There has been much effort on studying how social media sites, such as Twitter, help propagate information in different situations, including spreading alerts and SOS messages in an emergency. However, existing work has not addressed how to actively identify and engage the right strangers at the right time on social media to help effectively propagate intended information within a desired time frame. To address this problem, we have developed two models: (i) a feature-based model that leverages peoples' exhibited social behavior, including the content of their tweets and social interactions, to characterize their willingness and readiness to propagate information on Twitter via the act of retweeting; and (ii) a wait-time model based on a user's previous retweeting wait times to predict her next retweeting time when asked. Based on these two models, we build a recommender system that predicts the likelihood of a stranger to retweet information when asked, within a specific time window, and recommends the top-N qualified strangers to engage with. Our experiments, including live studies in the real world, demonstrate the effectiveness of our work.
An implementation on detection of trusted service provider in mobile ad-hoc networks
Venue: arXiv cs.CR 2014
Year: 2014

The mobile ad-hoc network consists of energy constraint devices called nodes communicating through radio signals forming a temporary network i.e. nodes are continuously switching from one network to another. To minimize the power consumption, we form the clusters with an elected cluster head (Service Provider) based on any cluster head selection strategy.To establish a trusted link amongst newly entered node and CH we have adopted an indirect trust computation technique based on recommendations, which form an important component in trust-based access control models for pervasive environment.In this paper, we shall present some existing indirect trust based techniques and subsequently discuss our proposal along with its merits and future scope.
A Framework for Bottom-Up Simulation of SLD-Resolution
Venue: arXiv cs.LO 2014
Year: 2014

This paper introduces a framework for the bottom-up simulation of SLD-resolution based on partial evaluation. The main idea is to use database facts to represent a set of SLD goals. For deductive databases it is natural to assume that the rules defining derived predicates are known at "compile time", whereas the database predicates are known only later at runtime. The framework is inspired by the author's own SLDMagic method, and a variant of Earley deduction recently introduced by Heike Stephan and the author. However, it opens a much broader perspective. [To appear in Theory and Practice of Logic Programming (TPLP)]
Higher Dimensional Modal Logic
Venue: arXiv cs.LO 2014
Year: 2014

Higher dimensional automata (HDA) are a model of concurrency that can express most of the traditional partial order models like Mazurkiewicz traces, pomsets, event structures, or Petri nets. Modal logics, interpreted over Kripke structures, are the logics for reasoning about sequential behavior and interleaved concurrency. Modal logic is a well behaved subset of first-order logic; many variants of modal logic are decidable. However, there are no modal-like logics for the more expressive HDA models. In this paper we introduce and investigate a modal logic over HDAs which incorporates two modalities for reasoning about "during" and "after". We prove that this general higher dimensional modal logic (HDML) is decidable and we define an axiomatic system for it. We also show how, when the HDA model is restricted to Kripke structures, a syntactic restriction of HDML becomes the standard modal logic. Then we isolate the class of HDAs that encode Mazurkiewicz traces and show how HDML, with natural definitions of corresponding Until operators, can be restricted to LTrL (the linear time temporal logic over Mazurkiewicz traces) or the branching time ISTL. We also study the expressiveness of the basic HDML language wrt. bisimulations and conclude that HDML captures the split-bisimulation.
Multi-power-level Energy Saving Management for Passive Optical Networks
Venue: arXiv cs.NI 2014
Year: 2014

Environmental concerns have motivated network designers to further reduce energy consumption of access networks. This paper focuses on reducing energy consumption of Ethernet passive optical network (EPON) as one of the most efficient transmission technologies for broadband access. In EPON, the downstream traffic is sent from the optical line terminal (OLT) located at the central office to all optical network units (ONUs). Each ONU checks all arrival downstream packets and selects the downstream packets destined to itself. Therefore, receivers at ONUs have to always stay awake, thus consuming a large amount of energy. Contrariwise, an ONU transmitter can be triggered by the arrival of the upstream traffic and so it can go to the low power mode when no traffic is observed. Putting ONUs into the low power mode during light traffic is a known strategy for energy saving. In this article, we address the downstream challenge and also improve the ONU transmitter sleep time by proposing a simple sleep control scheme. We also propose an upstream and a downstream sleep-aware traffic scheduling scheme to avoid missing the packets during the sleep states. The proposed sleep control scheme does not need the handshake process and is based on the mutual inference at OLT and ONU. Simulation results show that the proposed scheme can save energy as much as 60% when the network traffic is light.
Link Prediction in Complex Networks: A Mutual Information Perspective
Venue: arXiv cs.SI 2014
Year: 2014

Topological properties of networks are widely applied to study the link-prediction problem recently. Common Neighbors, for example, is a natural yet efficient framework. Many variants of Common Neighbors have been thus proposed to further boost the discriminative resolution of candidate links. In this paper, we reexamine the role of network topology in predicting missing links from the perspective of information theory, and present a practical approach based on the mutual information of network structures. It not only can improve the prediction accuracy substantially, but also experiences reasonable computing complexity.
Thematically Reinforced Explicit Semantic Analysis
Venue: arXiv cs.CL 2014
Year: 2014

We present an extended, thematically reinforced version of Gabrilovich and Markovitch's Explicit Semantic Analysis (ESA), where we obtain thematic information through the category structure of Wikipedia. For this we first define a notion of categorical tfidf which measures the relevance of terms in categories. Using this measure as a weight we calculate a maximal spanning tree of the Wikipedia corpus considered as a directed graph of pages and categories. This tree provides us with a unique path of "most related categories" between each page and the top of the hierarchy. We reinforce tfidf of words in a page by aggregating it with categorical tfidfs of the nodes of these paths, and define a thematically reinforced ESA semantic relatedness measure which is more robust than standard ESA and less sensitive to noise caused by out-of-context words. We apply our method to the French Wikipedia corpus, evaluate it through a text classification on a 37.5 MB corpus of 20 French newsgroups and obtain a precision increase of 9-10% compared with standard ESA.
Robustness of Time Reversal vs. All-Rake Transceivers in Multiple Access Channels
Venue: arXiv cs.IT 2014
Year: 2014

Time reversal, that is prefiltering of transmitted signals with time reversed channel impulse responses, may be used in single user communications in order to move complexity from the receiver to the transmitter, and in multiuser communications to also modify statistical properties of multiuser interference. Imperfect channel estimation may, however, affect pre- vs. post- filtering schemes in a different way. This issue is the object of this paper; Robustness of time reversal vs. All-Rake (AR) transceivers, in multiple access communications, with respect to channel estimation errors, is investigated. Results of performance analyses in terms of symbol error probability and spectral efficiency when the receiver is structured either by a bank of matched filters or by 1Rake, followed by independent decoders, indicate that AR is slightly more robust than time reversal but requires in practice more complex channel estimation procedures since all channels must be simultaneously inferred in the multiuser communication setting.
Seeking the Principles of Sustainable Software Engineering
Venue: arXiv cs.DC 2014
Year: 2014

Like other engineering disciplines, software engineering should also have principles to guide the construction of sustainable computer applications. Tangible properties include a) unlimited scalability, b) maximal reproducibility, and c) optimizable energy efficiency. In practice, we expect a sustainable scientific application should be written once and execute many times on multiple different processing platforms of different scales with optimized performance and energy efficiency. For more than two decades, explicit parallel programming/processing paradigms only focused on performance. Practices showed that the rigid program-data binding prohibited dynamic runtime resource optimization and fault isolation, making it difficult to reproduce applications in scale. This paper reports our practice and experiences in search of the first principles of sustainable software engineering for compute and data intensive applications. Specifically, we report our practice and experiences using implicit parallel programming/processing paradigms.
A Memetic Algorithm for the Linear Ordering Problem with Cumulative Costs
Venue: arXiv cs.NE 2014
Year: 2014

This paper introduces an effective memetic algorithm for the linear ordering problem with cumulative costs. The proposed algorithm combines an order-based recombination operator with an improved forward-backward local search procedure and employs a solution quality based replacement criterion for pool updating. Extensive experiments on 118 well-known benchmark instances show that the proposed algorithm achieves competitive results by identifying 46 new upper bounds. Furthermore, some critical ingredients of our algorithm are analyzed to understand the source of its performance.
Adaptive Delay-Tolerant Distributed Space-Time Coding Based on Adjustable Code Matrices for Cooperative MIMO Relaying Systems
Venue: arXiv cs.IT 2014
Year: 2014

An adaptive delay-tolerant distributed space-time coding (DSTC) scheme that exploits feedback is proposed for two-hop cooperative MIMO networks. Maximum likelihood (ML) receivers and adjustable code matrices are considered subject to a power constraint with a decode-and-forward (DF) cooperation strategy. In the proposed delay-tolerant DSTC scheme, an adjustable code matrix is employed to transform the space-time coded matrix at the relay nodes. Least-squares (LS) algorithms are developed with reduced computational complexity to adjust the parameters of the codes. Simulation results show that the proposed algorithms obtain significant performance gains and address the delay issue for cooperative MIMO systems as compared to existing delay-tolerant DSTC schemes.
$Υ$-DB: Managing scientific hypotheses as uncertain data
Venue: arXiv cs.DB 2014
Year: 2014

In view of the paradigm shift that makes science ever more data-driven, we consider deterministic scientific hypotheses as uncertain data. This vision comprises a probabilistic database (p-DB) design methodology for the systematic construction and management of U-relational hypothesis DBs, viz., $Υ$-DBs. It introduces hypothesis management as a promising new class of applications for p-DBs. We illustrate the potential of $Υ$-DB as a tool for deep predictive analytics.