OpenRaiser/Intern-Atlas huggingface dataset:
Fast Recognition of Partial Star Products and Quasi Cartesian Products
Venue: arXiv cs.DM 2013
Year: 2013

This paper is concerned with the fast computation of a relation $\R$ on the edge set of connected graphs that plays a decisive role in the recognition of approximate Cartesian products, the weak reconstruction of Cartesian products, and the recognition of Cartesian graph bundles with a triangle free basis. A special case of $\R$ is the relation $δ^\ast$, whose convex closure yields the product relation $σ$ that induces the prime factor decomposition of connected graphs with respect to the Cartesian product. For the construction of $\R$ so-called Partial Star Products are of particular interest. Several special data structures are used that allow to compute Partial Star Products in constant time. These computations are tuned to the recognition of approximate graph products, but also lead to a linear time algorithm for the computation of $δ^\ast$ for graphs with maximum bounded degree. Furthermore, we define \emph{quasi Cartesian products} as graphs with non-trivial $δ^\ast$. We provide several examples, and show that quasi Cartesian products can be recognized in linear time for graphs with bounded maximum degree. Finally, we note that quasi products can be recognized in sublinear time with a parallelized algorithm.
Search Optimization for Minimum Load under Detection Performance Constraints in Multifunction Radars
Venue: arXiv cs.SY 2013
Year: 2013

This paper presents a solution procedure of search parameter optimization for minimum load ensuring desired one-off and cumulative probabilities of detection in a multifunction phased array radar. The key approach is to convert this nonlinear optimization on four search parameters into a scalar optimization on signal-to-noise ratio by a semi-analytic process based on subproblem decomposition. The efficacy of the proposed solution approach is verified with theoretical analysis and numerical case studies.
Recovery of Low-Rank Matrices under Affine Constraints via a Smoothed Rank Function
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, the problem of matrix rank minimization under affine constraints is addressed. The state-of-the-art algorithms can recover matrices with a rank much less than what is sufficient for the uniqueness of the solution of this optimization problem. We propose an algorithm based on a smooth approximation of the rank function, which practically improves recovery limits on the rank of the solution. This approximation leads to a non-convex program; thus, to avoid getting trapped in local solutions, we use the following scheme. Initially, a rough approximation of the rank function subject to the affine constraints is optimized. As the algorithm proceeds, finer approximations of the rank are optimized and the solver is initialized with the solution of the previous approximation until reaching the desired accuracy. On the theoretical side, benefiting from the spherical section property, we will show that the sequence of the solutions of the approximating function converges to the minimum rank solution. On the experimental side, it will be shown that the proposed algorithm, termed SRF standing for Smoothed Rank Function, can recover matrices which are unique solutions of the rank minimization problem and yet not recoverable by nuclear norm minimization. Furthermore, it will be demonstrated that, in completing partially observed matrices, the accuracy of SRF is considerably and consistently better than some famous algorithms when the number of revealed entries is close to the minimum number of parameters that uniquely represent a low-rank matrix.
Lossy Compression of Exponential and Laplacian Sources using Expansion Coding
Venue: arXiv cs.IT 2013
Year: 2013

A general method of source coding over expansion is proposed in this paper, which enables one to reduce the problem of compressing an analog (continuous-valued source) to a set of much simpler problems, compressing discrete sources. Specifically, the focus is on lossy compression of exponential and Laplacian sources, which is subsequently expanded using a finite alphabet prior to being quantized. Due to decomposability property of such sources, the resulting random variables post expansion are independent and discrete. Thus, each of the expanded levels corresponds to an independent discrete source coding problem, and the original problem is reduced to coding over these parallel sources with a total distortion constraint. Any feasible solution to the optimization problem is an achievable rate distortion pair of the original continuous-valued source compression problem. Although finding the solution to this optimization problem at every distortion is hard, we show that our expansion coding scheme presents a good solution in the low distrotion regime. Further, by adopting low-complexity codes designed for discrete source coding, the total coding complexity can be tractable in practice.
Signature-Based Gröbner Basis Algorithms --- Extended MMM Algorithm for computing Gröbner bases
Venue: arXiv cs.SC 2013
Year: 2013

