OpenRaiser/Intern-Atlas huggingface dataset:
Expurgated Bounds for the Asymmetric Broadcast Channel
Venue: arXiv cs.IT 2017
Year: 2017

This work contains two main contributions concerning the expurgation of hierarchical ensembles for the asymmetric broadcast channel. The first is an analysis of the optimal maximum likelihood (ML) decoders for the weak and strong user. Two different methods of code expurgation will be used, that will provide two competing error exponents. The second is the derivation of expurgated exponents under the generalized stochastic likelihood decoder (GLD). We prove that the GLD exponents are at least as tight as the maximum between the random coding error exponents derived in an earlier work by Averbuch and Merhav (2017) and one of our ML-based expurgated exponents. By that, we actually prove the existence of hierarchical codebooks that achieve the best of the random coding exponent and the expurgated exponent simultaneously for both users.
Seeded Graph Matching: Efficient Algorithms and Theoretical Guarantees
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, a new information theoretic framework for graph matching is introduced. Using this framework, the graph isomorphism and seeded graph matching problems are studied. The maximum degree algorithm for graph isomorphism is analyzed and sufficient conditions for successful matching are rederived using type analysis. Furthermore, a new seeded matching algorithm with polynomial time complexity is introduced. The algorithm uses `typicality matching' and techniques from point-to-point communications for reliable matching. Assuming an Erdos-Renyi model on the correlated graph pair, it is shown that successful matching is guaranteed when the number of seeds grows logarithmically with the number of vertices in the graphs. The logarithmic coefficient is shown to be inversely proportional to the mutual information between the edge variables in the two graphs.
Sentiment analysis of twitter data
Venue: arXiv cs.IR 2017
Year: 2017

Social networks are the main resources to gather information about people's opinion and sentiments towards different topics as they spend hours daily on social media and share their opinion. In this technical paper, we show the application of sentimental analysis and how to connect to Twitter and run sentimental analysis queries. We run experiments on different queries from politics to humanity and show the interesting results. We realized that the neutral sentiments for tweets are significantly high which clearly shows the limitations of the current works.
The robot skin placement problem: a new technique to place triangular modules inside polygons
Venue: arXiv cs.RO 2017
Year: 2017

Providing robots with large-scale robot skin is a challenging goal, especially when considering surfaces characterized by different shapes and curvatures. The problem originates from technological advances in tactile sensing, and in particular from two requirements: (i) covering the largest possible area of a robot's surface with tactile sensors, and (ii) doing it using cheap, replicable hardware modules. Given modules of a specific shape, the problem of optimally placing them requires to maximize the number of modules that can be fixed on the selected robot body part. Differently from previous approaches, which are based on methods inspired by computational geometry (e.g., packing), we propose a novel layout design method inspired by physical insights, referred to as Iterative Placement (ItPla), which arranges modules as if physical forces acted on them. A number of case studies from the literature are considered to evaluate the algorithm.
Faster range minimum queries
Venue: arXiv cs.DS 2017
Year: 2017

Range Minimum Query (RMQ) is an important building brick of many compressed data structures and string matching algorithms. Although this problem is essentially solved in theory, with sophisticated data structures allowing for constant time queries, practical performance and construction time also matter. Additionally, there are offline scenarios in which the number of queries, $q$, is rather small and given beforehand, which encourages to use a simpler approach. In this work, we present a simple data structure, with very fast construction, which allows to handle queries in constant time on average. This algorithm, however, requires access to the input data during queries (which is not the case of sophisticated RMQ solutions). We subsequently refine our technique, combining it with one of the existing succinct solutions with $O(1)$ worst-case time queries and no access to the input array. The resulting hybrid is still a memory frugal data structure, spending usually up to about $3n$ bits, and providing competitive query times, especially for wide ranges. We also show how to make our baseline data structure more compact. Experimental results demonstrate that the proposed BbST (Block-based Sparse Table) variants are competitive to existing solutions, also in the offline scenario.
Sampling Markov Models under Constraints: Complexity Results for Binary Equalities and Grammar Membership
Venue: arXiv cs.CC 2017
Year: 2017

We aim at enforcing hard constraints to impose a global structure on sequences generated from Markov models. In this report, we study the complexity of sampling Markov sequences under two classes of constraints: Binary Equalities and Grammar Membership Constraints. First, we give a sketch of proof of #P-completeness for binary equalities and identify three sub-cases where sampling is polynomial. We then give a proof of #P-completeness for grammar membership, and identify two cases where sampling is tractable. The first polynomial sub-case where sampling is tractable is when the grammar is proven to be unambiguous. Our main contribution is to identify a new, broader class of grammars for which sampling is tractable. We provide algorithm along with time and space complexity for all the polynomial cases we have identified.
VLSI Design of a Nonparametric Equalizer for Massive MU-MIMO
Venue: arXiv cs.IT 2017
Year: 2017

Linear minimum mean-square error (L-MMSE) equalization is among the most popular methods for data detection in massive multi-user multiple-input multiple-output (MU-MIMO) wireless systems. While L-MMSE equalization enables near-optimal spectral efficiency, accurate knowledge of the signal and noise powers is necessary. Furthermore, corresponding VLSI designs must solve linear systems of equations, which requires high arithmetic precision, exhibits stringent data dependencies, and results in high circuit complexity. This paper proposes the first VLSI design of the NOnParametric Equalizer (NOPE), which avoids knowledge of the transmit signal and noise powers, provably delivers the performance of L-MMSE equalization for massive MU-MIMO systems, and is resilient to numerous system and hardware impairments due to its parameter-free nature. Moreover, NOPE avoids computation of a matrix inverse and only requires hardware-friendly matrix-vector multiplications. To showcase the practical advantages of NOPE, we propose a parallel VLSI architecture and provide synthesis results in 28nm CMOS. We demonstrate that NOPE performs on par with existing data detectors for massive MU-MIMO that require accurate knowledge of the signal and noise powers.
Openmv: A Python powered, extensible machine vision camera
Venue: arXiv cs.CV 2017
Year: 2017

Advances in semiconductor manufacturing processes and large scale integration keep pushing demanding applications further away from centralized processing, and closer to the edges of the network (i.e. Edge Computing). It has become possible to perform complex in-network image processing using low-power embedded smart cameras, enabling a multitude of new collaborative image processing applications. This paper introduces OpenMV, a new low-power smart camera that lends itself naturally to wireless sensor networks and machine vision applications. The uniqueness of this platform lies in running an embedded Python3 interpreter, allowing its peripherals and machine vision library to be scripted in Python. In addition, its hardware is extensible via modules that augment the platform with new capabilities, such as thermal imaging and networking modules.
Highlighting objects of interest in an image by integrating saliency and depth
Venue: arXiv cs.CV 2017
Year: 2017

Stereo images have been captured primarily for 3D reconstruction in the past. However, the depth information acquired from stereo can also be used along with saliency to highlight certain objects in a scene. This approach can be used to make still images more interesting to look at, and highlight objects of interest in the scene. We introduce this novel direction in this paper, and discuss the theoretical framework behind the approach. Even though we use depth from stereo in this work, our approach is applicable to depth data acquired from any sensor modality. Experimental results on both indoor and outdoor scenes demonstrate the benefits of our algorithm.
Intent-Aware Contextual Recommendation System
Venue: arXiv cs.IR 2017
Year: 2017

Recommender systems take inputs from user history, use an internal ranking algorithm to generate results and possibly optimize this ranking based on feedback. However, often the recommender system is unaware of the actual intent of the user and simply provides recommendations dynamically without properly understanding the thought process of the user. An intelligent recommender system is not only useful for the user but also for businesses which want to learn the tendencies of their users. Finding out tendencies or intents of a user is a difficult problem to solve. Keeping this in mind, we sought out to create an intelligent system which will keep track of the user's activity on a web-application as well as determine the intent of the user in each session. We devised a way to encode the user's activity through the sessions. Then, we have represented the information seen by the user in a high dimensional format which is reduced to lower dimensions using tensor factorization techniques. The aspect of intent awareness (or scoring) is dealt with at this stage. Finally, combining the user activity data with the contextual information gives the recommendation score. The final recommendations are then ranked using filtering and collaborative recommendation techniques to show the top-k recommendations to the user. A provision for feedback is also envisioned in the current system which informs the model to update the various weights in the recommender system. Our overall model aims to combine both frequency-based and context-based recommendation systems and quantify the intent of a user to provide better recommendations. We ran experiments on real-world timestamped user activity data, in the setting of recommending reports to the users of a business analytics tool and the results are better than the baselines. We also tuned certain aspects of our model to arrive at optimized results.
Deep learning analysis of breast MRIs for prediction of occult invasive disease in ductal carcinoma in situ
Venue: arXiv cs.CV 2017
Year: 2017

Purpose: To determine whether deep learning-based algorithms applied to breast MR images can aid in the prediction of occult invasive disease following the di- agnosis of ductal carcinoma in situ (DCIS) by core needle biopsy. Material and Methods: In this institutional review board-approved study, we analyzed dynamic contrast-enhanced fat-saturated T1-weighted MRI sequences of 131 patients at our institution with a core needle biopsy-confirmed diagnosis of DCIS. The patients had no preoperative therapy before breast MRI and no prior history of breast cancer. We explored two different deep learning approaches to predict whether there was a hidden (occult) invasive component in the analyzed tumors that was ultimately detected at surgical excision. In the first approach, we adopted the transfer learning strategy, in which a network pre-trained on a large dataset of natural images is fine-tuned with our DCIS images. Specifically, we used the GoogleNet model pre-trained on the ImageNet dataset. In the second approach, we used a pre-trained network to extract deep features, and a support vector machine (SVM) that utilizes these features to predict the upstaging of the DCIS. We used 10-fold cross validation and the area under the ROC curve (AUC) to estimate the performance of the predictive models. Results: The best classification performance was obtained using the deep features approach with GoogleNet model pre-trained on ImageNet as the feature extractor and a polynomial kernel SVM used as the classifier (AUC = 0.70, 95% CI: 0.58- 0.79). For the transfer learning based approach, the highest AUC obtained was 0.53 (95% CI: 0.41-0.62). Conclusion: Convolutional neural networks could potentially be used to identify occult invasive disease in patients diagnosed with DCIS at the initial core needle biopsy.
Utilitarians Without Utilities: Maximizing Social Welfare for Graph Problems using only Ordinal Preferences - Full Version
Venue: arXiv cs.MA 2017
Year: 2017

We consider ordinal approximation algorithms for a broad class of utility maximization problems for multi-agent systems. In these problems, agents have utilities for connecting to each other, and the goal is to compute a maximum-utility solution subject to a set of constraints. We represent these as a class of graph optimization problems, including matching, spanning tree problems, TSP, maximum weight planar subgraph, and many others. We study these problems in the ordinal setting: latent numerical utilities exist, but we only have access to ordinal preference information, i.e., every agent specifies an ordering over the other agents by preference. We prove that for the large class of graph problems we identify, ordinal information is enough to compute solutions which are close to optimal, thus demonstrating there is no need to know the underlying numerical utilities. For example, for problems in this class with bounded degree $b$ a simple ordinal greedy algorithm always produces a ($b+1$)-approximation; we also quantify how the quality of ordinal approximation depends on the sparsity of the resulting graphs. In particular, our results imply that ordinal information is enough to obtain a 2-approximation for Maximum Spanning Tree; a 4-approximation for Max Weight Planar Subgraph; a 2-approximation for Max-TSP; and a 2-approximation for various Matching problems.
Optimal Dynamic Sensor Subset Selection for Tracking a Time-Varying Stochastic Process
Venue: arXiv cs.SY 2017
Year: 2017

Motivated by the Internet-of-things and sensor networks for cyberphysical systems, the problem of dynamic sensor activation for the tracking of a time-varying process is examined. The tradeoff is between energy efficiency, which decreases with the number of active sensors, and fidelity, which increases with the number of active sensors. The problem of minimizing the time-averaged mean-squared error over infinite horizon is examined under the constraint of the mean number of active sensors. The proposed methods artfully combine three key ingredients: Gibbs sampling, stochastic approximation for learning, and modifications to consensus algorithms to create a high performance, energy efficient tracking mechanisms with active sensor selection. The following progression of scenarios are considered: centralized tracking of an i.i.d. process; distributed tracking of an i.i.d. process and finally distributed tracking of a Markov chain. The challenge of the i.i.d. case is that the process has a distribution parameterized by a known or unknown parameter which must be learned. The key theoretical results prove that the proposed algorithms converge to local optima for the two i.i.d process cases; numerical results suggest that global optimality is in fact achieved. The proposed distributed tracking algorithm for a Markov chain, based on Kalman-consensus filtering and stochastic approximation, is seen to offer an error performance comparable to that of a competetive centralized Kalman filter.
Active Betweenness Cardinality: Algorithms and Applications
Venue: arXiv cs.SI 2017
Year: 2017

Centrality rankings such as degree, closeness, betweenness, Katz, PageRank, etc. are commonly used to identify critical nodes in a graph. These methods are based on two assumptions that restrict their wider applicability. First, they assume the exact topology of the network is available. Secondly, they do not take into account the activity over the network and only rely on its topology. However, in many applications, the network is autonomous, vast, and distributed, and it is hard to collect the exact topology. At the same time, the underlying pairwise activity between node pairs is not uniform and node criticality strongly depends on the activity on the underlying network. In this paper, we propose active betweenness cardinality, as a new measure, where the node criticalities are based on not the static structure, but the activity of the network. We show how this metric can be computed efficiently by using only local information for a given node and how we can find the most critical nodes starting from only a few nodes. We also show how this metric can be used to monitor a network and identify failed nodes.We present experimental results to show effectiveness by demonstrating how the failed nodes can be identified by measuring active betweenness cardinality of a few nodes in the system.
Symbolic vs. Bounded Synthesis for Petri Games
Venue: arXiv cs.LO 2017
Year: 2017

Petri games are a multiplayer game model for the automatic synthesis of distributed systems. We compare two fundamentally different approaches for solving Petri games. The symbolic approach decides the existence of a winning strategy via a reduction to a two-player game over a finite graph, which in turn is solved by a fixed point iteration based on binary decision diagrams (BDDs). The bounded synthesis approach encodes the existence of a winning strategy, up to a given bound on the size of the strategy, as a quantified Boolean formula (QBF). In this paper, we report on initial experience with a prototype implementation of the bounded synthesis approach. We compare bounded synthesis to the existing implementation of the symbolic approach in the synthesis tool ADAM. We present experimental results on a collection of benchmarks, including one new benchmark family, modeling manufacturing and workflow scenarios with multiple concurrent processes.
A Review on Cooperative Diversity Techniques Bypassing Channel Estimation
Venue: arXiv cs.IT 2017
Year: 2017

Wireless communication technology has seen a remarkably fast evolution due to its capability to provide a quality, reliable and high-speed data transmission amongst the users. However, transmission of information in wireless channels is primarily impaired by deleterious multipath fading, which affects the quality and reliability of the system. In order to overcome the detrimental effects of fading, Multiple-Input Multiple-Output (MIMO) technology is an attractive scheme that employs multiple transceiver antennas to carry the data over the same frequency band over a variety of signal paths. This technology has shown great solutions due to its ability to provide better spectral efficiency, capacity, throughput and robustness of the data transmission. But in practice, it is impractical to install multiple antennas on small-sized devices. Hence, to overcome the limitations of MIMO gain in the future wireless networks, cooperative diversity has recently draw in attention due to its ability to circumvent the difficulties of implementing actual antenna arrays in Multiple-Input and Multiple-Output (MIMO). By exploiting the broadcast feature of the wireless medium, cooperation among multiple nearby nodes is formed for data transmission. At the receiver, the signals are either coherently or differentially detected. Coherent detection requires exact channel estimation, which is difficult to apply in a time-varying channel. Hence, when the nodes are mobile, or when the channel is inaccurately estimated, the differential detection techniques that omit channel estimation become an alternative as compared to coherent detection. This article presents a review of the differential transmission techniques for cooperative diversity networks.
Cybersecurity Attacks in Vehicle-to-Infrastructure (V2I) Applications and their Prevention
Venue: arXiv cs.NI 2017
Year: 2017

A connected vehicle (CV) environment is composed of a diverse data collection, data communication and dissemination, and computing infrastructure systems that are vulnerable to the same cyberattacks as all traditional computing environments. Cyberattacks can jeopardize the expected safety, mobility, energy, and environmental benefits from connected vehicle applications. As cyberattacks can lead to severe traffic incidents, it has become one of the primary concerns in connected vehicle applications. In this paper, we investigate the impact of cyberattacks on the vehicle-to-infrastructure (V2I) network from a V2I application point of view. Then, we develop a novel V2I cybersecurity architecture, named CVGuard, which can detect and prevent cyberattacks on the V2I environment. In designing CVGuard, key challenges, such as scalability, resiliency and future usability were considered. A case study using a distributed denial of service (DDoS) on a V2I application, i.e., the Stop Sign Gap Assist (SSGA) application, shows that CVGuard was effective in mitigating the adverse effects created by a DDoS attack. In our case study, because of the DDoS attack, conflicts between the minor and major road vehicles occurred in an unsignalized intersection, which could have caused potential crashes. A reduction of conflicts between vehicles occurred because CVGuard was in operation. The reduction of conflicts was compared based on the number of conflicts before and after the implementation and operation of the CVGuard security platform. Analysis revealed that the strategies adopted by the CVGuard were successful in reducing the inter-vehicle conflicts by 60% where a DDoS attack compromised the SSGA application at an unsignalized intersection.
Load Forecasting Based Distribution System Network Reconfiguration-A Distributed Data-Driven Approach
Venue: arXiv cs.SY 2017
Year: 2017

In this paper, a short-term load forecasting approach based network reconfiguration is proposed in a parallel manner. Specifically, a support vector regression (SVR) based short-term load forecasting approach is designed to provide an accurate load prediction and benefit the network reconfiguration. Because of the nonconvexity of the three-phase balanced optimal power flow, a second-order cone program (SOCP) based approach is used to relax the optimal power flow problem. Then, the alternating direction method of multipliers (ADMM) is used to compute the optimal power flow in distributed manner. Considering the limited number of the switches and the increasing computation capability, the proposed network reconfiguration is solved in a parallel way. The numerical results demonstrate the feasible and effectiveness of the proposed approach.