OpenRaiser/Intern-Atlas huggingface dataset:
A Novel Compressed Sensing Based Model for Reconstructing Sparse Signals Using Phase Sparse Character
Venue: arXiv cs.IT 2014
Year: 2014

Phase modulation is a commonly used modulation mode in digital communication, which usually brings phase sparsity to digital signals. It is naturally to connect the sparsity with the newly emerged theory of compressed sensing (CS), which enables sub-Nyquist sampling of high-bandwidth to sparse signals. For the present, applications of CS theory in communication field mainly focus on spectrum sensing, sparse channel estimation etc. Few of current researches take the phase sparse character into consideration. In this paper, we establish the novel model of phase modulation signals based on phase sparsity, and introduce CS theory to the phase domain. According to CS theory, rather than the bandwidth, the sampling rate required here is scaling with the symbol rate, which is usually much lower than the Nyquist rate. In this paper, we provide analytical support for the model, and simulations verify its validity.
Multipath Routing of Fragmented Data Transfer in a Smart Grid Environment
Venue: arXiv cs.CR 2014
Year: 2014

The purpose of this paper is to do a general survey on the existing communication modes inside a smart grid, the existing security loopholes and their countermeasures. Then we suggest a detailed countermeasure, building upon the Jigsaw based secure data transfer [8] for enhanced security of the data flow inside the communication system of a smart grid. The paper has been written without the consideration of any factor of inoperability between the various security techniques inside a smart grid
Sample NLPDE and NLODE Social-Media Modeling of Information Transmission for Infectious Diseases:Case Study Ebola
Venue: arXiv cs.SI 2014
Year: 2014

We investigate the spreading of information through Twitter messaging related to the spread of Ebola in western Africa using epidemic based dynamic models. Diffusive spreading leads to NLPDE models and fixed point analysis yields systems of NLODE models. When tweets are mapped as connected nodes in a graph and are treated as a time sequenced Markov chain, TSMC, then by the Kurtz theorem these specific paths can be identified as being near solutions to systems of ordinary differential equations that in the large N limit retain many of the features of the original Tweet dynamics. Constraints on the model related to Tweet and re-Tweet rates lead to different versions of the system of equations. We use Ebola Twitter meme based data to investigate a modified four parameter model and apply the resulting fit to an accuracy metric for a set of Ebola memes. In principle the temporal and spatial evolution equations describing the propagation of the Twitter based memes can help ascertain and inform decision makers on the nature of the spreading and containment of an epidemic of this type.
On the Complexity of Optimal Routing and Content Caching in Heterogeneous Networks
Venue: arXiv cs.NI 2014
Year: 2014

We investigate the problem of optimal request routing and content caching in a heterogeneous network supporting in-network content caching with the goal of minimizing average content access delay. Here, content can either be accessed directly from a back-end server (where content resides permanently) or be obtained from one of multiple in-network caches. To access a piece of content, a user must decide whether to route its request to a cache or to the back-end server. Additionally, caches must decide which content to cache. We investigate the problem complexity of two problem formulations, where the direct path to the back-end server is modeled as i) a congestion-sensitive or ii) a congestion-insensitive path, reflecting whether or not the delay of the uncached path to the back-end server depends on the user request load, respectively. We show that the problem is NP-complete in both cases. We prove that under the congestion-insensitive model the problem can be solved optimally in polynomial time if each piece of content is requested by only one user, or when there are at most two caches in the network. We also identify a structural property of the user-cache graph that potentially makes the problem NP-complete. For the congestion-sensitive model, we prove that the problem remains NP-complete even if there is only one cache in the network and each content is requested by only one user. We show that approximate solutions can be found for both models within a (1-1/e) factor of the optimal solution, and demonstrate a greedy algorithm that is found to be within 1% of optimal for small problem sizes. Through trace-driven simulations we evaluate the performance of our greedy algorithms, which show up to a 50% reduction in average delay over solutions based on LRU content caching.
A rapid algorithm to calculate joint probability matrices for joint entropies of arbitrary order
Venue: arXiv cs.IT 2014
Year: 2014

