OpenRaiser/Intern-Atlas huggingface dataset:
Reoptimization of the Closest Substring Problem under Pattern Length Modification
Venue: arXiv cs.DS 2017
Year: 2017

This study investigates whether reoptimization can help in solving the closest substring problem. We are dealing with the following reoptimization scenario. Suppose, we have an optimal l-length closest substring of a given set of sequences S. How can this information be beneficial in obtaining an (l+k)-length closest substring for S? In this study, we show that the problem is still computationally hard even with k=1. We present greedy approximation algorithms that make use of the given information and prove that it has an additive error that grows as the parameter k increases. Furthermore, we present hard instances for each algorithm to show that the computed approximation ratio is tight. We also show that we can slightly improve the running-time of the existing polynomial-time approximation scheme (PTAS) for the original problem through reoptimization.
Inference-Based Distributed Channel Allocation in Wireless Sensor Networks
Venue: arXiv cs.IT 2017
Year: 2017

Interference-aware resource allocation of time slots and frequency channels in single-antenna, halfduplex radio wireless sensor networks (WSN) is challenging. Devising distributed algorithms for such task further complicates the problem. This work studiesWSN joint time and frequency channel allocation for a given routing tree, such that: a) allocation is performed in a fully distributed way, i.e., information exchange is only performed among neighboring WSN terminals, within communication up to two hops, and b) detection of potential interfering terminals is simplified and can be practically realized. The algorithm imprints space, time, frequency and radio hardware constraints into a loopy factor graph and performs iterative message passing/ loopy belief propagation (BP) with randomized initial priors. Sufficient conditions for convergence to a valid solution are offered, for the first time in the literature, exploiting the structure of the proposed factor graph. Based on theoretical findings, modifications of BP are devised that i) accelerate convergence to a valid solution and ii) reduce computation cost. Simulations reveal promising throughput results of the proposed distributed algorithm, even though it utilizes simplified interfering terminals set detection. Future work could modify the constraints such that other disruptive wireless technologies (e.g., full-duplex radios or network coding) could be accommodated within the same inference framework.
Timbre Analysis of Music Audio Signals with Convolutional Neural Networks
Venue: arXiv cs.SD 2017
Year: 2017

The focus of this work is to study how to efficiently tailor Convolutional Neural Networks (CNNs) towards learning timbre representations from log-mel magnitude spectrograms. We first review the trends when designing CNN architectures. Through this literature overview we discuss which are the crucial points to consider for efficiently learning timbre representations using CNNs. From this discussion we propose a design strategy meant to capture the relevant time-frequency contexts for learning timbre, which permits using domain knowledge for designing architectures. In addition, one of our main goals is to design efficient CNN architectures -- what reduces the risk of these models to over-fit, since CNNs' number of parameters is minimized. Several architectures based on the design principles we propose are successfully assessed for different research tasks related to timbre: singing voice phoneme classification, musical instrument recognition and music auto-tagging.
Complex Number Formulation and Convex Relaxations for Aircraft Conflict Resolution
Venue: arXiv cs.CE 2017
Year: 2017

We present a novel complex number formulation along with tight convex relaxations for the aircraft conflict resolution problem. Our approach combines both speed and heading control and provides global optimality guarantees despite non-convexities in the feasible region. As a side result, we present a new characterization of the conflict separation condition in the form of disjunctive linear constraints. Our formulation features one binary variable per pair of aircraft, is free of trigonometric functions, and captures the non-convexity in a set of quadratic concave constraints. Using our approach, we are able to close a number of open instances and reduce computational time by up to two orders of magnitude on standard instances.
On Auxiliary Entity Allocation Problem in Multi-layered Interdependent Critical Infrastructures
Venue: arXiv cs.NI 2017
Year: 2017

Operation of critical infrastructures are highly interdependent on each other. Such dependencies causes failure in these infrastructures to cascade on an initial failure event. Owing to this vulnerability it is imperative to incorporate efficient strategies for their protection. Modifying dependencies by adding additional dependency implications using entities (termed as \emph{auxiliary entities}) is shown to mitigate this issue to a certain extent. With this finding, in this article we introduce the Auxiliary Entity Allocation problem. The objective is to maximize protection in Power and Communication infrastructures using a budget in number of dependency modifications using the auxiliary entities. The problem is proved to be NP-complete in general case. We provide an optimal solution using Integer Linear program and a heuristic for a restricted case. The efficacy of heuristic with respect to the optimal is judged through experimentation using real world data sets with heuristic deviating $6.75 \%$ from optimal on average.
Distributed Constraint Problems for Utilitarian Agents with Privacy Concerns, Recast as POMDPs
Venue: arXiv cs.AI 2017
Year: 2017

