OpenRaiser/Intern-Atlas huggingface dataset:
Parallelize Bubble and Merge Sort Algorithms Using Message Passing Interface (MPI)
Venue: arXiv cs.DC 2014
Year: 2014

Sorting has been a profound area for the algorithmic researchers and many resources are invested to suggest more works for sorting algorithms. For this purpose, many existing sorting algorithms were observed in terms of the efficiency of the algorithmic complexity. In this paper we implemented the bubble and merge sort algorithms using Message Passing Interface (MPI) approach. The proposed work tested on two standard datasets (text file) with different size. The main idea of the proposed algorithm is distributing the elements of the input datasets into many additional temporary sub-arrays according to a number of characters in each word. The sizes of each of these sub-arrays are decided depending on a number of elements with the same number of characters in the input array. We implemented MPI using Intel core i7-3610QM ,(8 CPUs),using two approaches (vectors of string and array 3D) . Finally, we get the data structure effects on the performance of the algorithm for that we choice the second approach.
Wi-Fi Gesture Recognition on Existing Devices
Venue: arXiv cs.HC 2014
Year: 2014

This paper introduces the first wireless gesture recognition system that operates using existingWi-Fi signals and devices. To achieve this, we first identify limitations of existing wireless gesture recognition approaches that limit their applicability to Wi-Fi. We then introduce algorithms that can classify gestures using information that is readily available on Wi-Fi devices. We demonstrate the feasibility of our design using a prototype implementation on off-the-shelf Wi-Fi devices. Our results show that we can achieve a classification accuracy of 91% while classifying four gestures across six participants, without the need for per-participant training. Finally, we show the feasibility of gesture recognition in non-line-ofsight situations with the participants interacting with a Wi-Fi device placed in a backpack.
On Compiling Structured CNFs to OBDDs
Venue: arXiv cs.LO 2014
Year: 2014

We present new results on the size of OBDD representations of structurally characterized classes of CNF formulas. First, we identify a natural sufficient condition, which we call the few subterms property, for a class of CNFs to have polynomial OBDD size; we then prove that CNFs whose incidence graphs are variable convex have few subterms (and hence have polynomial OBDD size), and observe that the few subterms property also explains the known fact that classes of CNFs of bounded treewidth have polynomial OBDD size. Second, we prove an exponential lower bound on the OBDD size of a family of CNF classes with incidence graphs of bounded degree, exploiting the combinatorial properties of expander graphs.
Learning a Recurrent Visual Representation for Image Caption Generation
Venue: arXiv cs.CV 2014
Year: 2014

In this paper we explore the bi-directional mapping between images and their sentence-based descriptions. We propose learning this mapping using a recurrent neural network. Unlike previous approaches that map both sentences and images to a common embedding, we enable the generation of novel sentences given an image. Using the same model, we can also reconstruct the visual features associated with an image given its visual description. We use a novel recurrent visual memory that automatically learns to remember long-term visual concepts to aid in both sentence generation and visual feature reconstruction. We evaluate our approach on several tasks. These include sentence generation, sentence retrieval and image retrieval. State-of-the-art results are shown for the task of generating novel image descriptions. When compared to human generated captions, our automatically generated captions are preferred by humans over $19.8\%$ of the time. Results are better than or comparable to state-of-the-art results on the image and sentence retrieval tasks for methods using similar visual features.
Zeno machines and Running Turing machine for infinite time
Venue: arXiv cs.FL 2014
Year: 2014

This paper explores and clarifies several issues surrounding Zeno machines and the issue of running a Turing machine for infinite time. Without a minimum hypothetical bound on physical conditions, any magical machine can be created, and therefore, a thesis on the bound is formulated. This paper then proves that the halting problem algorithm for every Turing-recognizable program and every input cannot be devised whatever method is used to exploit infinite running-time of Turing machine.
New Bounds For Frameproof Codes
Venue: arXiv cs.IT 2014
Year: 2014

