OpenRaiser/Intern-Atlas huggingface dataset:
Algorithm-Hardware Co-Optimization of the Memristor-Based Framework for Solving SOCP and Homogeneous QCQP Problems
Venue: arXiv cs.ET 2018
Year: 2018

A memristor crossbar, which is constructed with memristor devices, has the unique ability to change and memorize the state of each of its memristor elements. It also has other highly desirable features such as high density, low power operation and excellent scalability. Hence the memristor crossbar technology can potentially be utilized for developing low-complexity and high-scalability solution frameworks for solving a large class of convex optimization problems, which involve extensive matrix operations and have critical applications in multiple disciplines. This paper, as the first attempt towards this direction, proposes a novel memristor crossbar-based framework for solving two important convex optimization problems, i.e., second-order cone programming (SOCP) and homogeneous quadratically constrained quadratic programming (QCQP) problems. In this paper, the alternating direction method of multipliers (ADMM) is adopted. It splits the SOCP and homogeneous QCQP problems into sub-problems that involve the solution of linear systems, which could be effectively solved using the memristor crossbar in O(1) time complexity. The proposed algorithm is an iterative procedure that iterates a constant number of times. Therefore, algorithms to solve SOCP and homogeneous QCQP problems have pseudo-O(N) complexity, which is a significant reduction compared to the state-of-the-art software solvers (O(N^3.5) - O(N^4)).
Study of SIC and RLS Channel Estimation for Large-Scale Antenna Systems with 1-Bit ADCs
Venue: arXiv cs.IT 2018
Year: 2018

We propose a novel low-resolution-aware recursive least squares channel estimation algorithm for uplink multi-user multiple-input multiple-output systems. In order to reduce the energy consumption, 1-bit ADCs are used on each receive antenna. The loss of performance can be recovered by the large-scale antenna arrays at the receiver. The proposed adaptive channel estimator can mitigate the distortions due to the coarse quantization. Moreover, we propose a low-resolution-aware minimum mean square error based successive interference canceler to successively mitigate the multiuser interference. Simulation results show good performance of the system in terms of mean square error and bit error rate.
Densely Connected Bidirectional LSTM with Applications to Sentence Classification
Venue: arXiv cs.CL 2018
Year: 2018

Deep neural networks have recently been shown to achieve highly competitive performance in many computer vision tasks due to their abilities of exploring in a much larger hypothesis space. However, since most deep architectures like stacked RNNs tend to suffer from the vanishing-gradient and overfitting problems, their effects are still understudied in many NLP tasks. Inspired by this, we propose a novel multi-layer RNN model called densely connected bidirectional long short-term memory (DC-Bi-LSTM) in this paper, which essentially represents each layer by the concatenation of its hidden state and all preceding layers' hidden states, followed by recursively passing each layer's representation to all subsequent layers. We evaluate our proposed model on five benchmark datasets of sentence classification. DC-Bi-LSTM with depth up to 20 can be successfully trained and obtain significant improvements over the traditional Bi-LSTM with the same or even less parameters. Moreover, our model has promising performance compared with the state-of-the-art approaches.
D2D Big Data: Content Deliveries over Wireless Device-to-Device Sharing in Large Scale Mobile Networks
Venue: arXiv cs.NI 2018
Year: 2018

Recently the topic of how to effectively offload cellular traffic onto device-to-device (D2D) sharing among users in proximity has been gaining more and more attention of global researchers and engineers. Users utilize wireless short-range D2D communications for sharing contents locally, due to not only the rapid sharing experience and free cost, but also high accuracy on deliveries of interesting and popular contents, as well as strong social impacts among friends. Nevertheless, the existing related studies are mostly confined to small-scale datasets, limited dimensions of user features, or unrealistic assumptions and hypotheses on user behaviors. In this article, driven by emerging Big Data techniques, we propose to design a big data platform, named D2D Big Data, in order to encourage the wireless D2D communications among users effectively, to promote contents for providers accurately, and to carry out offloading intelligence for operators efficiently. We deploy a big data platform and further utilize a large-scale dataset (3.56 TBytes) from a popular D2D sharing application (APP), which contains 866 million D2D sharing activities on 4.5 million files disseminated via nearly 850 million users in 13 weeks. By abstracting and analyzing multidimensional features, including online behaviors, content properties, location relations, structural characteristics, meeting dynamics, social arborescence, privacy preservation policies and so on, we verify and evaluate the D2D Big Data platform regarding predictive content propagating coverage. Finally, we discuss challenges and opportunities regarding D2D Big Data and propose to unveil a promising upcoming future of wireless D2D communications.
Path Planning for Minimizing the Expected Cost until Success
Venue: arXiv cs.RO 2018
Year: 2018

