OpenRaiser/Intern-Atlas huggingface dataset:
An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner
Venue: arXiv cs.DS 2017
Year: 2017

A tree $σ$-spanner of a positively real-weighted $n$-vertex and $m$-edge undirected graph $G$ is a spanning tree $T$ of $G$ which approximately preserves (i.e., up to a multiplicative stretch factor $σ$) distances in $G$. Tree spanners with provably good stretch factors find applications in communication networks, distributed systems, and network design. However, finding an optimal or even a good tree spanner is a very hard computational task. Thus, if one has to face a transient edge failure in $T$, the overall effort that has to be afforded to rebuild a new tree spanner (i.e., computational costs, set-up of new links, updating of the routing tables, etc.) can be rather prohibitive. To circumvent this drawback, an effective alternative is that of associating with each tree edge a best possible (in terms of resulting stretch) swap edge -- a well-established approach in the literature for several other tree topologies. Correspondingly, the problem of computing all the best swap edges of a tree spanner is a challenging algorithmic problem, since solving it efficiently means to exploit the structure of shortest paths not only in $G$, but also in all the scenarios in which an edge of $T$ has failed. For this problem we provide a very efficient solution, running in $O(n^2 \log^4 n)$ time, which drastically improves (almost by a quadratic factor in $n$ in dense graphs!) on the previous known best result.
Joint optimization of transmission and propulsion in aerial communication networks
Venue: arXiv cs.SY 2017
Year: 2017

Communication energy in a wireless network of mobile autonomous agents should be considered as the sum of transmission energy and propulsion energy used to facilitate the transfer of information. Accordingly, communication-theoretic and Newtonian dynamic models are developed to model the communication and locomotion expenditures of each node. These are subsequently used to formulate a novel nonlinear optimal control problem (OCP) over a network of autonomous nodes. It is then shown that, under certain conditions, the OCP can be transformed into an equivalent convex form. Numerical results for a single link between a node and access point allow for comparison with known solutions before the framework is applied to a multiple-node UAV network, for which previous results are not readily extended. Simulations show that transmission energy can be of the same order of magnitude as propulsion energy allowing for possible savings, whilst also exemplifying how speed adaptations together with power control may increase the network throughput.
The Parameterized Complexity of Centrality Improvement in Networks
Venue: arXiv cs.DM 2017
Year: 2017

The centrality of a vertex v in a network intuitively captures how important v is for communication in the network. The task of improving the centrality of a vertex has many applications, as a higher centrality often implies a larger impact on the network or less transportation or administration cost. In this work we study the parameterized complexity of the NP-complete problems Closeness Improvement and Betweenness Improvement in which we ask to improve a given vertex' closeness or betweenness centrality by a given amount through adding a given number of edges to the network. Herein, the closeness of a vertex v sums the multiplicative inverses of distances of other vertices to v and the betweenness sums for each pair of vertices the fraction of shortest paths going through v. Unfortunately, for the natural parameter "number of edges to add" we obtain hardness results, even in rather restricted cases. On the positive side, we also give an island of tractability for the parameter measuring the vertex deletion distance to cluster graphs.
Independent Low-Rank Matrix Analysis Based on Parametric Majorization-Equalization Algorithm
Venue: arXiv cs.SD 2017
Year: 2017

In this paper, we propose a new optimization method for independent low-rank matrix analysis (ILRMA) based on a parametric majorization-equalization algorithm. ILRMA is an efficient blind source separation technique that simultaneously estimates a spatial demixing matrix (spatial model) and the power spectrograms of each estimated source (source model). In ILRMA, since both models are alternately optimized by iterative update rules, the difference in the convergence speeds between these models often results in a poor local solution. To solve this problem, we introduce a new parameter that controls the convergence speed of the source model and find the best balance between the optimizations in the spatial and source models for ILRMA.
Analysis of Lur'e dominant systems in the frequency domain
Venue: arXiv cs.SY 2017
Year: 2017