Frameproof codes are used to fingerprint digital data. It can prevent copyrighted materials from unauthorized use. In this paper, we study upper and lower bounds for $w$-frameproof codes of length $N$ over an alphabet of size $q$. The upper bound is based on a combinatorial approach and the lower bound is based on a probabilistic construction. Both bounds can improve previous results when $q$ is small compared to $w$, say $cq\leq w$ for some constant $c\leq q$. Furthermore, we pay special attention to binary frameproof codes. We show a binary $w$-frameproof code of length $N$ can not have more than $N$ codewords if $N<\binom{w+1}{2}$.
A Comparison of Skewed and Orthogonal Lattices in Gaussian Wiretap Channels
Venue: arXiv cs.IT 2014
Year: 2014

We consider lattice coset-coded transmissions over a wiretap channel with additive white Gaussian noise (AWGN). Examining a function that can be interpreted as either the legitimate receiver's error probability or the eavesdropper's correct decision probability, we rigorously show that, albeit offering simple bit labeling, orthogonal nested lattices are suboptimal for coset coding in terms of both the legitimate receiver's and the eavesdropper's probabilities.
Efficiently learning Ising models on arbitrary graphs
Venue: arXiv cs.LG 2014
Year: 2014

We consider the problem of reconstructing the graph underlying an Ising model from i.i.d. samples. Over the last fifteen years this problem has been of significant interest in the statistics, machine learning, and statistical physics communities, and much of the effort has been directed towards finding algorithms with low computational cost for various restricted classes of models. Nevertheless, for learning Ising models on general graphs with $p$ nodes of degree at most $d$, it is not known whether or not it is possible to improve upon the $p^{d}$ computation needed to exhaustively search over all possible neighborhoods for each node. In this paper we show that a simple greedy procedure allows to learn the structure of an Ising model on an arbitrary bounded-degree graph in time on the order of $p^2$. We make no assumptions on the parameters except what is necessary for identifiability of the model, and in particular the results hold at low-temperatures as well as for highly non-uniform models. The proof rests on a new structural property of Ising models: we show that for any node there exists at least one neighbor with which it has a high mutual information. This structural property may be of independent interest.
Packet-Level Network Compression: Realization and Scaling of the Network-Wide Benefits
Venue: arXiv cs.NI 2014
Year: 2014

The existence of considerable amount of redundancy in the Internet traffic at the packet level has stimulated the deployment of packet-level redundancy elimination techniques within the network by enabling network nodes to memorize data packets. Redundancy elimination results in traffic reduction which in turn improves the efficiency of network links. In this paper, the concept of network compression is introduced that aspires to exploit the statistical correlation beyond removing large duplicate strings from the flow to better suppress redundancy. In the first part of the paper, we introduce "memory-assisted compression", which utilizes the memorized content within the network to learn the statistics of the information source generating the packets which can then be used toward reducing the length of codewords describing the packets emitted by the source. Using simulations on data gathered from real network traces, we show that memory-assisted compression can result in significant traffic reduction. In the second part of the paper, we study the scaling of the average network-wide benefits of memory-assisted compression. We discuss routing and memory placement problems in network for the reduction of overall traffic. We derive a closed-form expression for the scaling of the gain in Erdos-Renyi random network graphs, where obtain a threshold value for the number of memories deployed in a random graph beyond which network-wide benefits start to shine. Finally, the network-wide benefits are studied on Internet-like scale-free networks. We show that non-vanishing network compression gain is obtained even when only a tiny fraction of the total number of nodes in the network are memory-enabled.
Folding a Paper Strip to Minimize Thickness
Venue: arXiv cs.DS 2014
Year: 2014