Consider a general path planning problem of a robot on a graph with edge costs, and where each node has a Boolean value of success or failure (with respect to some task) with a given probability. The objective is to plan a path for the robot on the graph that minimizes the expected cost until success. In this paper, it is our goal to bring a foundational understanding to this problem. We start by showing how this problem can be optimally solved by formulating it as an infinite horizon Markov Decision Process, but with an exponential space complexity. We then formally prove its NP-hardness. To address the space complexity, we then propose a path planner, using a game-theoretic framework, that asymptotically gets arbitrarily close to the optimal solution. Moreover, we also propose two fast and non-myopic path planners. To show the performance of our framework, we do extensive simulations for two scenarios: a rover on Mars searching for an object for scientific studies, and a robot looking for a connected spot to a remote station (with real data from downtown San Francisco). Our numerical results show a considerable performance improvement over existing state-of-the-art approaches.
Delay Analysis of Random Scheduling and Round Robin in Small Cell Networks
Venue: arXiv cs.IT 2018
Year: 2018

We analyze the delay performance of small cell networks operating under random scheduling (RS) and round robin (RR) protocols. Based on stochastic geometry and queuing theory, we derive accurate and tractable expressions for the distribution of mean delay, which accounts for the impact of random traffic arrivals, queuing interactions, and failed packet retransmissions. Our analysis asserts that RR outperforms RS in terms of mean delay, regardless of traffic statistic. Moreover, the gain from RR is more pronounced in the presence of heavy traffic, which confirms the importance of accounting fairness in the design of scheduling policy. We also find that constrained on the same delay outage probability, RR is able to support more user equipments (UEs) than that of RS, demonstrating it as an appropriate candidate for the traffic scheduling policy of internet-of-things (IoT) network.
Realizing Uncertainty-Aware Timing Stack in Embedded Operating System
Venue: arXiv cs.RO 2018
Year: 2018

Time awareness is critical to a broad range of emerging applications -- in Cyber-Physical Systems and Internet of Things -- running on commodity platforms and operating systems. Traditionally, time is synchronized across devices through a best-effort background service whose performance is neither observable nor controllable, thus consuming system resources independently of application needs while not allowing the applications and OS services to adapt to changes in uncertainty in system time. We advocate for rethinking how time is managed in a system stack. In this paper, we propose a new clock model that characterizes various sources of timing uncertainties in true time. We then present a Kalman filter based time synchronization protocol that adapts to the uncertainties exposed by the clock model. Our realization of a uncertainty-aware clock model and synchronization protocol is based on a standard embedded Linux platform.
On the Minimax Misclassification Ratio of Hypergraph Community Detection
Venue: arXiv cs.IT 2018
Year: 2018

Community detection in hypergraphs is explored. Under a generative hypergraph model called "d-wise hypergraph stochastic block model" (d-hSBM) which naturally extends the Stochastic Block Model from graphs to d-uniform hypergraphs, the asymptotic minimax mismatch ratio is characterized. For proving the achievability, we propose a two-step polynomial time algorithm that achieves the fundamental limit. The first step of the algorithm is a hypergraph spectral clustering method which achieves partial recovery to a certain precision level. The second step is a local refinement method which leverages the underlying probabilistic model along with parameter estimation from the outcome of the first step. To characterize the asymptotic performance of the proposed algorithm, we first derive a sufficient condition for attaining weak consistency in the hypergraph spectral clustering step. Then, under the guarantee of weak consistency in the first step, we upper bound the worst-case risk attained in the local refinement step by an exponentially decaying function of the size of the hypergraph and characterize the decaying rate. For proving the converse, the lower bound of the minimax mismatch ratio is set by finding a smaller parameter space which contains the most dominant error events, inspired by the analysis in the achievability part. It turns out that the minimax mismatch ratio decays exponentially fast to zero as the number of nodes tends to infinity, and the rate function is a weighted combination of several divergence terms, each of which is the Renyi divergence of order 1/2 between two Bernoulli's. The Bernoulli's involved in the characterization of the rate function are those governing the random instantiation of hyperedges in d-hSBM. Experimental results on synthetic data validate our theoretical finding that the refinement step is critical in achieving the optimal statistical limit.
Demand-driven Alias Analysis : Formalizing Bidirectional Analyses for Soundness and Precision
Venue: arXiv cs.PL 2018
Year: 2018

