OpenRaiser/Intern-Atlas huggingface dataset:
MIMO with Energy Recycling
Venue: arXiv cs.IT 2018
Year: 2018

We consider a Multiple Input Single Output (MISO) point-to-point communication system in which the transmitter is designed such that, each antenna can transmit information or harvest energy at any given point in time. We evaluate the achievable rate by such an energy-recycling MISO system under an average transmission power constraint. Our achievable scheme carefully switches the mode of the antennas between transmission and wireless harvesting, where most of the harvesting happens from the neighboring antennas' transmissions, i.e., recycling. We show that, with recycling, it is possible to exceed the capacity of the classical non-harvesting counterpart. As the complexity of the achievable algorithm is exponential with the number of antennas, we also provide an almost linear algorithm that has a minimal degradation in achievable rate. To address the major questions on the capability of recycling and the impacts of antenna coupling, we also develop a hardware setup and experimental results for a 4-antenna transmitter, based on a uniform linear array (ULA). We demonstrate that the loss in the rate due to antenna coupling can be made negligible with sufficient antenna spacing and provide hardware measurements for the power recycled from the transmitting antennas and the power received at the target receiver, taken simultaneously. We provide refined performance measurement results, based on our actual measurements.
Listening to the cohomology of graphs
Venue: arXiv cs.DM 2018
Year: 2018

We prove that the spectrum of the Kirchhoff Laplacian H0 of a finite simple Barycentric refined graph and the spectrum of the connection Laplacian L of G determine each other: we prove that L-L^(-1) is similar to the Hodge Laplacian H of G which is in one dimensions the direct sum of the Kirchhoff Laplacian H0 and its 1-form analog H1. The spectrum of a single choice of H0,H1 or H alone determines the Betti numbers b0,b1 of G as well as the spectrum of the other matrices. It follows that b0 is the number of eigenvalues 1 of L and that b1 is the number of eigenvalues -1 of L. For a general abstract finite simplicial complex G, we express the matrix entries g(x,y) = w(x) w(y) X( St(x) cap St(y) ) of the inverse of L using stars St(x)= { z in G | x subset of z } of x and w(x)=(-1)^dim(x) and Euler characteristic X. One can see W+(x)=St(x) and W-(x)={ z in G | z subset x } as stable and unstable manifolds of a simplex x in G and g(x,y) =w(x) w(y) X(W+(x) cap W+(y)) as heteroclinic intersection numbers or curvatures and the identity L g=1 as a collection of Gauss-Bonnet formulas. The homoclinic energy w(x)=X(W+(x) cap W-(x)) by definition adds up to X(G). The matrix M(x,y)=w(x) w(y) X(W-(x) cap W-(y)) is similar to L(x,y)=X(W-(x) cap W-(y)). The sum of the matrix entries of M is the definition of Wu characteristic. For dimension 2 and higher we don't know yet how to recover the Betti numbers from the eigenvalues of the matrix H or from L. So far, it can only be obtained from a collection of block matrices, via the Hodge relations b_k = dim(H_k). A natural conjecture is that for a Barycentric refinement of a complex G, the spectrum of L determines the Betti vector. We know this now in one dimensions.
Fast Approximations for Metric-TSP via Linear Programming
Venue: arXiv cs.DS 2018
Year: 2018

We develop faster approximation algorithms for Metric-TSP building on recent, nearly linear time approximation schemes for the LP relaxation [Chekuri and Quanrud, 2017]. We show that the LP solution can be sparsified via cut-sparsification techniques such as those of Benczur and Karger [2015]. Given a weighted graph $G$ with $m$ edges and $n$ vertices, and $ε> 0$, our randomized algorithm outputs with high probability a $(1+ε)$-approximate solution to the LP relaxation whose support has $\operatorname{O}(n \log n /ε^2)$ edges. The running time of the algorithm is $\operatorname{Õ}(m/ε^2)$. This can be generically used to speed up algorithms that rely on the LP. For Metric-TSP, we obtain the following concrete result. For a weighted graph $G$ with $m$ edges and $n$ vertices, and $ε> 0$, we describe an algorithm that outputs with high probability a tour of $G$ with cost at most $(1 + ε) \frac{3}{2}$ times the minimum cost tour of $G$ in time $\operatorname{Õ}(m/ε^2 + n^{1.5}/ε^3)$. Previous implementations of Christofides' algorithm [Christofides, 1976] require, for a $\frac{3}{2}$-optimal tour, $\operatorname{Õ}(n^{2.5})$ time when the metric is explicitly given, or $\operatorname{Õ}(\min\{m^{1.5}, mn+n^{2.5}\})$ time when the metric is given implicitly as the shortest path metric of a weighted graph.
Data Augmentation of Railway Images for Track Inspection
Venue: arXiv cs.CV 2018
Year: 2018