Frequency domain analysis of linear time-invariant (LTI) systems in feedback with static nonlinearities is a classical and fruitful topic of nonlinear systems theory. We generalize this approach beyond equilibrium stability analysis with the aim of characterizing feedback systems whose asymptotic behavior is low dimensional. We illustrate the theory with a generalization of the circle criterion for the analysis of multistable and oscillatory Lur'e feedback systems.
IQ of Neural Networks
Venue: arXiv cs.LG 2017
Year: 2017

IQ tests are an accepted method for assessing human intelligence. The tests consist of several parts that must be solved under a time constraint. Of all the tested abilities, pattern recognition has been found to have the highest correlation with general intelligence. This is primarily because pattern recognition is the ability to find order in a noisy environment, a necessary skill for intelligent agents. In this paper, we propose a convolutional neural network (CNN) model for solving geometric pattern recognition problems. The CNN receives as input multiple ordered input images and outputs the next image according to the pattern. Our CNN is able to solve problems involving rotation, reflection, color, size and shape patterns and score within the top 5% of human performance.
Decomposition of Nonlinear Dynamical Systems Using Koopman Gramians
Venue: arXiv cs.SY 2017
Year: 2017

In this paper we propose a new Koopman operator approach to the decomposition of nonlinear dynamical systems using Koopman Gramians. We introduce the notion of an input-Koopman operator, and show how input-Koopman operators can be used to cast a nonlinear system into the classical state-space form, and identify conditions under which input and state observable functions are well separated. We then extend an existing method of dynamic mode decomposition for learning Koopman operators from data known as deep dynamic mode decomposition to systems with controls or disturbances. We illustrate the accuracy of the method in learning an input-state separable Koopman operator for an example system, even when the underlying system exhibits mixed state-input terms. We next introduce a nonlinear decomposition algorithm, based on Koopman Gramians, that maximizes internal subsystem observability and disturbance rejection from unwanted noise from other subsystems. We derive a relaxation based on Koopman Gramians and multi-way partitioning for the resulting NP-hard decomposition problem. We lastly illustrate the proposed algorithm with the swing dynamics for an IEEE 39-bus system.
The Energy Complexity of Broadcast
Venue: arXiv cs.DC 2017
Year: 2017

Energy is often the most constrained resource in networks of battery-powered devices, and as devices become smaller, they spend a larger fraction of their energy on communication (transceiver usage) not computation. As an imperfect proxy for true energy usage, we define energy complexity to be the number of time slots a device transmits/listens; idle time and computation are free. In this paper we investigate the energy complexity of fundamental communication primitives such as broadcast in multi-hop radio networks. We consider models with collision detection (CD) and without (No-CD), as well as both randomized and deterministic algorithms. Some take-away messages from this work include: 1. The energy complexity of broadcast in a multi-hop network is intimately connected to the time complexity of leader election in a single-hop (clique) network. Many existing lower bounds on time complexity immediately transfer to energy complexity. For example, in the CD and No-CD models, we need $Ω(\log n)$ and $Ω(\log^2 n)$ energy, respectively. 2. The energy lower bounds above can almost be achieved, given sufficient ($Ω(n)$) time. In the CD and No-CD models we can solve broadcast using $O(\frac{\log n\log\log n}{\log\log\log n})$ energy and $O(\log^3 n)$ energy, respectively. 3. The complexity measures of Energy and Time are in conflict, and it is an open problem whether both can be minimized simultaneously. We give a tradeoff showing it is possible to be nearly optimal in both measures simultaneously. For any constant $ε>0$, broadcast can be solved in $O(D^{1+ε}\log^{O(1/ε)} n)$ time with $O(\log^{O(1/ε)} n)$ energy, where $D$ is the diameter of the network.
FOCAN: A Fog-supported Smart City Network Architecture for Management of Applications in the Internet of Everything Environments
Venue: arXiv cs.DC 2017
Year: 2017