There is no closed form analytical equation or quick method to calculate probabilities based only on the entropy of a signal or process. Except in the cases where there are constraints on the state probabilities, one must typically derive the underlying probabilities through search algorithms. These become more computationally expensive as entropies of higher orders are investigated. In this paper, a method to calculate a joint probability matrix based on the entropy for any order is elaborated. With this method, only first order entropies need to be successfully calculated while the others are derived via multiplicative cascades.
TextLuas: Tracking and Visualizing Document and Term Clusters in Dynamic Text Data
Venue: arXiv cs.IR 2014
Year: 2014

For large volumes of text data collected over time, a key knowledge discovery task is identifying and tracking clusters. These clusters may correspond to emerging themes, popular topics, or breaking news stories in a corpus. Therefore, recently there has been increased interest in the problem of clustering dynamic data. However, there exists little support for the interactive exploration of the output of these analysis techniques, particularly in cases where researchers wish to simultaneously explore both the change in cluster structure over time and the change in the textual content associated with clusters. In this paper, we propose a model for tracking dynamic clusters characterized by the evolutionary events of each cluster. Motivated by this model, the TextLuas system provides an implementation for tracking these dynamic clusters and visualizing their evolution using a metro map metaphor. To provide overviews of cluster content, we adapt the tag cloud representation to the dynamic clustering scenario. We demonstrate the TextLuas system on two different text corpora, where they are shown to elucidate the evolution of key themes. We also describe how TextLuas was applied to a problem in bibliographic network research.
A Novel Model for Integration of Information Security Management against Replication Attack Based on Biological Structures of the Body
Venue: arXiv cs.CR 2014
Year: 2014

By developing communications and increase of access points, computer networks have been vulnerable considerably against wide range of information attacks, specially new and complicated attacks. Every day, replication attacks attack millions of network and mobile users. Increase in amount of replication attack may be a potential danger for income of SMS or network and causes losing customers of these services provider. Humans or software can be used to encounter these replication attacks. It is obvious that lonely absolute use of each method will not result in a proper answer to encounter replication attack`s problem. Since replication attack is one of the important problems of information protection and security in organizations for computer and mobile phone users, while reviewing types of replication attacks and methods of encountering, this paper uses similarities between pathologies in body and invader factors in replication attacks, a model is provided based on biological simulation methods existing in body`s adapted immune system to encounter these threats.
Applications of UWB Technology
Venue: arXiv cs.NI 2015
Year: 2015

Recent advances in wideband impulse technology, low power communication along with unlicensed band have enabled ultra wide band (UWB) as a leading technology for future wireless applications. This paper outlines the applications of emerging UWB technology in a private and commercial sector. We further talk about UWB technology for a wireless body area network (WBAN).
An Offline Technique for Localization of License Plates for Indian Commercial Vehicles
Venue: arXiv cs.CV 2015
Year: 2015

Automatic License Plate Recognition (ALPR) is a challenging area of research due to its importance to variety of commercial applications. The overall problem may be subdivided into two key modules, firstly, localization of license plates from vehicle images, and secondly, optical character recognition of extracted license plates. In the current work, we have concentrated on the first part of the problem, i.e., localization of license plate regions from Indian commercial vehicles as a significant step towards development of a complete ALPR system for Indian vehicles. The technique is based on color based segmentation of vehicle images and identification of potential license plate regions. True license plates are finally localized based on four spatial and horizontal contrast features. The technique successfully localizes the actual license plates in 73.4% images.
Truthful Mechanisms with Implicit Payment Computation
Venue: arXiv cs.GT 2015
Year: 2015