A demand-driven approach to program analysis have been viewed as efficient algorithms to compute only the information required to serve a target demand. In contrast, an exhaustive approach computes all information in anticipation of it being used later. However, for a given set of demands, demand-driven methods are believed to compute the same information that would be computed by the corresponding exhaustive methods. We investigate the precision and bidirectional nature of demand-driven methods and show that: (a) demand-driven methods can be formalized inherently as bidirectional data flow analysis because the demands are propagated against the control flow and the information to satisfy the demands is propagated along the control flow. We extend the formalization of the Meet Over Paths solution to bidirectional flows. This formalization helps us to prove the soundness and precision of our analysis, and (b) since a demand-driven method computes only the required information to meet a demand, it should be able to reduce the imprecision caused by data abstractions and hence should be more precise than an exhaustive method. We show that while this is indeed the case with Java, for C/C++, the precision critically hinges on how indirect assignments are handled. We use this insight and propose a demand-driven alias analysis that is more precise than an exhaustive analysis for C/C++ too. We have chosen devirtualization as an application. Our measurements show that our method is not only more efficient but more precise than the existing demand-driven method, as well as the corresponding exhaustive method.
Learning the Synthesizability of Dynamic Texture Samples
Venue: arXiv cs.CV 2018
Year: 2018

A dynamic texture (DT) refers to a sequence of images that exhibit temporal regularities and has many applications in computer vision and graphics. Given an exemplar of dynamic texture, it is a dynamic but challenging task to generate new samples with high quality that are perceptually similar to the input exemplar, which is known to be {\em example-based dynamic texture synthesis (EDTS)}. Numerous approaches have been devoted to this problem, in the past decades, but none them are able to tackle all kinds of dynamic textures equally well. In this paper, we investigate the synthesizability of dynamic texture samples: {\em given a dynamic texture sample, how synthesizable it is by using EDTS, and which EDTS method is the most suitable to synthesize it?} To this end, we propose to learn regression models to connect dynamic texture samples with synthesizability scores, with the help of a compiled dynamic texture dataset annotated in terms of synthesizability. More precisely, we first define the synthesizability of DT samples and characterize them by a set of spatiotemporal features. Based on these features and an annotated dynamic texture dataset, we then train regression models to predict the synthesizability scores of texture samples and learn classifiers to select the most suitable EDTS methods. We further complete the selection, partition and synthesizability prediction of dynamic texture samples in a hierarchical scheme. We finally apply the learned synthesizability to detecting synthesizable regions in videos. The experiments demonstrate that our method can effectively learn and predict the synthesizability of DT samples.
Content based Weighted Consensus Summarization
Venue: arXiv cs.IR 2018
Year: 2018

Multi-document summarization has received a great deal of attention in the past couple of decades. Several approaches have been proposed, many of which perform equally well and it is becoming in- creasingly difficult to choose one particular system over another. An ensemble of such systems that is able to leverage the strengths of each individual systems can build a better and more robust summary. Despite this, few attempts have been made in this direction. In this paper, we describe a category of ensemble systems which use consensus between the candidate systems to build a better meta-summary. We highlight two major shortcomings of such systems: the inability to take into account relative performance of individual systems and overlooking content of candidate summaries in favour of the sentence rankings. We propose an alternate method, content-based weighted consensus summarization, which address these concerns. We use pseudo-relevant summaries to estimate the performance of individual candidate systems, and then use this information to generate a better aggregate ranking. Experiments on DUC 2003 and DUC 2004 datasets show that the proposed system outperforms existing consensus-based techniques by a large margin.
Lyapunov Design for Event-Triggered Exponential Stabilization
Venue: arXiv cs.SY 2018
Year: 2018

Control Lyapunov Functions (CLF) method gives a constructive tool for stabilization of nonlinear systems. To find a CLF, many methods have been proposed in the literature, e.g. backstepping for cascaded systems and sum of squares (SOS) programming for polynomial systems. Dealing with continuous-time systems, the CLF-based controller is also continuous-time, whereas practical implementation on a digital platform requires sampled-time control. In this paper, we show that if the continuous-time controller provides exponential stabilization, then an exponentially stabilizing event-triggered control strategy exists with the convergence rate arbitrarily close to the rate of the continuous-time system.
HPC Curriculum and Associated Ressources in the Academic Context
Venue: arXiv cs.DC 2018
Year: 2018

Hardware support for high-performance computing (HPC) has so far been subject to significant advances. The pervasiveness of HPC systems, mainly made up with parallel computing units, makes it crucial to spread and vivify effective HPC curricula. Besides didactic considerations, it appears very important to implement HPC hardware infrastructures that will serves for practices, and also for scientific and industrial requests. The latter ensures a valuable connection with surrounding cutting-edge research activities in other topics ({\em life sciences, physics, data mining, applied mathematics, finance, quantitative economy, engineering sciences}, to name a few), and also with industrial entities and services providers from their requests related to HPC means and expertise. This aspect is very important as it makes an HPC Center becoming a social actor, while bringing real-life scenarios into the academic context. The current paper describes the major steps and objectives for a consistent HPC curriculum, with specific analyses of particular contexts; suggests how to technically set up operational HPC infrastructures; and discusses the connection with end-users, all these in both effective and prospective standpoints.
Privacy-Aware Smart Metering: Progress and Challenges
Venue: arXiv cs.IT 2018
Year: 2018