In this paper, we study how to fold a specified origami crease pattern in order to minimize the impact of paper thickness. Specifically, origami designs are often expressed by a mountain-valley pattern (plane graph of creases with relative fold orientations), but in general this specification is consistent with exponentially many possible folded states. We analyze the complexity of finding the best consistent folded state according to two metrics: minimizing the total number of layers in the folded state (so that a "flat folding" is indeed close to flat), and minimizing the total amount of paper required to execute the folding (where "thicker" creases consume more paper). We prove both problems strongly NP-complete even for 1D folding. On the other hand, we prove the first problem fixed-parameter tractable in 1D with respect to the number of layers.
Warp2: A Method of Email and Messaging with Encrypted Addressing and Headers
Venue: arXiv cs.CR 2014
Year: 2014

Secure communications are playing increasing roles in society, particularly in finance, journalism, and military projects. Current methods of securing e-mail and similar messaging methods rely on encryption of the message body, but the header with addressing information remains plaintext. This allows third party eavesdroppers to collect and analyse the header metadata and construct a network model of the participants in conversations (who, where, when, subject). In this article, we describe a method of communication where the header is also encrypted, hindering the assembly of the communication network models, which is verified with a working prototype application. This provides a useful tool to journalists and proponents of free speech in oppressed countries, protecting both the messages and their sources.
Understanding Common Perceptions from Online Social Media
Venue: arXiv cs.SI 2014
Year: 2014

Modern society habitually uses online social media services to publicly share observations, thoughts, opinions, and beliefs at any time and from any location. These geotagged social media posts may provide aggregate insights into people's perceptions on a bad range of topics across a given geographical area beyond what is currently possible through services such as Yelp and Foursquare. This paper develops probabilistic language models to investigate whether collective, topic-based perceptions within a geographical area can be extracted from the content of geotagged Twitter posts. The capability of the methodology is illustrated using tweets from three areas of different sizes. An application of the approach to support power grid restoration following a storm is presented.
Quotient of Acceptance Specifications under Reachability Constraints
Venue: arXiv cs.FL 2014
Year: 2014

The quotient operation, which is dual to the composition, is crucial in specification theories as it allows the synthesis of missing specifications and thus enables incremental design. In this paper, we consider a specification theory based on marked acceptance specifications (MAS) which are automata enriched with variability information encoded by acceptance sets and with reachability constraints on states. We define a sound and complete quotient for MAS hence ensuring reachability properties by construction.
Energy-Efficient Strategies for Cooperative Multi-Channel MAC Protocols
Venue: arXiv cs.NI 2014
Year: 2014

Distributed Information SHaring (DISH) is a new cooperative approach to designing multi-channel MAC protocols. It aids nodes in their decision making processes by compensating for their missing information via information sharing through other neighboring nodes. This approach was recently shown to significantly boost the throughput of multi-channel MAC protocols. However, a critical issue for ad hoc communication devices, i.e., energy efficiency, has yet to be addressed. In this paper, we address this issue by developing simple solutions which (1) reduce the energy consumption (2) without compromising the throughput performance, and meanwhile (3) maximize cost efficiency. We propose two energy-efficient strategies: in-situ energy conscious DISH which uses existing nodes only, and altruistic DISH which needs additional nodes called altruists. We compare five protocols with respect to the strategies and identify altruistic DISH to be the right choice in general: it (1) conserves 40-80% of energy, (2) maintains the throughput advantage gained from the DISH approach, and (3) more than doubles the cost efficiency compared to protocols without applying the strategy. On the other hand, our study shows that in-situ energy conscious DISH is suitable only in certain limited scenarios.
One Vector is Not Enough: Entity-Augmented Distributional Semantics for Discourse Relations
Venue: arXiv cs.CL 2014
Year: 2014