It is widely believed that computing payments needed to induce truthful bidding is somehow harder than simply computing the allocation. We show that the opposite is true: creating a randomized truthful mechanism is essentially as easy as a single call to a monotone allocation rule. Our main result is a general procedure to take a monotone allocation rule for a single-parameter domain and transform it (via a black-box reduction) into a randomized mechanism that is truthful in expectation and individually rational for every realization. The mechanism implements the same outcome as the original allocation rule with probability arbitrarily close to 1, and requires evaluating that allocation rule only once. We also provide an extension of this result to multi-parameter domains and cycle-monotone allocation rules, under mild star-convexity and non-negativity hypotheses on the type space and allocation rule, respectively. Because our reduction is simple, versatile, and general, it has many applications to mechanism design problems in which re-evaluating the allocation rule is either burdensome or informationally impossible. Applying our result to the multi-armed bandit problem, we obtain truthful randomized mechanisms whose regret matches the information-theoretic lower bound up to logarithmic factors, even though prior work showed this is impossible for truthful deterministic mechanisms. We also present applications to offline mechanism design, showing that randomization can circumvent a communication complexity lower bound for deterministic payments computation, and that it can also be used to create truthful shortest path auctions that approximate the welfare of the VCG allocation arbitrarily well, while having the same running time complexity as Dijkstra's algorithm.
Set-Monotonicity Implies Kelly-Strategyproofness
Venue: arXiv cs.MA 2015
Year: 2015

This paper studies the strategic manipulation of set-valued social choice functions according to Kelly's preference extension, which prescribes that one set of alternatives is preferred to another if and only if all elements of the former are preferred to all elements of the latter. It is shown that set-monotonicity---a new variant of Maskin-monotonicity---implies Kelly-strategyproofness in comprehensive subdomains of the linear domain. Interestingly, there are a handful of appealing Condorcet extensions---such as the top cycle, the minimal covering set, and the bipartisan set---that satisfy set-monotonicity even in the unrestricted linear domain, thereby answering questions raised independently by Barberà (1977) and Kelly (1977).
Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy
Venue: arXiv cs.CC 2015
Year: 2015

In this paper we prove lower bounds on randomized multiparty communication complexity, both in the \emph{blackboard model} (where each message is written on a blackboard for all players to see) and (mainly) in the \emph{message-passing model}, where messages are sent player-to-player. We introduce a new technique for proving such bounds, called \emph{symmetrization}, which is natural, intuitive, and often easy to use. For example, for the problem where each of $k$ players gets a bit-vector of length $n$, and the goal is to compute the coordinate-wise XOR of these vectors, we prove a tight lower bounds of $Ω(nk)$ in the blackboard model. For the same problem with AND instead of XOR, we prove a lower bounds of roughly $Ω(nk)$ in the message-passing model (assuming $k \le n/3200$) and $Ω(n \log k)$ in the blackboard model. We also prove lower bounds for bit-wise majority, for a graph-connectivity problem, and for other problems; the technique seems applicable to a wide range of other problems as well. All of our lower bounds allow randomized communication protocols with two-sided error. We also use the symmetrization technique to prove several direct-sum-like results for multiparty communication.
On strongly spanning $k$-edge-colorable subgraphs
Venue: arXiv cs.DM 2015
Year: 2015

A subgraph $H$ of a multigraph $G$ is called strongly spanning, if any vertex of $G$ is not isolated in $H$, while it is called maximum $k$-edge-colorable, if $H$ is proper $k$-edge-colorable and has the largest size. We introduce a graph-parameter $sp(G)$, that coincides with the smallest $k$ that a graph $G$ has a strongly spanning maximum $k$-edge-colorable subgraph. Our first result offers some alternative definitions of $sp(G)$. Next, we show that $Δ(G)$ is an upper bound for $sp(G)$, and then we characterize the class of graphs $G$ that satisfy $sp(G)=Δ(G)$. Finally, we prove some bounds for $sp(G)$ that involve well-known graph-theoretic parameters.
The set of solutions of random XORSAT formulae
Venue: arXiv cs.DM 2015
Year: 2015