Privacy has traditionally been a major motivation for distributed problem solving. Distributed Constraint Satisfaction Problem (DisCSP) as well as Distributed Constraint Optimization Problem (DCOP) are fundamental models used to solve various families of distributed problems. Even though several approaches have been proposed to quantify and preserve privacy in such problems, none of them is exempt from limitations. Here we approach the problem by assuming that computation is performed among utilitarian agents. We introduce a utilitarian approach where the utility of each state is estimated as the difference between the reward for reaching an agreement on assignments of shared variables and the cost of privacy loss. We investigate extensions to solvers where agents integrate the utility function to guide their search and decide which action to perform, defining thereby their policy. We show that these extended solvers succeed in significantly reducing privacy loss without significant degradation of the solution quality.
Multi-style Generative Network for Real-time Transfer
Venue: arXiv cs.CV 2017
Year: 2017

Despite the rapid progress in style transfer, existing approaches using feed-forward generative network for multi-style or arbitrary-style transfer are usually compromised of image quality and model flexibility. We find it is fundamentally difficult to achieve comprehensive style modeling using 1-dimensional style embedding. Motivated by this, we introduce CoMatch Layer that learns to match the second order feature statistics with the target styles. With the CoMatch Layer, we build a Multi-style Generative Network (MSG-Net), which achieves real-time performance. We also employ an specific strategy of upsampled convolution which avoids checkerboard artifacts caused by fractionally-strided convolution. Our method has achieved superior image quality comparing to state-of-the-art approaches. The proposed MSG-Net as a general approach for real-time style transfer is compatible with most existing techniques including content-style interpolation, color-preserving, spatial control and brush stroke size control. MSG-Net is the first to achieve real-time brush-size control in a purely feed-forward manner for style transfer. Our implementations and pre-trained models for Torch, PyTorch and MXNet frameworks will be publicly available.
Pattern Division Multiple Access with Large-scale Antenna Array
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, pattern division multiple access with large-scale antenna array (LSA-PDMA) is proposed as a novel non-orthogonal multiple access (NOMA) scheme. In the proposed scheme, pattern is designed in both beam domain and power domain in a joint manner. At the transmitter, pattern mapping utilizes power allocation to improve the system sum rate and beam allocation to enhance the access connectivity and realize the integration of LSA into multiple access spontaneously. At the receiver, hybrid detection of spatial filter (SF) and successive interference cancellation (SIC) is employed to separate the superposed multiple-domain signals. Furthermore, we formulate the sum rate maximization problem to obtain the optimal pattern mapping policy, and the optimization problem is proved to be convex through proper mathematical manipulations. Simulation results show that the proposed LSA-PDMA scheme achieves significant performance gain on system sum rate compared to both the orthogonal multiple access scheme and the power-domain NOMA scheme.
Fog Computing for Sustainable Smart Cities: A Survey
Venue: arXiv cs.NI 2017
Year: 2017

The Internet of Things (IoT) aims to connect billions of smart objects to the Internet, which can bring a promising future to smart cities. These objects are expected to generate large amounts of data and send the data to the cloud for further processing, specially for knowledge discovery, in order that appropriate actions can be taken. However, in reality sensing all possible data items captured by a smart object and then sending the complete captured data to the cloud is less useful. Further, such an approach would also lead to resource wastage (e.g. network, storage, etc.). The Fog (Edge) computing paradigm has been proposed to counterpart the weakness by pushing processes of knowledge discovery using data analytics to the edges. However, edge devices have limited computational capabilities. Due to inherited strengths and weaknesses, neither Cloud computing nor Fog computing paradigm addresses these challenges alone. Therefore, both paradigms need to work together in order to build an sustainable IoT infrastructure for smart cities. In this paper, we review existing approaches that have been proposed to tackle the challenges in the Fog computing domain. Specifically, we describe several inspiring use case scenarios of Fog computing, identify ten key characteristics and common features of Fog computing, and compare more than 30 existing research efforts in this domain. Based on our review, we further identify several major functionalities that ideal Fog computing platforms should support and a number of open challenges towards implementing them, so as to shed light on future research directions on realizing Fog computing for building sustainable smart cities.
Full-duplex Amplify-and-Forward Relaying: Power and Location Optimization
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we consider a full-duplex (FD) amplify-and-forward (AF) relay system and optimize its power allocation and relay location to minimize the system symbol error rate (SER). We first derive the asymptotic expressions of the outage probability and SER performance by taking into account the residual self interference (RSI) in FD systems. We then formulate the optimization problem based on the minimal SER criterion. Analytical and numerical results show that optimized relay location and power allocation can greatly improve system SER performance, and the performance floor caused by the RSI can be significantly reduced via optimizing relay location or power allocation.
Frequency Offset Estimation for OFDM Systems with a Novel Frequency Domain Training Sequence
Venue: arXiv cs.IT 2017
Year: 2017