Regular maintenance of all the assets is pivotal for proper functioning of railway. Manual maintenance can be very cumbersome and leave room for errors. Track anomalies like vegetation overgrowth, sun kinks affect the track construct and result in unequal load transfer, imbalanced lateral forces on tracks which causes further deterioration of tracks and can ultimately result in derailment of locomotive. Hence there is a need to continuously monitor rail track health. Track anomalies are rare with the skew as high as one anomaly in millions of good images. We propose a method to build training data that will make our algorithms more robust and help us detect real world track issues. The data augmentation will have a direct effect in making us detect better anomalies and hence improve time for railroads that is spent in manual inspection. This paper talks about a real world use case of detecting railway track defects from a camera mounted on a moving locomotive and tracking their locations. The camera is engineered to withstand the environment factors on a moving train and provide a consistent steady image at around 30 frames per second. An image simulation pipeline of track detection, region of interest selection, augmenting image for anomalies is implemented. Training images are simulated for sun kink and vegetation overgrowth. Inception V3 model pretrained on Imagenet dataset is finetuned for a 2 class classification. For the case of vegetation overgrowth, the model generalizes well on actual vegetation images, though it was trained and validated solely on simulated images which might have different distribution than the actual vegetation. Sun kink classifier can classify professionally simulated sun kink videos with a precision of 97.5%.
Polarization and Fake News: Early Warning of Potential Misinformation Targets
Venue: arXiv cs.SI 2018
Year: 2018

Users polarization and confirmation bias play a key role in misinformation spreading on online social media. Our aim is to use this information to determine in advance potential targets for hoaxes and fake news. In this paper, we introduce a general framework for promptly identifying polarizing content on social media and, thus, "predicting" future fake news topics. We validate the performances of the proposed methodology on a massive Italian Facebook dataset, showing that we are able to identify topics that are susceptible to misinformation with 77% accuracy. Moreover, such information may be embedded as a new feature in an additional classifier able to recognize fake news with 91% accuracy. The novelty of our approach consists in taking into account a series of characteristics related to users behavior on online social media, making a first, important step towards the smoothing of polarization and the mitigation of misinformation phenomena.
Big Data Analytics for Wireless and Wired Network Design: A Survey
Venue: arXiv cs.NI 2018
Year: 2018

Currently, the world is witnessing a mounting avalanche of data due to the increasing number of mobile network subscribers, Internet websites, and online services. This trend is continuing to develop in a quick and diverse manner in the form of big data. Big data analytics can process large amounts of raw data and extract useful, smaller-sized information, which can be used by different parties to make reliable decisions. In this paper, we conduct a survey on the role that big data analytics can play in the design of data communication networks. Integrating the latest advances that employ big data analytics with the networks control/traffic layers might be the best way to build robust data communication networks with refined performance and intelligent features. First, the survey starts with the introduction of the big data basic concepts, framework, and characteristics. Second, we illustrate the main network design cycle employing big data analytics. This cycle represents the umbrella concept that unifies the surveyed topics. Third, there is a detailed review of the current academic and industrial efforts toward network design using big data analytics. Forth, we identify the challenges confronting the utilization of big data analytics in network design. Finally, we highlight several future research directions. To the best of our knowledge, this is the first survey that addresses the use of big data analytics techniques for the design of a broad range of networks.
Can Common Crawl reliably track persistent identifier (PID) use over time?
Venue: arXiv cs.DL 2018
Year: 2018