The XOR-satisfiability (XORSAT) problem requires finding an assignment of $n$ Boolean variables that satisfy $m$ exclusive OR (XOR) clauses, whereby each clause constrains a subset of the variables. We consider random XORSAT instances, drawn uniformly at random from the ensemble of formulae containing $n$ variables and $m$ clauses of size $k$. This model presents several structural similarities to other ensembles of constraint satisfaction problems, such as $k$-satisfiability ($k$-SAT), hypergraph bicoloring and graph coloring. For many of these ensembles, as the number of constraints per variable grows, the set of solutions shatters into an exponential number of well-separated components. This phenomenon appears to be related to the difficulty of solving random instances of such problems. We prove a complete characterization of this clustering phase transition for random $k$-XORSAT. In particular, we prove that the clustering threshold is sharp and determine its exact location. We prove that the set of solutions has large conductance below this threshold and that each of the clusters has large conductance above the same threshold. Our proof constructs a very sparse basis for the set of solutions (or the subset within a cluster). This construction is intimately tied to the construction of specific subgraphs of the hypergraph associated with an instance of $k$-XORSAT. In order to study such subgraphs, we establish novel local weak convergence results for them.
Specifying and Staging Mixed-Initiative Dialogs with Program Generation and Transformation
Venue: arXiv cs.PL 2015
Year: 2015

Specifying and implementing flexible human-computer dialogs, such as those used in kiosks and smart phone apps, is challenging because of the numerous and varied directions in which each user might steer a dialog. The objective of this research is to improve dialog specification and implementation. To do so we enriched a notation based on concepts from programming languages, especially partial evaluation, for specifying a variety of unsolicited reporting, mixed-initiative dialogs in a concise representation that serves as a design for dialog implementation. We also built a dialog mining system that extracts a specification in this notation from requirements. To demonstrate that such a specification provides a design for dialog implementation, we built a system that automatically generates an implementation of the dialog, called a stager, from it. These two components constitute a dialog modeling toolkit that automates dialog specification and implementation. These results provide a proof of concept and demonstrate the study of dialog specification and implementation from a programming languages perspective. The ubiquity of dialogs in domains such as travel, education, and health care combined with the demand for smart phone apps provide a landscape for further investigation of these results.
The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme
Venue: arXiv cs.CC 2015
Year: 2015

The Traveling Salesman Problem (TSP) is among the most famous NP-hard optimization problems. We design for this problem a randomized polynomial-time algorithm that computes a (1+eps)-approximation to the optimal tour, for any fixed eps>0, in TSP instances that form an arbitrary metric space with bounded intrinsic dimension. The celebrated results of Arora (A-98) and Mitchell (M-99) prove that the above result holds in the special case of TSP in a fixed-dimensional Euclidean space. Thus, our algorithm demonstrates that the algorithmic tractability of metric TSP depends on the dimensionality of the space and not on its specific geometry. This result resolves a problem that has been open since the quasi-polynomial time algorithm of Talwar (T-04).
Consensus over Random Graph Processes: Network Borel-Cantelli Lemmas for Almost Sure Convergence
Venue: arXiv cs.DC 2015
Year: 2015

Distributed consensus computation over random graph processes is considered. The random graph process is defined as a sequence of random variables which take values from the set of all possible digraphs over the node set. At each time step, every node updates its state based on a Bernoulli trial, independent in time and among different nodes: either averaging among the neighbor set generated by the random graph, or sticking with its current state. Connectivity-independence and arc-independence are introduced to capture the fundamental influence of the random graphs on the consensus convergence. Necessary and/or sufficient conditions are presented on the success probabilities of the Bernoulli trials for the network to reach a global almost sure consensus, with some sharp threshold established revealing a consensus zero-one law. Convergence rates are established by lower and upper bounds of the $ε$-computation time. We also generalize the concepts of connectivity/arc independence to their analogues from the $*$-mixing point of view, so that our results apply to a very wide class of graphical models, including the majority of random graph models in the literature, e.g., Erdős-Rényi, gossiping, and Markovian random graphs. We show that under $*$-mixing, our convergence analysis continues to hold and the corresponding almost sure consensus conditions are established. Finally, we further investigate almost sure finite-time convergence of random gossiping algorithms, and prove that the Bernoulli trials play a key role in ensuring finite-time convergence. These results add to the understanding of the interplay between random graphs, random computations, and convergence probability for distributed information processing.
A new variational principle for the Euclidean distance function: Linear approach to the non-linear eikonal problem
Venue: arXiv cs.CV 2015
Year: 2015