A novel frequency domain training sequence and the corresponding carrier frequency offset (CFO) estimator are proposed for orthogonal frequency division multiplexing (OFDM) systems over frequency-selective fading channels. The proposed frequency domain training sequence comprises two types of pilot tones, namely distinctively spaced pilot tones with high energies and uniformly spaced ones with low energies. Based on the distinctively spaced pilot tones, integer CFO estimation is accomplished. After the subcarriers occupied by the distinctively spaced pilot tones and their adjacent subcarriers are nulled for the sake of interference cancellation, fractional CFO estimation is executed according to the uniformly spaced pilot tones. By exploiting a predefined lookup table making the best of the structure of the distinctively spaced pilot tones, computational complexity of the proposed CFO estimator can be decreased considerably. With the aid of the uniformly spaced pilot tones generated from Chu sequence with cyclically orthogonal property, the ability of the proposed estimator to combat multipath effect is enhanced to a great extent. Simulation results illustrate the good performance of the proposed CFO estimator.
Zero-Error Affine, Unitary, and Probabilistic OBDDs
Venue: arXiv cs.CC 2017
Year: 2017

We introduce the affine OBDD model and show that zero-error affine OBDDs can be exponentially narrower than bounded-error unitary and probabilistic OBDDs on certain problems. Moreover, we show that Las Vegas unitary and probabilistic OBDDs can be quadratically narrower than deterministic OBDDs. We also obtain the same results by considering the automata versions of these models.
Materials in Participatory Design Processes
Venue: arXiv cs.HC 2017
Year: 2017

This dissertation presents three years of academic inquiry into the question of what role materials play in interaction design and participatory design processes. The dissertation aims at developing conceptual tools, based on Deweys pragmatism, for understanding how materials aid design reflection. It has been developed using a research-through-design approach in which the author has conducted practical design work in order to investigate and experiment with using materials to scaffold design inquiry. The results of the PhD work is submitted as seven separate papers, submitted to esteemed journals and conferences within the field of interaction design and HCI. The work is motivated both by the growing interest in materials in interaction design and HCI and the interest in design processes and collaboration within those fields. At the core of the dissertation lies an interest in the many different materials used during the design process: sketches, prototypes as well as the materials we shape products out of: physical and digital materials now form a unity of computation and physical materials that has given rise to a new research interest in design and materiality. The main results from the dissertation are an understanding of design materials that draws on pragmatist philosophy. The papers and overview article highlights how materials in a pragmatist perspective are more than the matter out of which we shape an idea. Rather they structure the entire process of inquiry, helping us frame problems, inspire solutions and try out these solutions in practice. This framework, developed in several of the submitted papers, is tested and illustrated through a series of experimental design cases.
Kalman Filtering of Distributed Time Series
Venue: arXiv cs.GL 2017
Year: 2017

This paper aims to introduce an application to Kalman Filtering Theory, which is rather unconventional. Recent experiments have shown that many natural phenomena, especially from ecology or meteorology, could be monitored and predicted more accurately when accounting their evolution over some geographical area. Thus, the signals they provide are gathered together into a collection of distributed time series. Despite the common sense, such time series are more or less correlated each other. Instead of processing each time series independently, their collection can constitute the set of measurable states provided by some open system. Modeling and predicting the system states can take benefit from the family of Kalman filtering algorithms. The article describes an adaptation of basic Kalman filter to the context of distributed signals collections and completes with an application coming from Meteorology.
The Effect of Phasor Measurement Units on the Accuracy of the Network Estimated Variables
Venue: arXiv cs.SY 2017
Year: 2017

The most commonly used weighted least square state estimator in power industry is nonlinear and formulated by using conventional measurements such as line flow and injection measurements. PMUs (Phasor Measurement Units) are gradually adding them to improve the state estimation process. In this paper the way of corporation the PMU data to the conventional measurements and a linear formulation of the state estimation using only PMU measured data are investigated. Six cases are tested while gradually increasing the number of PMUs which are added to the measurement set and the effect of PMUs on the accuracy of variables are illustrated and compared by applying them on IEEE 14, 30 test systems.
An Accelerated Analog Neuromorphic Hardware System Emulating NMDA- and Calcium-Based Non-Linear Dendrites
Venue: arXiv cs.NE 2017
Year: 2017