Discourse relations bind smaller linguistic units into coherent texts. However, automatically identifying discourse relations is difficult, because it requires understanding the semantics of the linked arguments. A more subtle challenge is that it is not enough to represent the meaning of each argument of a discourse relation, because the relation may depend on links between lower-level components, such as entity mentions. Our solution computes distributional meaning representations by composition up the syntactic parse tree. A key difference from previous work on compositional distributional semantics is that we also compute representations for entity mentions, using a novel downward compositional pass. Discourse relations are predicted from the distributional representations of the arguments, and also of their coreferent entity mentions. The resulting system obtains substantial improvements over the previous state-of-the-art in predicting implicit discourse relations in the Penn Discourse Treebank.
HCRS: A hybrid clothes recommender system based on user ratings and product features
Venue: arXiv cs.AI 2014
Year: 2014

Nowadays, online clothes-selling business has become popular and extremely attractive because of its convenience and cheap-and-fine price. Good examples of these successful Web sites include Yintai.com, Vancl.com and Shop.vipshop.com which provide thousands of clothes for online shoppers. The challenge for online shoppers lies on how to find a good product from lots of options. In this article, we propose a collaborative clothes recommender for easy shopping. One of the unique features of this system is the ability to recommend clothes in terms of both user ratings and clothing attributes. Experiments in our simulation environment show that the proposed recommender can better satisfy the needs of users.
Mobile Agent based Market Basket Analysis on Cloud
Venue: arXiv cs.CY 2014
Year: 2014

This paper describes the design and development of a location-based mobile shopping application for bakery product shops. Whole application is deployed on cloud. The three-tier architecture consists of, front-end, middle-ware and back-end. The front-end level is a location-based mobile shopping application for android mobile devices, for purchasing bakery products of nearby places. Front-end level also displays association among the purchased products. The middle-ware level provides a web service to generate JSON (JavaScript Object Notation) output from the relational database. It exchanges information and data between mobile application and servers in cloud. The back-end level provides the Apache Tomcat Web server and MySQL database. The application also uses the Google Cloud Messaging for generating and sending notification of orders to shopkeeper.
Hypotheses of neural code and the information model of the neuron-detector
Venue: arXiv cs.NE 2014
Year: 2014

This paper deals with the problem of neural code solving. On the basis of the formulated hypotheses the information model of a neuron-detector is suggested, the detector being one of the basic elements of an artificial neural network (ANN). The paper subjects the connectionist paradigm of ANN building to criticism and suggests a new presentation paradigm for ANN building and neuroelements (NE) learning. The adequacy of the suggested model is proved by the fact that is does not contradict the modern propositions of neuropsychology and neurophysiology.
A Tag Identification Approach Based On Fragile Watermark
Venue: arXiv cs.MM 2014
Year: 2014

This paper proposes a tag identify approach based on fragile Watermark that based on Least significant bit of the replacement that we first use a special way to initialize the cover to ensure that we can use random positions to embed the information of tag. Using this way enhance the security of other to get the right information of this tag. Finally as long as the covered information can be decoded, the completeness and accuracy of the tag information can be guaranteed. the result of simulation experiment show that this approach has high sensitivity and security .
Solving the Periodic Timetabling Problem using a Genetic Algorithm
Venue: arXiv cs.AI 2014
Year: 2014

In railway operations, a timetable is established to determine the departure and arrival times for the trains or other rolling stock at the different stations or relevant points inside the rail network or a subset of this network. The elaboration of this timetable is done to respond to the commercial requirements for both passenger and freight traffic, but also it must respect a set of security and capacity constraints associated with the railway network, rolling stock and legislation. Combining these requirements and constraints, as well as the important number of trains and schedules to plan, makes the preparation of a feasible timetable a complex and time-consuming process, that normally takes several months to be completed. This article addresses the problem of generating periodic timetables, which means that the involved trains operate in a recurrent pattern. For instance, the trains belonging to the same train line, depart from some station every 15 minutes or one hour. To tackle the problem, we present a constraint-based model suitable for this kind of problem. Then, we propose a genetic algorithm, allowing a rapid generation of feasible periodic timetables. Finally, two case studies are presented, the first, describing a sub-set of the Netherlands rail network, and the second a large portion of the Nord-pas-de-Calais regional rail network, both of them are then solved using our algorithm and the results are presented and discussed.
Certification of programs with computational effects
Venue: arXiv cs.LO 2014
Year: 2014