We present a fast convolution-based technique for computing an approximate, signed Euclidean distance function $S$ on a set of 2D and 3D grid locations. Instead of solving the non-linear, static Hamilton-Jacobi equation ($\|\nabla S\|=1$), our solution stems from first solving for a scalar field $ϕ$ in a linear differential equation and then deriving the solution for $S$ by taking the negative logarithm. In other words, when $S$ and $ϕ$ are related by $ϕ= \exp \left(-\frac{S}τ \right)$ and $ϕ$ satisfies a specific linear differential equation corresponding to the extremum of a variational problem, we obtain the approximate Euclidean distance function $S = -τ\log(ϕ)$ which converges to the true solution in the limit as $τ\rightarrow 0$. This is in sharp contrast to techniques like the fast marching and fast sweeping methods which directly solve the Hamilton-Jacobi equation by the Godunov upwind discretization scheme. Our linear formulation results in a closed-form solution to the approximate Euclidean distance function expressible as a discrete convolution, and hence efficiently computable using the fast Fourier transform (FFT). Our solution also circumvents the need for spatial discretization of the derivative operator. As $τ\rightarrow0$ we show the convergence of our results to the true solution and also bound the error for a given value of $τ$. The differentiability of our solution allows us to compute---using a set of convolutions---the first and second derivatives of the approximate distance function. In order to determine the sign of the distance function (defined to be positive inside a closed region and negative outside), we compute the winding number in 2D and the topological degree in 3D, whose computations can also be performed via fast convolutions. We demonstrate the efficacy of our method through a set of experimental results.
The Locality of Distributed Symmetry Breaking
Venue: arXiv cs.DC 2015
Year: 2015

Symmetry breaking problems are among the most well studied in the field of distributed computing and yet the most fundamental questions about their complexity remain open. In this paper we work in the LOCAL model (where the input graph and underlying distributed network are identical) and study the randomized complexity of four fundamental symmetry breaking problems on graphs: computing MISs (maximal independent sets), maximal matchings, vertex colorings, and ruling sets. A small sample of our results includes - An MIS algorithm running in $O(\log^2Δ+ 2^{O(\sqrt{\log\log n})})$ time, where $Δ$ is the maximum degree. This is the first MIS algorithm to improve on the 1986 algorithms of Luby and Alon, Babai, and Itai, when $\log n \ll Δ\ll 2^{\sqrt{\log n}}$, and comes close to the $Ω(\log Δ)$ lower bound of Kuhn, Moscibroda, and Wattenhofer. - A maximal matching algorithm running in $O(\logΔ+ \log^4\log n)$ time. This is the first significant improvement to the 1986 algorithm of Israeli and Itai. Moreover, its dependence on $Δ$ is provably optimal. - A method for reducing symmetry breaking problems in low arboricity/degeneracy graphs to low degree graphs. (Roughly speaking, the arboricity or degeneracy of a graph bounds the density of any subgraph.) Corollaries of this reduction include an $O(\sqrt{\log n})$-time maximal matching algorithm for graphs with arboricity up to $2^{\sqrt{\log n}}$ and an $O(\log^{2/3} n)$-time MIS algorithm for graphs with arboricity up to $2^{(\log n)^{1/3}}$. Each of our algorithms is based on a simple, but powerful technique for reducing a randomized symmetry breaking task to a corresponding deterministic one on a poly$(\log n)$-size graph.