We report here on the results of two studies using two and four monthly web crawls respectively from the Common Crawl (CC) initiative between 2014 and 2017, whose initial goal was to provide empirical evidence for the changing patterns of use of so-called persistent identifiers. This paper focusses on the tooling needed for dealing with CC data, and the problems we found with it. The first study is based on over $10^{12}$ URIs from over $5 * 10^9$ pages crawled in April 2014 and April 2017, the second study adds a further $3 * 10^9$ pages from the April 2015 and April 2016 crawls. We conclude with suggestions on specific actions needed to enable studies based on CC to give reliable longitudinal information.
Road Segmentation in SAR Satellite Images with Deep Fully-Convolutional Neural Networks
Venue: arXiv cs.CV 2018
Year: 2018

Remote sensing is extensively used in cartography. As transportation networks grow and change, extracting roads automatically from satellite images is crucial to keep maps up-to-date. Synthetic Aperture Radar satellites can provide high resolution topographical maps. However roads are difficult to identify in these data as they look visually similar to targets such as rivers and railways. Most road extraction methods on Synthetic Aperture Radar images still rely on a prior segmentation performed by classical computer vision algorithms. Few works study the potential of deep learning techniques, despite their successful applications to optical imagery. This letter presents an evaluation of Fully-Convolutional Neural Networks for road segmentation in SAR images. We study the relative performance of early and state-of-the-art networks after carefully enhancing their sensitivity towards thin objects by adding spatial tolerance rules. Our models shows promising results, successfully extracting most of the roads in our test dataset. This shows that, although Fully-Convolutional Neural Networks natively lack efficiency for road segmentation, they are capable of good results if properly tuned. As the segmentation quality does not scale well with the increasing depth of the networks, the design of specialized architectures for roads extraction should yield better performances.
Hardening Deep Neural Networks via Adversarial Model Cascades
Venue: arXiv cs.LG 2018
Year: 2018

Deep neural networks (DNNs) are vulnerable to malicious inputs crafted by an adversary to produce erroneous outputs. Works on securing neural networks against adversarial examples achieve high empirical robustness on simple datasets such as MNIST. However, these techniques are inadequate when empirically tested on complex data sets such as CIFAR-10 and SVHN. Further, existing techniques are designed to target specific attacks and fail to generalize across attacks. We propose the Adversarial Model Cascades (AMC) as a way to tackle the above inadequacies. Our approach trains a cascade of models sequentially where each model is optimized to be robust towards a mixture of multiple attacks. Ultimately, it yields a single model which is secure against a wide range of attacks; namely FGSM, Elastic, Virtual Adversarial Perturbations and Madry. On an average, AMC increases the model's empirical robustness against various attacks simultaneously, by a significant margin (of 6.225% for MNIST, 5.075% for SVHN and 2.65% for CIFAR10). At the same time, the model's performance on non-adversarial inputs is comparable to the state-of-the-art models.
Reducing CMSO Model Checking to Highly Connected Graphs
Venue: arXiv cs.DS 2018
Year: 2018

Given a Counting Monadic Second Order (CMSO) sentence $ψ$, the CMSO$[ψ]$ problem is defined as follows. The input to CMSO$[ψ]$ is a graph $G$, and the objective is to determine whether $G\models ψ$. Our main theorem states that for every CMSO sentence $ψ$, if CMSO$[ψ]$ is solvable in polynomial time on "globally highly connected graphs", then CMSO$[ψ]$ is solvable in polynomial time (on general graphs). We demonstrate the utility of our theorem in the design of parameterized algorithms. Specifically we show that technical problem-specific ingredients of a powerful method for designing parameterized algorithms, recursive understanding, can be replaced by a black-box invocation of our main theorem. We also show that our theorem can be easily deployed to show fixed parameterized tractability of a wide range of problems, where the input is a graph $G$ and the task is to find a connected induced subgraph of $G$ such that "few" vertices in this subgraph have neighbors outside the subgraph, and additionally the subgraph has a CMSO-definable property.
PinMe: Tracking a Smartphone User around the World
Venue: arXiv cs.CR 2018
Year: 2018