The next-generation energy network, the so-called smart grid (SG), promises a tremendous increase in efficiency, safety and flexibility of managing the electricity grid as compared to the legacy energy network. This is needed today more than ever, as the global energy consumption is growing at an unprecedented rate, and renewable energy sources have to be seamlessly integrated into the grid to assure a sustainable human development. Smart meters (SMs) are among the crucial enablers of the SG concept; they supply accurate high-frequency information about users' household energy consumption to a utility provider, which is essential for time of use pricing, rapid fault detection, energy theft prevention, while also providing consumers with more flexibility and control over their consumption. However, highly accurate and granular SM data also poses a threat to consumer privacy as non-intrusive load monitoring techniques enable a malicious attacker to infer many details of a user's private life. This article focuses on privacy-enhancing energy management techniques that provide accurate energy consumption information to the grid operator, without sacrificing consumer privacy. In particular, we focus on techniques that shape and modify the actual user energy consumption by means of physical resources, such as rechargeable batteries, renewable energy sources or demand shaping. A rigorous mathematical analysis of privacy is presented under various physical constraints on the available physical resources. Finally, open questions and challenges that need to be addressed to pave the way to the effective protection of users' privacy in future SGs are presented.
Industrial Symbiotic Relations as Cooperative Games
Venue: arXiv cs.MA 2018
Year: 2018

In this paper, we introduce a game-theoretical formulation for a specific form of collaborative industrial relations called "Industrial Symbiotic Relation (ISR) games" and provide a formal framework to model, verify, and support collaboration decisions in this new class of two-person operational games. ISR games are formalized as cooperative cost-allocation games with the aim to allocate the total ISR-related operational cost to involved industrial firms in a fair and stable manner by taking into account their contribution to the total traditional ISR-related cost. We tailor two types of allocation mechanisms using which firms can implement cost allocations that result in a collaboration that satisfies the fairness and stability properties. Moreover, while industries receive a particular ISR proposal, our introduced methodology is applicable as a managerial decision support to systematically verify the quality of the ISR in question. This is achievable by analyzing if the implemented allocation mechanism is a stable/fair allocation.
On Higher Inductive Types in Cubical Type Theory
Venue: arXiv cs.LO 2018
Year: 2018

Cubical type theory provides a constructive justification to certain aspects of homotopy type theory such as Voevodsky's univalence axiom. This makes many extensionality principles, like function and propositional extensionality, directly provable in the theory. This paper describes a constructive semantics, expressed in a presheaf topos with suitable structure inspired by cubical sets, of some higher inductive types. It also extends cubical type theory by a syntax for the higher inductive types of spheres, torus, suspensions,truncations, and pushouts. All of these types are justified by the semantics and have judgmental computation rules for all constructors, including the higher dimensional ones, and the universes are closed under these type formers.
Valuation of Crypto-Currency Mining Operations
Venue: arXiv cs.CY 2018
Year: 2018

Traditionally, the Net Present Value method is used to compare diverging investment strategies. However, valuating crypto-projects with fiat-based currency is confusing due to extreme coin appreciation rates as compared to fiat interest rates. Here, we provide a net present value method based on using crypto-coin as the underlying asset. Using this method, we compare HODL vs. mining, we also provide a sensitivity analysis of profitability
On-the-fly Detection of Autogenerated Tweets
Venue: arXiv cs.SI 2018
Year: 2018

Most previous work related to tweet classification have focused on identifying a given tweet as a spam, or to classify a Twitter user account as a spammer or a bot. In most cases the tweet classification has taken place offline, on a pre-collected dataset of tweets. In this paper we present an \emph{on-the-fly} approach to classify each newly downloaded tweet as \emph{autogenerated} or not. We define an autogenerated tweet (AGT) as a tweet where all or parts of the natural language content is generated automatically by a bot or other type of program. Our on-the-fly approach makes use of two classifiers. The first classifies a tweet solely based on the twitter text and the tweet metadata that comes with every tweet. It is used for tweets posted by unknown users with no available tweet history. An unknown user also triggers a batch job to start downloading the missing user timeline information. The second classifier is used for tweets posted by a user where the user timeline is downloaded and available. Initially, it will be the first classifier that handles most of the tweets. This will gradually change and after an initialization phase where we download historic data for the most active users, we reach a state where the second classifier handles a vast majority of all the tweets. A simulation using our on-the-fly detection mechanism indicates that we can handle Twitter streams with up to 68,000 unique users each day. The bottleneck is the time required to download new user timelines. The AGT detection is very accurate. In a set of 5,000 tweets we correctly classified about 98\% of all AGTs using a subject-wise cross-validation.