Signature-based algorithms is a popular kind of algorithms for computing Gröbner bases, and many related papers have been published recently. In this paper, no new signature-based algorithms and no new proofs are presented. Instead, a view of signature-based algorithms is given, that is, signature-based algorithms can be regarded as an extended version of the famous MMM algorithm. By this view, this paper aims to give an easier way to understand signature-based Gröbner basis algorithms.
Throughput of One-Hop Wireless Networks with Noisy Feedback Channel
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we consider the effect of feedback channel error on the throughput of one-hop wireless networks under the random connection model. The transmission strategy is based on activating source-destination pairs with strongest direct links. While these activated pairs are identified based on Channel State Information (CSI) at the receive side, the transmit side will be provided with a noisy version of this information via the feedback channel. Such error will degrade network throughput, as we investigate in this paper. Our results show that if the feedback error probability is below a given threshold, network can tolerate such error without any significant throughput loss. The threshold value depends on the number of nodes in the network and the channel fading distribution. Such analysis is crucial in design of error correction codes for feedback channel in such networks.
An Efficient Transport Protocol for delivery of Multimedia An Efficient Transport Protocol for delivery of Multimedia Content in Wireless Grids
Venue: arXiv cs.MM 2013
Year: 2013

A grid computing system is designed for solving complicated scientific and commercial problems effectively,whereas mobile computing is a traditional distributed system having computing capability with mobility and adopting wireless communications. Media and Entertainment fields can take advantage from both paradigms by applying its usage in gaming applications and multimedia data management. Multimedia data has to be stored and retrieved in an efficient and effective manner to put it in use. In this paper, we proposed an application layer protocol for delivery of multimedia data in wireless girds i.e. multimedia grid protocol (MMGP). To make streaming efficient a new video compression algorithm called dWave is designed and embedded in the proposed protocol. This protocol will provide faster, reliable access and render an imperceptible QoS in delivering multimedia in wireless grid environment and tackles the challenging issues such as i) intermittent connectivity, ii) device heterogeneity, iii) weak security and iv) device mobility.
Bias of the SIR filter in estimation of the state transition noise
Venue: arXiv cs.SY 2013
Year: 2013

This Note investigates the bias of the sampling importance resampling (SIR) filter in estimation of the state transition noise in the state space model. The SIR filter may suffer from sample impoverishment that is caused by the resampling and therefore will benefit from a sampling proposal that has a heavier tail, e.g. the state transition noise simulated for particle preparation is bigger than the true noise involved with the state dynamics. This is because a comparably big transition noise used for particle propagation can spread overlapped particles to counteract impoverishment, giving better approximation of the posterior. As such, the SIR filter tends to yield a biased (bigger-than-the-truth) estimate of the transition noise if it is unknown and needs to be estimated, at least, in the forward-only filtering estimation. The bias is elaborated via the direct roughening approach by means of both qualitative logical deduction and quantitative numerical simulation.
Alpha current flow betweenness centrality
Venue: arXiv cs.SI 2013
Year: 2013

A class of centrality measures called betweenness centralities reflects degree of participation of edges or nodes in communication between different parts of the network. The original shortest-path betweenness centrality is based on counting shortest paths which go through a node or an edge. One of shortcomings of the shortest-path betweenness centrality is that it ignores the paths that might be one or two steps longer than the shortest paths, while the edges on such paths can be important for communication processes in the network. To rectify this shortcoming a current flow betweenness centrality has been proposed. Similarly to the shortest path betwe has prohibitive complexity for large size networks. In the present work we propose two regularizations of the current flow betweenness centrality, α-current flow betweenness and truncated α-current flow betweenness, which can be computed fast and correlate well with the original current flow betweenness.
KL-based Control of the Learning Schedule for Surrogate Black-Box Optimization
Venue: arXiv cs.LG 2013
Year: 2013

This paper investigates the control of an ML component within the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) devoted to black-box optimization. The known CMA-ES weakness is its sample complexity, the number of evaluations of the objective function needed to approximate the global optimum. This weakness is commonly addressed through surrogate optimization, learning an estimate of the objective function a.k.a. surrogate model, and replacing most evaluations of the true objective function with the (inexpensive) evaluation of the surrogate model. This paper presents a principled control of the learning schedule (when to relearn the surrogate model), based on the Kullback-Leibler divergence of the current search distribution and the training distribution of the former surrogate model. The experimental validation of the proposed approach shows significant performance gains on a comprehensive set of ill-conditioned benchmark problems, compared to the best state of the art including the quasi-Newton high-precision BFGS method.
A Static Malware Detection System Using Data Mining Methods
Venue: arXiv cs.CR 2013
Year: 2013

A serious threat today is malicious executables. It is designed to damage computer system and some of them spread over network without the knowledge of the owner using the system. Two approaches have been derived for it i.e. Signature Based Detection and Heuristic Based Detection. These approaches performed well against known malicious programs but cannot catch the new malicious programs. Different researchers have proposed methods using data mining and machine learning for detecting new malicious programs. The method based on data mining and machine learning has shown good results compared to other approaches. This work presents a static malware detection system using data mining techniques such as Information Gain, Principal component analysis, and three classifiers: SVM, J48, and Naïve Bayes. For overcoming the lack of usual anti-virus products, we use methods of static analysis to extract valuable features of Windows PE file. We extract raw features of Windows executables which are PE header information, DLLs, and API functions inside each DLL of Windows PE file. Thereafter, Information Gain, calling frequencies of the raw features are calculated to select valuable subset features, and then Principal Component Analysis is used for dimensionality reduction of the selected features. By adopting the concepts of machine learning and data-mining, we construct a static malware detection system which has a detection rate of 99.6%.
Completeness Results for Parameterized Space Classes
Venue: arXiv cs.CC 2013
Year: 2013