This paper presents an extension of the BrainScaleS accelerated analog neuromorphic hardware model. The scalable neuromorphic architecture is extended by the support for multi-compartment models and non-linear dendrites. These features are part of a \SI{65}{\nano\meter} prototype ASIC. It allows to emulate different spike types observed in cortical pyramidal neurons: NMDA plateau potentials, calcium and sodium spikes. By replicating some of the structures of these cells, they can be configured to perform coincidence detection within a single neuron. Built-in plasticity mechanisms can modify not only the synaptic weights, but also the dendritic synaptic composition to efficiently train large multi-compartment neurons. Transistor-level simulations demonstrate the functionality of the analog implementation and illustrate analogies to biological measurements.
Resilience of Complex Networks
Venue: arXiv cs.SY 2017
Year: 2017

This article determines and characterizes the minimal number of actuators needed to ensure structural controllability of a linear system under structural alterations that can severe the connection between any two states. We assume that initially the system is structurally controllable with respect to a given set of controls, and propose an efficient system-synthesis mechanism to find the minimal number of additional actuators required for resilience of the system w.r.t such structural changes. The effectiveness of this approach is demonstrated by using standard IEEE power networks.
Multi Agent Driven Data Mining For Knowledge Discovery in Cloud Computing
Venue: arXiv cs.DB 2017
Year: 2017

Today, huge amount of data is available on the web. Now there is a need to convert that data in knowledge which can be useful for different purposes. This paper depicts the use of data mining process, OLAP with the combination of multi agent system to find the knowledge from data in cloud computing. For this, I am also trying to explain one case study of online shopping of one Bakery Shop. May be we can increase the sale of items by using the model, which I am trying to represent.
Distributed Distance-Bounded Network Design Through Distributed Convex Programming
Venue: arXiv cs.DS 2017
Year: 2017

Solving linear programs is often a challenging task in distributed settings. While there are good algorithms for solving packing and covering linear programs in a distributed manner (Kuhn et al.~2006), this is essentially the only class of linear programs for which such an algorithm is known. In this work we provide a distributed algorithm for solving a different class of convex programs which we call "distance-bounded network design convex programs". These can be thought of as relaxations of network design problems in which the connectivity requirement includes a distance constraint (most notably, graph spanners). Our algorithm runs in $O( (D/ε) \log n)$ rounds in the $\mathcal{LOCAL}$ model and finds a $(1+ε)$-approximation to the optimal LP solution for any $0 < ε\leq 1$, where $D$ is the largest distance constraint. While solving linear programs in a distributed setting is interesting in its own right, this class of convex programs is particularly important because solving them is often a crucial step when designing approximation algorithms. Hence we almost immediately obtain new and improved distributed approximation algorithms for a variety of network design problems, including Basic $3$- and $4$-Spanner, Directed $k$-Spanner, Lowest Degree $k$-Spanner, and Shallow-Light Steiner Network Design with a spanning demand graph. Our algorithms do not require any "heavy" computation and essentially match the best-known centralized approximation algorithms, while previous approaches which do not use heavy computation give approximations which are worse than the best-known centralized bounds.
Cognitive Hierarchy Theory for Distributed Resource Allocation in the Internet of Things
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, the problem of distributed resource allocation is studied for an Internet of Things (IoT) system, composed of a heterogeneous group of nodes compromising both machine-type devices (MTDs) and human-type devices (HTDs). The problem is formulated as a noncooperative game between the heterogeneous IoT devices that seek to find the optimal time allocation so as to meet their quality-of-service (QoS) requirements in terms of energy, rate and latency. Since the strategy space of each device is dependent on the actions of the other devices, the generalized Nash equilibrium (GNE) solution is first characterized, and the conditions for uniqueness of the GNE are derived. Then, to explicitly capture the heterogeneity of the devices, in terms of resource constraints and QoS needs, a novel and more realistic game-theoretic approach, based on the behavioral framework of cognitive hierarchy (CH) theory, is proposed. This approach is then shown to enable the IoT devices to reach a CH equilibrium (CHE) concept that takes into account the various levels of rationality corresponding to the heterogeneous computational capabilities and the information accessible for each one of the MTDs and HTDs. Simulation results show that the proposed CHE solution keeps the percentage of devices with satisfied QoS constraints above 96% for IoT networks containing up to 10,000 devices without considerably degrading the overall system performance.