Smart city vision brings emerging heterogeneous communication technologies such as Fog Computing (FC) together to substantially reduce the latency and energy consumption of Internet of Everything (IoE) devices running various applications. The key feature that distinguishes the FC paradigm for smart cities is that it spreads communication and computing resources over the wired/wireless access network (e.g., proximate access points and base stations) to provide resource augmentation (e.g., cyberforaging) for resource and energy-limited wired/wireless (possibly mobile) things. Moreover, smart city applications are developed with the goal of improving the management of urban flows and allowing real-time responses to challenges that can arise in users' transactional relationships. This article presents a Fog-supported smart city network architecture called Fog Computing Architecture Network (FOCAN), a multi-tier structure in which the applications running on things jointly compute, route, and communicate with one another through the smart city environment to decrease latency and improve energy provisioning and the efficiency of services among things with different capabilities. An important concern that arises with the introduction of FOCAN is the need to avoid transferring data to/from distant things and instead to cover the nearest region for an IoT application. We define three types of communications between FOCAN devices (e.g., interprimary, primary, and secondary communication) to manage applications in a way that meets the quality of service standards for the IoE. One of the main advantages of FOCAN is that the devices can provide the services with low energy usage and in an efficient manner. Simulation results for a selected case study demonstrate the tremendous impact of the FOCAN energy-efficient solution on the communication performance of various types of things in smart cities.
A Modified DTC with Capability of Regenerative Braking Energy in BLDC driven Electric Vehicles Using Adaptive Control Theory
Venue: arXiv cs.SY 2017
Year: 2017

This paper represents a novel regenerative braking approach for the Electric Vehicles. The proposed method solves the short-range problem which is corresponding to the charge of the battery pack. The DTC switching algorithm has been modified to recover the electrical energy from Electrical Vehicle (EV), driven by Brushless DC motor, without using the additional power converter or the other electrical energy storage devices. During regenerative braking process, different switching pattern is applied to the inverter to convert the mechanical energy to the electrical energy through the reverse diodes. This switching pattern is different from the normal operation due to the special arrangement of voltage vectors which is considered to convert the mechanical energy to electrical energy. The state of charge of the battery is used as a performance indicator of the method. Simultaneously, a model reference adaptive system has been designed to tune the system parameters. Several simulations are carried out to validate the performance and effectiveness of the proposed methods. The results show the high capability and performance of the designed method.
Efficiently repairing algebraic geometry codes
Venue: arXiv cs.IT 2017
Year: 2017

Minimum storage regenerating codes have minimum storage of data in each node and therefore are maximal distance separable (MDS for short) codes. Thus, the number of nodes is upper bounded by $2^{\fb}$, where $\fb$ is the bits of data stored in each node. From both theoretical and practical points of view (see the details in Section 1), it is natural to consider regenerating codes that nearly have minimum storage of data, and meanwhile the number of nodes is unbounded. One of the candidates for such regenerating codes is an algebraic geometry code. In this paper, we generalize the repairing algorithm of Reed-Solomon codes given in \cite[STOC2016]{GW16} to algebraic geometry codes and present an efficient repairing algorithm for arbitrary one-point algebraic geometry codes. By applying our repairing algorithm to the one-point algebraic geometry codes based on the Garcia-Stichtenoth tower, one can repair a code of rate $1-\Ge$ and length $n$ over $\F_{q}$ with bandwidth $(n-1)(1-\Gt)\log q$ for any $\Ge=2^{(\Gt-1/2)\log q}$ with a real $τ\in(0,1/2)$. In addition, storage in each node for an algebraic geometry code is close to the minimum storage. Due to nice structures of Hermitian curves, repairing of Hermitian codes is also investigated. As a result, we are able to show that algebraic geometry codes are regenerating codes with good parameters. An example reveals that Hermitian codes outperform Reed-Solomon codes for certain parameters.
NTRUCipher-Lattice Based Secret Key Encryption
Venue: arXiv cs.CR 2017
Year: 2017