In purely functional programming languages imperative features, more generally computational effects are prohibited. However, non-functional lan- guages do involve effects. The theory of decorated logic provides a rigorous for- malism (with a refinement in operation signatures) for proving program properties with respect to computational effects. The aim of this thesis is to first develop Coq libraries and tools for verifying program properties in decorated settings as- sociated with several effects: states, local state, exceptions, non-termination, etc. Then, these tools will be combined to deal with several effects.
Program certification with computational effects
Venue: arXiv cs.LO 2014
Year: 2014

Dynamic evaluation is a paradigm in computer algebra which was introduced for computing with algebraic numbers. In linear algebra, for instance, dynamic evaluation can be used to apply programs which have been written for matrices with coefficients modulo some prime number to matrices with coefficients modulo some composite number. A way to implement dynamic evaluation in modern computing languages is to use the exceptions mechanism provided by the language. In this paper, we pesent a proof system for exceptions which involves both raising and handling, by extending Moggi's approach based on monads. Moreover, the core part of this proof system is dual to a proof system for the state effect in imperative languages, which relies on the categorical notion of comonad. Both proof systems are implemented in the Coq proof assistant, and they are combined in order to deal with both effects at the same time.
On the Impact of Hardware Impairments on Massive MIMO
Venue: arXiv cs.IT 2014
Year: 2014

Massive multi-user (MU) multiple-input multiple-output (MIMO) systems are one possible key technology for next generation wireless communication systems. Claims have been made that massive MU-MIMO will increase both the radiated energy efficiency as well as the sum-rate capacity by orders of magnitude, because of the high transmit directivity. However, due to the very large number of transceivers needed at each base-station (BS), a successful implementation of massive MU-MIMO will be contingent on of the availability of very cheap, compact and power-efficient radio and digital-processing hardware. This may in turn impair the quality of the modulated radio frequency (RF) signal due to an increased amount of power-amplifier distortion, phase-noise, and quantization noise. In this paper, we examine the effects of hardware impairments on a massive MU-MIMO single-cell system by means of theory and simulation. The simulations are performed using simplified, well-established statistical hardware impairment models as well as more sophisticated and realistic models based upon measurements and electromagnetic antenna array simulations.
Efficient analysis of caching strategies under dynamic content popularity
Venue: arXiv cs.PF 2014
Year: 2014

In this paper we develop a novel technique to analyze both isolated and interconnected caches operating under different caching strategies and realistic traffic conditions. The main strength of our approach is the ability to consider dynamic contents which are constantly added into the system catalogue, and whose popularity evolves over time according to desired profiles. We do so while preserving the simplicity and computational efficiency of models developed under stationary popularity conditions, which are needed to analyze several caching strategies. Our main achievement is to show that the impact of content popularity dynamics on cache performance can be effectively captured into an analytical model based on a fixed content catalogue (i.e., a catalogue whose size and objects' popularity do not change over time).
Successive Cancellation List Polar Decoder using Log-likelihood Ratios
Venue: arXiv cs.IT 2014
Year: 2014

Successive cancellation list (SCL) decoding algorithm is a powerful method that can help polar codes achieve excellent error-correcting performance. However, the current SCL algorithm and decoders are based on likelihood or log-likelihood forms, which render high hardware complexity. In this paper, we propose a log-likelihood-ratio (LLR)-based SCL (LLR-SCL) decoding algorithm, which only needs half the computation and storage complexity than the conventional one. Then, based on the proposed algorithm, we develop low-complexity VLSI architectures for LLR-SCL decoders. Analysis results show that the proposed LLR-SCL decoder achieves 50% reduction in hardware and 98% improvement in hardware efficiency.