With the pervasive use of smartphones that sense, collect, and process valuable information about the environment, ensuring location privacy has become one of the most important concerns in the modern age. A few recent research studies discuss the feasibility of processing data gathered by a smartphone to locate the phone's owner, even when the user does not intend to share his location information, e.g., when the Global Positioning System (GPS) is off. Previous research efforts rely on at least one of the two following fundamental requirements, which significantly limit the ability of the adversary: (i) the attacker must accurately know either the user's initial location or the set of routes through which the user travels and/or (ii) the attacker must measure a set of features, e.g., the device's acceleration, for potential routes in advance and construct a training dataset. In this paper, we demonstrate that neither of the above-mentioned requirements is essential for compromising the user's location privacy. We describe PinMe, a novel user-location mechanism that exploits non-sensory/sensory data stored on the smartphone, e.g., the environment's air pressure, along with publicly-available auxiliary information, e.g., elevation maps, to estimate the user's location when all location services, e.g., GPS, are turned off.
Robust Vertex Enumeration for Convex Hulls in High Dimensions
Venue: arXiv cs.CG 2018
Year: 2018

Computation of the vertices of the convex hull of a set $S$ of $n$ points in $\mathbb{R} ^m$ is a fundamental problem in computational geometry, optimization, machine learning and more. We present "All Vertex Triangle Algorithm" (AVTA), a robust and efficient algorithm for computing the subset $\overline S$ of all $K$ vertices of $conv(S)$, the convex hull of $S$. If $Γ_*$ is the minimum of the distances from each vertex to the convex hull of the remaining vertices, given any $γ\leq γ_* = Γ_*/R$, $R$ the diameter of $S$, $AVTA$ computes $\overline S$ in $O(nK(m+ γ^{-2}))$ operations. If $γ_*$ is unknown but $K$ is known, AVTA computes $\overline S$ in $O(nK(m+ γ_*^{-2})) \log(γ_*^{-1})$ operations. More generally, given $t \in (0,1)$, AVTA computes a subset $\overline S^t$ of $\overline S$ in $O(n |\overline S^t|(m+ t^{-2}))$ operations, where the distance between any $p \in conv(S)$ to $conv(\overline S^t)$ is at most $t R$. Next we consider AVTA where input is $S_\varepsilon$, an $\varepsilon$ perturbation of $S$. Assuming a bound on $\varepsilon$ in terms of the minimum of the distances of vertices of $conv(S)$ to the convex hull of the remaining point of $S$, we derive analogous complexity bounds for computing $\overline S_\varepsilon$. We also analyze AVTA under random projections of $S$ or $S_\varepsilon$. Finally, via AVTA we design new practical algorithms for two popular machine learning problems: topic modeling and non-negative matrix factorization. For topic models AVTA leads to significantly better reconstruction of the topic-word matrix than state of the art approaches~\cite{arora2013practical, bansal2014provable}. For non-negative matrix AVTA is competitive with existing methods~\cite{arora2012computing}. Empirically AVTA is robust and can handle larger amounts of noise than existing methods.
Un-unzippable Convex Caps
Venue: arXiv cs.CG 2018
Year: 2018

An unzipping of a polyhedron P is a cut-path through its vertices that unfolds P to a non-overlapping shape in the plane. It is an open problem to decide if every convex P has an unzipping. Here we show that there are nearly flat convex caps that have no unzipping. A convex cap is a "top" portion of a convex polyhedron; it has a boundary, i.e., it is not closed by a base.
Do You Want Your Autonomous Car To Drive Like You?
Venue: arXiv cs.RO 2018
Year: 2018

