OpenRaiser/Intern-Atlas huggingface dataset:
Fountain Codes under Maximum Likelihood Decoding
Venue: arXiv cs.IT 2017
Year: 2017

This dissertation focuses on fountain codes under maximum likelihood (ML) decoding. First LT codes are considered under a practical and widely used ML decoding algorithm known as inactivation decoding. Different analysis techniques are presented to characterize the decoding complexity. Next an upper bound to the probability of decoding failure of Raptor codes under ML decoding is provided. Then, the distance properties of an ensemble of fixed-rate Raptor codes with linear random outer codes are analyzed. Finally, a novel class of fountain codes is presented, which consists of a parallel concatenation of a block code with a linear random fountain code.
Beamforming and Scheduling for mmWave Downlink Sparse Virtual Channels With Non-Orthogonal and Orthogonal Multiple Access
Venue: arXiv cs.IT 2017
Year: 2017

We consider the problem of scheduling and power allocation for the downlink of a 5G cellular system operating in the millimeter wave (mmWave) band and serving two sets of users: fix-rate (FR) users typically seen in device-to-device (D2D) communications, and variable-rate (VR) users, or high data rate services. The scheduling objective is the weighted sum-rate of both FR and VR users, and the constraints ensure that active FR users get the required rate. The weights of the objective function provide a trade-off between the number of served FR users and the resources allocated to VR users. For mmWave channels the virtual channel matrix obtained by applying fixed discrete-Fourier transform (DFT) beamformers at both the transmitter and the receiver is sparse. This results into a sparsity of the resulting multiple access channel, which is exploited to simplify scheduling, first establishing an interference graph among users and then grouping users according to their orthogonality. The original scheduling problem is solved using a graph-coloring algorithm on the interference graph in order to select sub-sets of orthogonal VR users. Two options are considered for FR users: either they are chosen orthogonal to VR users or non-orthogonal. A waterfilling algorithm is then used to allocate power to the FR users.
Impulsive Sound Detection by a Novel Energy Formula and its Usage for Gunshot Recognition
Venue: arXiv cs.SD 2017
Year: 2017

There are many methods proposed for the detection of impulsive sounds in literature. Most of them are complex and require adaptation to ambient noise. In this paper we propose a very simple and efficient method to detect impulsive sounds. Although we use energy like most of the others to determine impulsive sounds, the way we calculate the energy is quite different. Also our calculation is immune to ambient noise and does not require any limit or adaptation. We could detect impulsive sounds embedded in various kinds of noises by using this formula. As our ultimate aim is to detect gunshots, next phase of impulsive sound detection is gunshot recognition phase. Detected impulsive sounds are fed into recognition phase in which we can decide on gunshots with high success rate.
Centralized and Distributed Sparsification for Low-Complexity Message Passing Algorithm in C-RAN Architectures
Venue: arXiv cs.IT 2017
Year: 2017

Cloud radio access network (C-RAN) is a promising technology for fifth-generation (5G) cellular systems. However the burden imposed by the huge amount of data to be collected (in the uplink) from the radio remote heads (RRHs) and processed at the base band unit (BBU) poses serious challenges. In order to reduce the computation effort of minimum mean square error (MMSE) receiver at the BBU the Gaussian message passing (MP) together with a suitable sparsification of the channel matrix can be used. In this paper we propose two sets of solutions, either centralized or distributed ones. In the centralized solutions, we propose different approaches to sparsify the channel matrix, in order to reduce the complexity of MP. However these approaches still require that all signals reaching the RRH are conveyed to the BBU, therefore the communication requirements among the backbone network devices are unaltered. In the decentralized solutions instead we aim at reducing both the complexity of MP at the BBU and the requirements on the RRHs-BBU communication links by pre-processing the signals at the RRH and convey a reduced set of signals to the BBU.
A Robust Data Hiding Process Contributing to the Development of a Semantic Web
Venue: arXiv cs.MM 2017
Year: 2017

In this paper, a novel steganographic scheme based on chaotic iterations is proposed. This research work takes place into the information hiding framework, and focus more specifically on robust steganography. Steganographic algorithms can participate in the development of a semantic web: medias being on the Internet can be enriched by information related to their contents, authors, etc., leading to better results for the search engines that can deal with such tags. As media can be modified by users for various reasons, it is preferable that these embedding tags can resist to changes resulting from some classical transformations as for example cropping, rotation, image conversion, and so on. This is why a new robust watermarking scheme for semantic search engines is proposed in this document. For the sake of completeness, the robustness of this scheme is finally compared to existing established algorithms.
Symbolic Versus Numerical Computation and Visualization of Parameter Regions for Multistationarity of Biological Networks
Venue: arXiv cs.SC 2017
Year: 2017