NTRU cryptosystem has allowed designing a range of cryptographic schemes due to its flexibility and efficiency. Although NTRU cryptosystem was introduced nearly two decades ago, it has not yet received any attention like designing a secret key encryption. In this paper, we propose a secret key encryption over NTRU lattices, named as NTRUCipher. This NTRUCipher is designed using modification of the NTRU public key encryption. We analyze this cipher efficiency and the space complexity with respect to security aspects, and also show that the NTRUCipher is secured under the indistinguishability chosen plaintext attack.
Model-Theoretic Characterizations of Boolean and Arithmetic Circuit Classes of Small Depth
Venue: arXiv cs.CC 2017
Year: 2017

In this paper we give a characterization of both Boolean and arithmetic circuit classes of logarithmic depth in the vein of descriptive complexity theory, i.e., the Boolean classes $\textrm{NC}^1$, $\textrm{SAC}^1$ and $\textrm{AC}^1$ as well as their arithmetic counterparts $\#\textrm{NC}^1$, $\#\textrm{SAC}^1$ and $\#\textrm{AC}^1$. We build on Immerman's characterization of constant-depth polynomial-size circuits by formulas of first-order logic, i.e., $\textrm{AC}^0 = \textrm{FO}$, and augment the logical language with an operator for defining relations in an inductive way. Considering slight variations of the new operator, we obtain uniform characterizations of the three just mentioned Boolean classes. The arithmetic classes can then be characterized by functions counting winning strategies in semantic games for formulas characterizing languages in the corresponding Boolean class.
Civil Asset Forfeiture: A Judicial Perspective
Venue: arXiv cs.CY 2017
Year: 2017

Civil Asset Forfeiture (CAF) is a longstanding and controversial legal process viewed on the one hand as a powerful tool for combating drug crimes and on the other hand as a violation of the rights of US citizens. Data used to support both sides of the controversy to date has come from government sources representing records of the events at the time of occurrence. Court dockets represent litigation events initiated following the forfeiture, however, and can thus provide a new perspective on the CAF legal process. This paper will show new evidence supporting existing claims about the growth of the practice and bias in its application based on the quantitative analysis of data derived from these court cases.
Indowordnets help in Indian Language Machine Translation
Venue: arXiv cs.CL 2017
Year: 2017

Being less resource languages, Indian-Indian and English-Indian language MT system developments faces the difficulty to translate various lexical phenomena. In this paper, we present our work on a comparative study of 440 phrase-based statistical trained models for 110 language pairs across 11 Indian languages. We have developed 110 baseline Statistical Machine Translation systems. Then we have augmented the training corpus with Indowordnet synset word entries of lexical database and further trained 110 models on top of the baseline system. We have done a detailed performance comparison using various evaluation metrics such as BLEU score, METEOR and TER. We observed significant improvement in evaluations of translation quality across all the 440 models after using the Indowordnet. These experiments give a detailed insight in two ways : (1) usage of lexical database with synset mapping for resource poor languages (2) efficient usage of Indowordnet sysnset mapping. More over, synset mapped lexical entries helped the SMT system to handle the ambiguity to a great extent during the translation.
Multiframe Scene Flow with Piecewise Rigid Motion
Venue: arXiv cs.CV 2017
Year: 2017

We introduce a novel multiframe scene flow approach that jointly optimizes the consistency of the patch appearances and their local rigid motions from RGB-D image sequences. In contrast to the competing methods, we take advantage of an oversegmentation of the reference frame and robust optimization techniques. We formulate scene flow recovery as a global non-linear least squares problem which is iteratively solved by a damped Gauss-Newton approach. As a result, we obtain a qualitatively new level of accuracy in RGB-D based scene flow estimation which can potentially run in real-time. Our method can handle challenging cases with rigid, piecewise rigid, articulated and moderate non-rigid motion, and does not rely on prior knowledge about the types of motions and deformations. Extensive experiments on synthetic and real data show that our method outperforms state-of-the-art.
Collaborative Platooning of Automated Vehicles Using Variable Time-Gaps
Venue: arXiv cs.SY 2017
Year: 2017