With progress in enabling autonomous cars to drive safely on the road, it is time to start asking how they should be driving. A common answer is that they should be adopting their users' driving style. This makes the assumption that users want their autonomous cars to drive like they drive - aggressive drivers want aggressive cars, defensive drivers want defensive cars. In this paper, we put that assumption to the test. We find that users tend to prefer a significantly more defensive driving style than their own. Interestingly, they prefer the style they think is their own, even though their actual driving style tends to be more aggressive. We also find that preferences do depend on the specific driving scenario, opening the door for new ways of learning driving style preference.
Spot that Bird: A Location Based Bird Game
Venue: arXiv cs.HC 2018
Year: 2018

In today's age of pervasive computing and social media people make extensive use of technology for communicating, sharing media and learning. Yet while in the outdoors, on a hike or a trail we find ourselves inept of information about the natural world surrounding us. In this paper I present in detail the design and technological considerations required to build a location based mobile application for learning about the avian taxonomy present in the user's surroundings. It is designed to be a game for better engagement and learning. The application makes suggestions for birds likely to be sighted in the vicinity of the user and requires the user to spot those birds and upload a photograph to the system. If spotted correctly the user scores points. I also discuss some design methods and evaluation approaches for the application.
Simultaneous Optimization of Signal Timing and Capacity Improvement in Urban Transportation Networks Using Simulated Annealing
Venue: arXiv cs.SY 2018
Year: 2018

Capacity expansions as well as its reduction have been widely anticipated as important countermeasures for traffic congestion. Although capacity expansion had been traditionally well noticed as a congestion mitigation measure, but it was not until recently that capacity reduction measures such as; congestion pricing, road diet and other such capacity reduction measures were noticed as congestion mitigation measures. Measures such as signal optimization, metering and congestion pricing are intended to affect the travel pattern and assignment behavior of travelers to make the results of the User Equilibrium (UE) traffic assignment, followed by the travelers, closer to the System Optimal (SO) outcomes, intended by the planners. As such, a bi-level optimization model was formulated for the simultaneous optimization of capacity improvement/expansion and signal timing in an urban transportation network. The model takes into account both the effect of higher demand, induced by the capacity expansion, and the rerouting potential effect of traffic signals. The solution algorithm developed here consists of two major components; the gradient projection algorithm (GP) to solve the lower level traffic assignment problem and the Simulated Annealing (SA) algorithm to solve the master problem. In order to illustrate the method a case study was examined. The analysis and application of the proposed algorithm shows that the performance function gradually converged along the simulation run, and no divergence problem is observed. By applying the developed algorithm, the total network travel time reduced by 13.42%, in which 5.76% is reached by only optimizing the signal times. Using the GP algorithm and taking advantages of dynamic memory in the process of simulation, the whole simulation acquired from computer time is 13.63 seconds with a convergence rate of 0.001.
Cross-Layer Authentication Protocol Design for Ultra-Dense 5G HetNets
Venue: arXiv cs.CR 2018
Year: 2018

Creating a secure environment for communications is becoming a significantly challenging task in 5G Heterogeneous Networks (HetNets) given the stringent latency and high capacity requirements of 5G networks. This is particularly factual knowing that the infrastructure tends to be highly diversified especially with the continuous deployment of small cells. In fact, frequent handovers in these cells introduce unnecessarily recurring authentications leading to increased latency. In this paper, we propose a software-defined wireless network (SDWN)-enabled fast cross-authentication scheme which combines non-cryptographic and cryptographic algorithms to address the challenges of latency and weak security. Initially, the received radio signal strength vectors at the mobile terminal (MT) is used as a fingerprinting source to generate an unpredictable secret key. Subsequently, a cryptographic mechanism based upon the authentication and key agreement protocol by employing the generated secret key is performed in order to improve the confidentiality and integrity of the authentication handover. Further, we propose a radio trusted zone database aiming to enhance the frequent authentication of radio devices which are present in the network. In order to reduce recurring authentications, a given covered area is divided into trusted zones where each zone contains more than one small cell, thus permitting the MT to initiate a single authentication request per zone, even if it keeps roaming between different cells. The proposed scheme is analyzed under different attack scenarios and its complexity is compared with cryptographic and non-cryptographic approaches to demonstrate its security resilience and computational efficiency.