We investigate models of the mitogenactivated protein kinases (MAPK) network, with the aim of determining where in parameter space there exist multiple positive steady states. We build on recent progress which combines various symbolic computation methods for mixed systems of equalities and inequalities. We demonstrate that those techniques benefit tremendously from a newly implemented graph theoretical symbolic preprocessing method. We compare computation times and quality of results of numerical continuation methods with our symbolic approach before and after the application of our preprocessing.
NOMA: Principles and Recent Results
Venue: arXiv cs.IT 2017
Year: 2017

Although non-orthogonal multiple access (NOMA) is recently considered for cellular systems, its key ideas such as successive interference cancellation (SIC) and superposition coding have been well studied in information theory. In this paper, we overview principles of NOMA based on information theory and present some recent results. Under a single-cell environment, we mainly focus on fundamental issues, e.g., power allocation and beamforming for downlink NOMA and coordinated and uncoordinated transmissions for uplink NOMA.
The IoT energy challenge: A software perspective
Venue: arXiv cs.SE 2017
Year: 2017

The Internet of Things (IoT) sparks a whole new world of embedded applications. Most of these applications are based on deeply embedded systems that have to operate on limited or unreliable sources of energy, such as batteries or energy harvesters. Meeting the energy requirements for such applications is a hard challenge, which threatens the future growth of the IoT. Software has the ultimate control over hardware. Therefore, its role is significant in optimizing the energy consumption of a system. Currently, programmers have no feedback on how their software affects the energy consumption of a system. Such feedback can be enabled by energy transparency, a concept that makes a program's energy consumption visible, from hardware to software. This paper discusses the need for energy transparency in software development and emphasizes on how such transparency can be realized to help tackling the IoT energy challenge.
Rate-Distortion Classification for Self-Tuning IoT Networks
Venue: arXiv cs.NI 2017
Year: 2017

Many future wireless sensor networks and the Internet of Things are expected to follow a software defined paradigm, where protocol parameters and behaviors will be dynamically tuned as a function of the signal statistics. New protocols will be then injected as a software as certain events occur. For instance, new data compressors could be (re)programmed on-the-fly as the monitored signal type or its statistical properties change. We consider a lossy compression scenario, where the application tolerates some distortion of the gathered signal in return for improved energy efficiency. To reap the full benefits of this paradigm, we discuss an automatic sensor profiling approach where the signal class, and in particular the corresponding rate-distortion curve, is automatically assessed using machine learning tools (namely, support vector machines and neural networks). We show that this curve can be reliably estimated on-the-fly through the computation of a small number (from ten to twenty) of statistical features on time windows of a few hundreds samples.
Way to Go! Automatic Optimization of Wayfinding Design
Venue: arXiv cs.GR 2017
Year: 2017

Wayfinding signs play an important role in guiding users to navigate in a virtual environment and in helping pedestrians to find their ways in a real-world architectural site. Conventionally, the wayfinding design of a virtual environment is created manually, so as the wayfinding design of a real-world architectural site. The many possible navigation scenarios, as well as the interplay between signs and human navigation, can make the manual design process overwhelming and non-trivial. As a result, creating a wayfinding design for a typical layout can take months to several years. In this paper, we introduce the Way to Go! approach for automatically generating a wayfinding design for a given layout. The designer simply has to specify some navigation scenarios; our approach will automatically generate an optimized wayfinding design with signs properly placed considering human agents' visibility and possibility of making mistakes during a navigation. We demonstrate the effectiveness of our approach in generating wayfinding designs for different layouts such as a train station, a downtown and a canyon. We evaluate our results by comparing different wayfinding designs and show that our optimized wayfinding design can guide pedestrians to their destinations effectively and efficiently. Our approach can also help the designer visualize the accessibility of a destination from different locations, and correct any "blind zone" with additional signs.
Classical Music Clustering Based on Acoustic Features
Venue: arXiv cs.IR 2017
Year: 2017

In this paper we cluster 330 classical music pieces collected from MusicNet database based on their musical note sequence. We use shingling and chord trajectory matrices to create signature for each music piece and performed spectral clustering to find the clusters. Based on different resolution, the output clusters distinctively indicate composition from different classical music era and different composing style of the musicians.
Managing a Fleet of Autonomous Mobile Robots (AMR) using Cloud Robotics Platform
Venue: arXiv cs.RO 2017
Year: 2017