Connected automated vehicles (CAVs) could potentially be coordinated to safely attain the maximum traffic flow on roadways under dynamic traffic patterns, such as those engendered by the merger of two strings of vehicles due a lane drop. Strings of vehicles have to be shaped correctly in terms of the inter-vehicular time-gap and velocity to ensure that such operation is feasible. However, controllers that can achieve such traffic shaping over the multiple dimensions of target time-gap and velocity over a region of space are unknown. The objective of this work is to design such a controller, and to show that we can design candidate time-gap and velocity profiles such that it can stabilize the string of vehicles in attaining the target profiles. Our analysis is based on studying the system in the spacial rather than the time domain, which enables us to study stability as in terms of minimizing errors from the target profile and across vehicles as a function of location. Finally, we conduct numeral simulations in the context of shaping two platoons for merger, which we use to illustrate how to select time-gap and velocity profiles for maximizing flow and maintaining safety.
Ground Edge based LIDAR Localization without a Reflectivity Calibration for Autonomous Driving
Venue: arXiv cs.RO 2017
Year: 2017

In this work we propose an alternative formulation to the problem of ground reflectivity grid based localization involving laser scanned data from multiple LIDARs mounted on autonomous vehicles. The driving idea of our localization formulation is an alternative edge reflectivity grid representation which is invariant to laser source, angle of incidence, range and robot surveying motion. Such property eliminates the need of the post-factory reflectivity calibration whose time requirements are infeasible in mass produced robots/vehicles. Our experiments demonstrate that we can achieve better performance than state of the art on ground reflectivity inference-map based localization at no additional computational burden.
Stacked Structure Learning for Lifted Relational Neural Networks
Venue: arXiv cs.LG 2017
Year: 2017

Lifted Relational Neural Networks (LRNNs) describe relational domains using weighted first-order rules which act as templates for constructing feed-forward neural networks. While previous work has shown that using LRNNs can lead to state-of-the-art results in various ILP tasks, these results depended on hand-crafted rules. In this paper, we extend the framework of LRNNs with structure learning, thus enabling a fully automated learning process. Similarly to many ILP methods, our structure learning algorithm proceeds in an iterative fashion by top-down searching through the hypothesis space of all possible Horn clauses, considering the predicates that occur in the training examples as well as invented soft concepts entailed by the best weighted rules found so far. In the experiments, we demonstrate the ability to automatically induce useful hierarchical soft concepts leading to deep LRNNs with a competitive predictive power.
Improved Upper Bound on the Network Function Computing Capacity
Venue: arXiv cs.IT 2017
Year: 2017

The problem of network function computation over a directed acyclic network is investigated in this paper. In such a network, a sink node desires to compute with zero error a {\em target function}, of which the inputs are generated at multiple source nodes. The edges in the network are assumed to be error-free and have limited capacity. The nodes in the network are assumed to have unbounded computing capability and be able to perform network coding. The {\em computing rate} of a network code that can compute the target function over the network is the average number of times that the target function is computed with zero error for one use of the network. In this paper, we obtain an improved upper bound on the computing capacity, which is applicable to arbitrary target functions and arbitrary network topologies. This improved upper bound not only is an enhancement of the previous upper bounds but also is the first tight upper bound on the computing capacity for computing an arithmetic sum over a certain non-tree network, which has been widely studied in the literature. We also introduce a multi-dimensional array approach that facilitates evaluation of the improved upper bound. Furthermore, we apply this bound to the problem of computing a vector-linear function over a network. With this bound, we are able to not only enhance a previous result on computing a vector-linear function over a network but also simplify the proof significantly. Finally, we prove that for computing the binary maximum function over the reverse butterfly network, our improved upper bound is not achievable. This result establishes that in general our improved upper bound is non achievable, but whether it is asymptotically achievable or not remains open.