The parameterized complexity of a problem is considered "settled" once it has been shown to lie in FPT or to be complete for a class in the W-hierarchy or a similar parameterized hierarchy. Several natural parameterized problems have, however, resisted such a classification. At least in some cases, the reason is that upper and lower bounds for their parameterized space complexity have recently been obtained that rule out completeness results for parameterized time classes. In this paper, we make progress in this direction by proving that the associative generability problem and the longest common subsequence problem are complete for parameterized space classes. These classes are defined in terms of different forms of bounded nondeterminism and in terms of simultaneous time--space bounds. As a technical tool we introduce a "union operation" that translates between problems complete for classical complexity classes and for W-classes.
A Survey of Protocols for Intermittently Connected Delay-Tolerant Wireless Sensor Networks
Venue: arXiv cs.NI 2013
Year: 2013

Intermittently Connected Delay-Tolerant Wireless Sensor Networks (ICDT-WSNs), a branch of Wireless Sensor Networks (WSNs), have features of WSNs and the intermittent connectivity of Delay-Tolerant Networks (DTNs). The applications of ICDT-WSNs are increasing in recent years, however, the communication protocols suitable for this category of networks often fall short. Most of the existing communication protocols are designed for either WSNs or DTNs and tend to be inadequate for direct use in ICDT-WSNs. This survey summarizes characteristics of ICDT-WSNs and their communication protocol requirements, and examines the communication protocols designed for WSNs and DTNs in recent years from the perspective of ICDT-WSNs. Opportunities for future research in ICDT-WSNs are also outlined.
How and why communications industry suppliers get squeezed out: now, and the next phase
Venue: arXiv cs.CY 2013
Year: 2013

The communications systems, terminals, software and deployment service, industries, have undergone the past ten years a significant technological internal evolution and external revolution at customer end (such as Internet, Mobile networks and terminals, Broadband,..). Very little management research has studied their financial survivability irrespective of changes in demand volumes in the present technological /organizational cycle. This paper analyzes the implications of genuine open mandated communications standards, of higher product volumes, of very high R&D, of the larger use of sourced /purchased technologies, and of contract manufacturing. The methodology used is equilibrium analyses. Two specific areas will be mentioned as examples. The paper also shows how eventually those industries in a later cycle will bounce back.
Lexical State Analyzer
Venue: arXiv cs.FL 2013
Year: 2013

Lexical states provide a powerful mechanism to scan regular expressions in a context sensitive manner. At the same time, lexical states also make it hard to reason about the correctness of the grammar. We first categorize the related correctness issues into two classes: errors and warnings, and then present a context sensitive and a context insensitive analysis to identify errors and warnings in context-free-grammars (CFGs). We also present a comparative study of these analyses. A standalone tool (LSA) has also been implemented by us that can identify errors and warnings in JavaCC grammars. The LSA tool outputs a graph that depicts the grammar and the error transitions. It can also generates counter example strings that can be used to establish the errors. We have used LSA to analyze a host of open-source JavaCC grammar files to good effect.
Isometric embedding of Busemann surfaces into $L_1$
Venue: arXiv cs.CG 2013
Year: 2013

In this paper, we prove that any non-positively curved 2-dimensional surface (alias, Busemann surface) is isometrically embeddable into $L_1$. As a corollary, we obtain that all planar graphs which are 1-skeletons of planar non-positively curved complexes with regular Euclidean polygons as cells are $L_1$-embeddable with distortion at most $2+π/2<4$. Our results significantly improve and simplify the results of the recent paper {\it A. Sidiropoulos, Non-positive curvature, and the planar embedding conjecture, FOCS 2013.}}
An interactive engine for multilingual video browsing using semantic content
Venue: arXiv cs.MM 2013
Year: 2013

The amount of audio-visual information has increased dramatically with the advent of High Speed Internet. Furthermore, technological advances in recent years in the field of information technology, have simplified the use of video data in various fields by the general public. This made it possible to store large collections of video documents into computer systems. To enable efficient use of these collections, it is necessary to develop tools to facilitate access to these documents and handling them. In this paper we propose a method for indexing and retrieval of video sequences in a video database of large dimension, based on a weighting technique to calculate the degree of membership of a concept in a video also a structuring of the data of the audio-visual (context / concept / video) and a relevance feedback mechanism.
Anti-Coordination Games and Stable Graph Colorings
Venue: arXiv cs.GT 2013
Year: 2013