In this paper, we provide details of implementing a system for managing a fleet of autonomous mobile robots (AMR) operating in a factory or a warehouse premise. While the robots are themselves autonomous in its motion and obstacle avoidance capability, the target destination for each robot is provided by a global planner. The global planner and the ground vehicles (robots) constitute a multi agent system (MAS) which communicate with each other over a wireless network. Three different approaches are explored for implementation. The first two approaches make use of the distributed computing based Networked Robotics architecture and communication framework of Robot Operating System (ROS) itself while the third approach uses Rapyuta Cloud Robotics framework for this implementation. The comparative performance of these approaches are analyzed through simulation as well as real world experiment with actual robots. These analyses provide an in-depth understanding of the inner working of the Cloud Robotics Platform in contrast to the usual ROS framework. The insight gained through this exercise will be valuable for students as well as practicing engineers interested in implementing similar systems else where. In the process, we also identify few critical limitations of the current Rapyuta platform and provide suggestions to overcome them.
CoNLL-SIGMORPHON 2017 Shared Task: Universal Morphological Reinflection in 52 Languages
Venue: arXiv cs.CL 2017
Year: 2017

The CoNLL-SIGMORPHON 2017 shared task on supervised morphological generation required systems to be trained and tested in each of 52 typologically diverse languages. In sub-task 1, submitted systems were asked to predict a specific inflected form of a given lemma. In sub-task 2, systems were given a lemma and some of its specific inflected forms, and asked to complete the inflectional paradigm by predicting all of the remaining inflected forms. Both sub-tasks included high, medium, and low-resource conditions. Sub-task 1 received 24 system submissions, while sub-task 2 received 3 system submissions. Following the success of neural sequence-to-sequence models in the SIGMORPHON 2016 shared task, all but one of the submissions included a neural component. The results show that high performance can be achieved with small training datasets, so long as models have appropriate inductive bias or make use of additional unlabeled data or synthetic data. However, different biasing and data augmentation resulted in disjoint sets of inflected forms being predicted correctly, suggesting that there is room for future improvement.
Critical Vertices and Edges in $H$-free Graphs
Venue: arXiv cs.CC 2017
Year: 2017

A vertex or edge in a graph is critical if its deletion reduces the chromatic number of the graph by 1. We consider the problems of deciding whether a graph has a critical vertex or edge, respectively. We give a complexity dichotomy for both problems restricted to $H$-free graphs, that is, graphs with no induced subgraph isomorphic to $H$. Moreover, we show that an edge is critical if and only if its contraction reduces the chromatic number by 1. Hence, we also obtain a complexity dichotomy for the problem of deciding if a graph has an edge whose contraction reduces the chromatic number by 1.
Machine-to-Machine (M2M) Communications in Virtualized Cellular Networks with MEC
Venue: arXiv cs.NI 2017
Year: 2017

As an important part of the Internet-of-Things (IoT), machine-to-machine (M2M) communications have attracted great attention. In this paper, we introduce mobile edge computing (MEC) into virtualized cellular networks with M2M communications, to decrease the energy consumption and optimize the computing resource allocation as well as improve computing capability. Moreover, based on different functions and quality of service (QoS) requirements, the physical network can be virtualized into several virtual networks, and then each MTCD selects the corresponding virtual network to access. Meanwhile, the random access process of MTCDs is formulated as a partially observable Markov decision process (POMDP) to minimize the system cost, which consists of both the energy consumption and execution time of computing tasks. Furthermore, to facilitate the network architecture integration, software-defined networking (SDN) is introduced to deal with the diverse protocols and standards in the networks. Extensive simulation results with different system parameters reveal that the proposed scheme could significantly improve the system performance compared to the existing schemes.
Bivariate Extensions of Abramov's Algorithm for Rational Summation
Venue: arXiv cs.SC 2017
Year: 2017

Abramov's algorithm enables us to decide whether a univariate rational function can be written as a difference of another rational function, which has been a fundamental algorithm for rational summation. In 2014, Chen and Singer generalized Abramov's algorithm to the case of rational functions in two ($q$-)discrete variables. In this paper we solve the remaining three mixed cases, which completes our recent project on bivariate extensions of Abramov's algorithm for rational summation.
LDPC Codes over the q-ary Multi-Bit Channel
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we introduce a new channel model we term the q-ary multi-bit channel (QMBC). This channel models a memory device, where q-ary symbols (q=2^s) are stored in the form of current/voltage levels. The symbols are read in a measurement process, which provides a symbol bit in each measurement step, starting from the most significant bit. An error event occurs when not all the symbol bits are known. To deal with such error events, we use GF(q) low-density parity-check (LDPC) codes and analyze their decoding performance. We start with iterative-decoding threshold analysis, and derive optimal edge-label distributions for maximizing the decoding threshold. We later move to finite-length iterative-decoding analysis and propose an edge-labeling algorithm for improved decoding performance. We then provide finite-length maximum-likelihood decoding analysis for both the standard non-binary random ensemble and LDPC ensembles. Finally, we demonstrate by simulations that the proposed edge-labeling algorithm improves finite-length decoding performance by orders of magnitude.
Named Entity Disambiguation for Noisy Text
Venue: arXiv cs.CL 2017
Year: 2017

We address the task of Named Entity Disambiguation (NED) for noisy text. We present WikilinksNED, a large-scale NED dataset of text fragments from the web, which is significantly noisier and more challenging than existing news-based datasets. To capture the limited and noisy local context surrounding each mention, we design a neural model and train it with a novel method for sampling informative negative examples. We also describe a new way of initializing word and entity embeddings that significantly improves performance. Our model significantly outperforms existing state-of-the-art methods on WikilinksNED while achieving comparable performance on a smaller newswire dataset.
Automating Sized Type Inference for Complexity Analysis (Technical Report)
Venue: arXiv cs.LO 2017
Year: 2017

This paper introduces a new methodology for the complexity analysis of higher-order functional programs, which is based on three ingredients: a powerful type system for size analysis and a sound type inference procedure for it, a ticking monadic transformation, and constraint solving. Noticeably, the presented methodology can be fully automated, and is able to analyse a series of examples which cannot be handled by most competitor methodologies. This is possible due to the choice of adopting an abstract index language and index polymorphism at higher ranks. A prototype implementation is available.
Dispersion on Trees
Venue: arXiv cs.DS 2017
Year: 2017

In the $k$-dispersion problem, we need to select $k$ nodes of a given graph so as to maximize the minimum distance between any two chosen nodes. This can be seen as a generalization of the independent set problem, where the goal is to select nodes so that the minimum distance is larger than 1. We design an optimal $O(n)$ time algorithm for the dispersion problem on trees consisting of $n$ nodes, thus improving the previous $O(n\log n)$ time solution from 1997. We also consider the weighted case, where the goal is to choose a set of nodes of total weight at least $W$. We present an $O(n\log^2n)$ algorithm improving the previous $O(n\log^4 n)$ solution. Our solution builds on the search version (where we know the minimum distance $λ$ between the chosen nodes) for which we present tight $Θ(n\log n)$ upper and lower bounds.
A Parameterized Approach to Personalized Variable Length Summarization of Soccer Matches
Venue: arXiv cs.CV 2017
Year: 2017

We present a parameterized approach to produce personalized variable length summaries of soccer matches. Our approach is based on temporally segmenting the soccer video into 'plays', associating a user-specifiable 'utility' for each type of play and using 'bin-packing' to select a subset of the plays that add up to the desired length while maximizing the overall utility (volume in bin-packing terms). Our approach systematically allows a user to override the default weights assigned to each type of play with individual preferences and thus see a highly personalized variable length summarization of soccer matches. We demonstrate our approach based on the output of an end-to-end pipeline that we are building to produce such summaries. Though aspects of the overall end-to-end pipeline are human assisted at present, the results clearly show that the proposed approach is capable of producing semantically meaningful and compelling summaries. Besides the obvious use of producing summaries of superior league matches for news broadcasts, we anticipate our work to promote greater awareness of the local matches and junior leagues by producing consumable summaries of them.
New Models and Methods for Formation and Analysis of Social Networks
Venue: arXiv cs.SI 2017
Year: 2017

This doctoral work focuses on three main problems related to social networks: (1) Orchestrating Network Formation: We consider the problem of orchestrating formation of a social network having a certain given topology that may be desirable for the intended usecases. Assuming the social network nodes to be strategic in forming relationships, we derive conditions under which a given topology can be uniquely obtained. We also study the efficiency and robustness of the derived conditions. (2) Multi-phase Influence Maximization: We propose that information diffusion be carried out in multiple phases rather than in a single instalment. With the objective of achieving better diffusion, we discover optimal ways of splitting the available budget among the phases, determining the time delay between consecutive phases, and also finding the individuals to be targeted for initiating the diffusion process. (3) Scalable Preference Aggregation: It is extremely useful to determine a small number of representatives of a social network such that the individual preferences of these nodes, when aggregated, reflect the aggregate preference of the entire network. Using real-world data collected from Facebook with human subjects, we discover a model that faithfully captures the spread of preferences in a social network. We hence propose fast and reliable ways of computing a truly representative aggregate preference of the entire network. In particular, we develop models and methods for solving the above problems, which primarily deal with formation and analysis of social networks.
Generating Appealing Brand Names
Venue: arXiv cs.CL 2017
Year: 2017

Providing appealing brand names to newly launched products, newly formed companies or for renaming existing companies is highly important as it can play a crucial role in deciding its success or failure. In this work, we propose a computational method to generate appealing brand names based on the description of such entities. We use quantitative scores for readability, pronounceability, memorability and uniqueness of the generated names to rank order them. A set of diverse appealing names is recommended to the user for the brand naming task. Experimental results show that the names generated by our approach are more appealing than names which prior approaches and recruited humans could come up.