Motivated by understanding non-strict and strict pure strategy equilibria in network anti-coordination games, we define notions of stable and, respectively, strictly stable colorings in graphs. We characterize the cases when such colorings exist and when the decision problem is NP-hard. These correspond to finding pure strategy equilibria in the anti-coordination games, whose price of anarchy we also analyze. We further consider the directed case, a generalization that captures both coordination and anti-coordination. We prove the decision problem for non-strict equilibria in directed graphs is NP-hard. Our notions also have multiple connections to other combinatorial questions, and our results resolve some open problems in these areas, most notably the complexity of the strictly unfriendly partition problem.
A Secure and Comparable Text Encryption Algorithm
Venue: arXiv cs.CR 2013
Year: 2013

This paper discloses a simple algorithm for encrypting text messages, based on the NP-completeness of the subset sum problem, such that the similarity between encryptions is roughly proportional to the semantic similarity between their generating messages. This allows parties to compare encrypted messages for semantic overlap without trusting an intermediary and might be applied, for example, as a means of finding scientific collaborators over the Internet.
YY Filter - A Paradigm of Digital Signal Processing
Venue: arXiv cs.IT 2013
Year: 2013

YY filter, named after the founder Prof. Yutaka Yamamoto, is a digital filter designed by sampled-data control theory, which can optimize the analog performance of the signal processing system with AD/DA converters. This article discusses problems in conventional signal processing and introduces advantages of the YY filter.
E-Governance: Past, Present and Future in India
Venue: arXiv cs.CY 2013
Year: 2013

Due to widespread demand of E-governance and exponentially increasing size of data, new technologies like Open source solutions and cloud computing need to be incorporated. In this paper, the latest trends of technology that the government of most of the country has adopted have been discussed. While working on this project we have concluded that E-Governance has made the working of government more efficient and more transparent to its citizens We have also presented an exhaustive list of E-Governance projects which is currently being used in India and in international scenario. We have provided a mechanism for improving E-Governance by including technologies such as Open Source and Cloud Computing.
History Based Coalition Formation in Hedonic Context Using Trust
Venue: arXiv cs.MA 2013
Year: 2013

In this paper we address the problem of coalition formation in hedonic context. Our modelling tries to be as realistic as possible. In previous models, once an agent joins a coalition it would not be able to leave the coalition and join the new one; in this research we made it possible to leave a coalition but put some restrictions to control the behavior of agents. Leaving or staying of an agent in a coalition will affect on the trust of the other agents included in this coalition. Agents will use the trust values in computing the expected utility of coalitions. Three different risk behaviors are introduced for agents that want to initiate a coalition. Using these risk behaviors, some simulations are made and results are analyzed.
The Entity Registry System: Implementing 5-Star Linked Data Without the Web
Venue: arXiv cs.DB 2013
Year: 2013

Linked Data applications often assume that connectivity to data repositories and entity resolution services are always available. This may not be a valid assumption in many cases. Indeed, there are about 4.5 billion people in the world who have no or limited Web access. Many data-driven applications may have a critical impact on the life of those people, but are inaccessible to those populations due to the architecture of today's data registries. In this paper, we propose and evaluate a new open-source system that can be used as a general-purpose entity registry suitable for deployment in poorly-connected or ad-hoc environments.
Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation
Venue: arXiv cs.LG 2013
Year: 2013

Stochastic neurons and hard non-linearities can be useful for a number of reasons in deep learning models, but in many cases they pose a challenging problem: how to estimate the gradient of a loss function with respect to the input of such stochastic or non-smooth neurons? I.e., can we "back-propagate" through these stochastic neurons? We examine this question, existing approaches, and compare four families of solutions, applicable in different settings. One of them is the minimum variance unbiased gradient estimator for stochatic binary neurons (a special case of the REINFORCE algorithm). A second approach, introduced here, decomposes the operation of a binary stochastic neuron into a stochastic binary part and a smooth differentiable part, which approximates the expected effect of the pure stochatic binary neuron to first order. A third approach involves the injection of additive or multiplicative noise in a computational graph that is otherwise differentiable. A fourth approach heuristically copies the gradient with respect to the stochastic output directly as an estimator of the gradient with respect to the sigmoid argument (we call this the straight-through estimator). To explore a context where these estimators are useful, we consider a small-scale version of {\em conditional computation}, where sparse stochastic units form a distributed representation of gaters that can turn off in combinatorially many ways large chunks of the computation performed in the rest of the neural network. In this case, it is important that the gating units produce an actual 0 most of the time. The resulting sparsity can be potentially be exploited to greatly reduce the computational cost of large deep networks for which conditional computation would be useful.