OpenRaiser/Intern-Atlas huggingface dataset:
Checking generalized debates with small space and randomness
Venue: arXiv cs.CC 2012
Year: 2012

We introduce a model of probabilistic debate checking, where a silent resource-bounded verifier reads a dialogue about the membership of the string in the language under consideration between a prover and a refuter. Our model combines and generalizes the concepts of one-way interactive proof systems, games of incomplete information, and probabilistically checkable complete-information debate systems. We consider debates of partial and zero information, where the prover is prevented from seeing some or all of the messages of the refuter, as well as those of complete information. The classes of languages with debates checkable by verifiers operating under severe bounds on the memory and randomness are studied. We give full characterizations of versions of these classes corresponding to simultaneous bounds of O(1) space and O(1) random bits, and of logarithmic space and polynomial time. It turns out that constant-space verifiers, which can only check complete-information debates for regular languages deterministically, can check for membership in any language in P when allowed to use a constant number of random bits. Similar increases also occur for zero- and partial- information debates, from NSPACE(n) to PSPACE, and from E to EXPTIME, respectively. Adding logarithmic space to these constant-randomness verifiers does not change their power. When logspace debate checkers are restricted to run in polynomial time without a bound on the number of random bits, the class of debatable languages equals PSPACE for all debate types. We also present a result on the hardness of approximating the quantified max word problem for matrices that is a corollary of this characterization.
On the capacity limit of wireless channels under colored scattering
Venue: arXiv cs.IT 2012
Year: 2012

It has been generally believed that the multiple-input multiple-output (MIMO) channel capacity grows linearly with the size of antenna arrays. In terms of degrees of freedom, linear transmit and receive arrays of length $L$ in a scattering environment of total angular spread $|Ω|$ asymptotically have $|Ω| L$ degrees of freedom. In this paper, it is claimed that the linear increase in degrees of freedom may not be attained when scattered electromagnetic fields in the underlying scattering environment are statistically correlated. After introducing a model of correlated scattering, which is referred to as the colored scattering model, we derive the number of degrees of freedom. Unlike the uncorrelated case, the number of degrees of freedom in the colored scattering channel is asymptotically limited by $|Ω| \cdot \min \{L, 1/Γ}$, where $Γ$ is a parameter determining the extent of correlation. In other words, for very large arrays in the colored scattering environment, degrees of freedom can get saturated to an intrinsic limit rather than increasing linearly with the array size.
Parameterized Study of the Test Cover Problem
Venue: arXiv cs.DS 2012
Year: 2012

We carry out a systematic study of a natural covering problem, used for identification across several areas, in the realm of parameterized complexity. In the {\sc Test Cover} problem we are given a set $[n]=\{1,...,n\}$ of items together with a collection, $\cal T$, of distinct subsets of these items called tests. We assume that $\cal T$ is a test cover, i.e., for each pair of items there is a test in $\cal T$ containing exactly one of these items. The objective is to find a minimum size subcollection of $\cal T$, which is still a test cover. The generic parameterized version of {\sc Test Cover} is denoted by $p(k,n,|{\cal T}|)$-{\sc Test Cover}. Here, we are given $([n],\cal{T})$ and a positive integer parameter $k$ as input and the objective is to decide whether there is a test cover of size at most $p(k,n,|{\cal T}|)$. We study four parameterizations for {\sc Test Cover} and obtain the following: (a) $k$-{\sc Test Cover}, and $(n-k)$-{\sc Test Cover} are fixed-parameter tractable (FPT). (b) $(|{\cal T}|-k)$-{\sc Test Cover} and $(\log n+k)$-{\sc Test Cover} are W[1]-hard. Thus, it is unlikely that these problems are FPT.
On the Role of Social Identity and Cohesion in Characterizing Online Social Communities
Venue: arXiv cs.SI 2012
Year: 2012

Two prevailing theories for explaining social group or community structure are cohesion and identity. The social cohesion approach posits that social groups arise out of an aggregation of individuals that have mutual interpersonal attraction as they share common characteristics. These characteristics can range from common interests to kinship ties and from social values to ethnic backgrounds. In contrast, the social identity approach posits that an individual is likely to join a group based on an intrinsic self-evaluation at a cognitive or perceptual level. In other words group members typically share an awareness of a common category membership. In this work we seek to understand the role of these two contrasting theories in explaining the behavior and stability of social communities in Twitter. A specific focal point of our work is to understand the role of these theories in disparate contexts ranging from disaster response to socio-political activism. We extract social identity and social cohesion features-of-interest for large scale datasets of five real-world events and examine the effectiveness of such features in capturing behavioral characteristics and the stability of groups. We also propose a novel measure of social group sustainability based on the divergence in group discussion. Our main findings are: 1) Sharing of social identities (especially physical location) among group members has a positive impact on group sustainability, 2) Structural cohesion (represented by high group density and low average shortest path length) is a strong indicator of group sustainability, and 3) Event characteristics play a role in shaping group sustainability, as social groups in transient events behave differently from groups in events that last longer.
Message-Passing Algorithms for Quadratic Minimization
Venue: arXiv cs.IT 2012
Year: 2012

Gaussian belief propagation (GaBP) is an iterative algorithm for computing the mean of a multivariate Gaussian distribution, or equivalently, the minimum of a multivariate positive definite quadratic function. Sufficient conditions, such as walk-summability, that guarantee the convergence and correctness of GaBP are known, but GaBP may fail to converge to the correct solution given an arbitrary positive definite quadratic function. As was observed in previous work, the GaBP algorithm fails to converge if the computation trees produced by the algorithm are not positive definite. In this work, we will show that the failure modes of the GaBP algorithm can be understood via graph covers, and we prove that a parameterized generalization of the min-sum algorithm can be used to ensure that the computation trees remain positive definite whenever the input matrix is positive definite. We demonstrate that the resulting algorithm is closely related to other iterative schemes for quadratic minimization such as the Gauss-Seidel and Jacobi algorithms. Finally, we observe, empirically, that there always exists a choice of parameters such that the above generalization of the GaBP algorithm converges.
A Comparative Study of Discretization Approaches for Granular Association Rule Mining
Venue: arXiv cs.DB 2012
Year: 2012

Granular association rule mining is a new relational data mining approach to reveal patterns hidden in multiple tables. The current research of granular association rule mining considers only nominal data. In this paper, we study the impact of discretization approaches on mining semantically richer and stronger rules from numeric data. Specifically, the Equal Width approach and the Equal Frequency approach are adopted and compared. The setting of interval numbers is a key issue in discretization approaches, so we compare different settings through experiments on a well-known real life data set. Experimental results show that: 1) discretization is an effective preprocessing technique in mining stronger rules; 2) the Equal Frequency approach helps generating more rules than the Equal Width approach; 3) with certain settings of interval numbers, we can obtain much more rules than others.
A Construction for Perfect Periodic Autocorrelation Sequences
Venue: arXiv cs.IT 2012
Year: 2012

We introduce a construction for perfect periodic autocorrelation sequences over roots of unity. The sequences share similarities to the perfect periodic sequence constructions of Liu, Frank, and Milewski.
Enhanced Multiple Routing Configurations For Fast IP Network Recovery From Multiple Failures
Venue: arXiv cs.NI 2012
Year: 2012

Now a days, Internet plays a major role in our day to day activities e.g., for online transactions, online shopping, and other network related applications. Internet suffers from slow convergence of routing protocols after a network failure which becomes a growing problem. Multiple Routing Configurations [MRC] recovers network from single node/link failures, but does not support network from multiple node/link failures. In this paper, we propose Enhanced MRC [EMRC], to support multiple node/link failures during data transmission in IP networks without frequent global re-convergence. By recovering these failures, data transmission in network will become fast.
An inverse iteration method for eigenvalue problems with eigenvector nonlinearities
Venue: arXiv cs.NA 2012
Year: 2012

Consider a symmetric matrix $A(v)\in\RR^{n\times n}$ depending on a vector $v\in\RR^n$ and satisfying the property $A(αv)=A(v)$ for any $α\in\RR\backslash{0}$. We will here study the problem of finding $(λ,v)\in\RR\times \RR^n\backslash\{0\}$ such that $(λ,v)$ is an eigenpair of the matrix $A(v)$ and we propose a generalization of inverse iteration for eigenvalue problems with this type of eigenvector nonlinearity. The convergence of the proposed method is studied and several convergence properties are shown to be analogous to inverse iteration for standard eigenvalue problems, including local convergence properties. The algorithm is also shown to be equivalent to a particular discretization of an associated ordinary differential equation, if the shift is chosen in a particular way. The algorithm is adapted to a variant of the Schrödinger equation known as the Gross-Pitaevskii equation. We use numerical simulations toillustrate the convergence properties, as well as the efficiency of the algorithm and the adaption.
Toeplitz Matrix Based Sparse Error Correction in System Identification: Outliers and Random Noises
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we consider robust system identification under sparse outliers and random noises. In our problem, system parameters are observed through a Toeplitz matrix. All observations are subject to random noises and a few are corrupted with outliers. We reduce this problem of system identification to a sparse error correcting problem using a Toeplitz structured real-numbered coding matrix. We prove the performance guarantee of Toeplitz structured matrix in sparse error correction. Thresholds on the percentage of correctable errors for Toeplitz structured matrices are also established. When both outliers and observation noise are present, we have shown that the estimation error goes to 0 asymptotically as long as the probability density function for observation noise is not "vanishing" around 0.
Unmixing of Hyperspectral Data Using Robust Statistics-based NMF
Venue: arXiv cs.CV 2012
Year: 2012

Mixed pixels are presented in hyperspectral images due to low spatial resolution of hyperspectral sensors. Spectral unmixing decomposes mixed pixels spectra into endmembers spectra and abundance fractions. In this paper using of robust statistics-based nonnegative matrix factorization (RNMF) for spectral unmixing of hyperspectral data is investigated. RNMF uses a robust cost function and iterative updating procedure, so is not sensitive to outliers. This method has been applied to simulated data using USGS spectral library, AVIRIS and ROSIS datasets. Unmixing results are compared to traditional NMF method based on SAD and AAD measures. Results demonstrate that this method can be used efficiently for hyperspectral unmixing purposes.
Stochastic Models of Misinformation Distribution in Online Social Networks
Venue: arXiv cs.SI 2012
Year: 2012

This report contains results of an experimental study of the distribution of misinformation in online social networks (OSNs). We consider the classification of the topologies of OSNs and analyze the parameters identified in order to relate the topology of a real network with one of the classes. We propose an algorithm for conducting a search for the percolation cluster in the social graph.
Modeling Movements in Oil, Gold, Forex and Market Indices using Search Volume Index and Twitter Sentiments
Venue: arXiv cs.CE 2012
Year: 2012

Study of the forecasting models using large scale microblog discussions and the search behavior data can provide a good insight for better understanding the market movements. In this work we collected a dataset of 2 million tweets and search volume index (SVI from Google) for a period of June 2010 to September 2011. We perform a study over a set of comprehensive causative relationships and developed a unified approach to a model for various market securities like equity (Dow Jones Industrial Average-DJIA and NASDAQ-100), commodity markets (oil and gold) and Euro Forex rates. We also investigate the lagged and statistically causative relations of Twitter sentiments developed during active trading days and market inactive days in combination with the search behavior of public before any change in the prices/ indices. Our results show extent of lagged significance with high correlation value upto 0.82 between search volumes and gold price in USD. We find weekly accuracy in direction (up and down prediction) uptil 94.3% for DJIA and 90% for NASDAQ-100 with significant reduction in mean average percentage error for all the forecasting models.
Latency Bounding by Trading off Consistency in NoSQL Store: A Staging and Stepwise Approach
Venue: arXiv cs.DB 2012
Year: 2012

Latency is a key service factor for user satisfaction. Consistency is in a trade-off relation with operation latency in the distributed and replicated scenario. Existing NoSQL stores guarantee either strong or weak consistencies but none provides the best consistency based on the response latency. In this paper, we introduce dConssandra, a NoSQL store enabling users to specify latency bounds for data access operations. dConssandra dynamically bounds data access latency by trading off replica consistency. dConssandra is based on Cassandra. In comparison to Cassandra's implementation, dConssandra has a staged replication strategy enabling synchronous or asynchronous replication on demand. The main idea to bound latency by trading off consistency is to decompose the replication process into minute steps and bound latency by executing only a subset of these steps. dConssandra also implements a different in-memory storage architecture to support the above features. Experimental results for dConssandra over an actual cluster demonstrate that (1) the actual response latency is bounded by the given latency constraint; (2) greater write latency bounds lead to a lower latency in reading the latest value; and, (3) greater read latency bounds lead to the return of more recently written values.
Energy-efficient transmission for wireless energy harvesting nodes
Venue: arXiv cs.IT 2012
Year: 2012

Energy harvesting is increasingly gaining importance as a means to charge battery powered devices such as sensor nodes. Efficient transmission strategies must be developed for Wireless Energy Harvesting Nodes (WEHNs) that take into account both the availability of energy and data in the node. We consider a scenario where data and energy packets arrive to the node where the time instants and amounts of the packets are known (offline approach). In this paper, the best data transmission strategy is found for a finite battery capacity WEHN that has to fulfill some Quality of Service (QoS) constraints, as well as the energy and data causality constraints. As a result of our analysis, we can state that losing energy due to overflows of the battery is inefficient unless there is no more data to transmit and that the problem may not have a feasible solution. Finally, an algorithm that computes the data transmission curve minimizing the total transmission time that satisfies the aforementioned constraints has been developed.
Streaming Balanced Graph Partitioning for Random Graphs
Venue: arXiv cs.DS 2012
Year: 2012

There has been a recent explosion in the size of stored data, partially due to advances in storage technology, and partially due to the growing popularity of cloud-computing and the vast quantities of data generated. This motivates the need for streaming algorithms that can compute approximate solutions without full random access to all of the data. We model the problem of loading a graph onto a distributed cluster as computing an approximately balanced $k$-partitioning of a graph in a streaming fashion with only one pass over the data. We give lower bounds on this problem, showing that no algorithm can obtain an $o(n)$ approximation with a random or adversarial stream ordering. We analyze two variants of a randomized greedy algorithm, one that prefers the $\arg\max$ and one that is proportional, on random graphs with embedded balanced $k$-cuts and are able to theoretically bound the performance of each algorithms - the $\arg\max$ algorithm is able to recover the embedded $k$-cut, while, surprisingly, the proportional variant can not. This matches the experimental results in [25].
Using Wikipedia to Boost SVD Recommender Systems
Venue: arXiv cs.LG 2012
Year: 2012

Singular Value Decomposition (SVD) has been used successfully in recent years in the area of recommender systems. In this paper we present how this model can be extended to consider both user ratings and information from Wikipedia. By mapping items to Wikipedia pages and quantifying their similarity, we are able to use this information in order to improve recommendation accuracy, especially when the sparsity is high. Another advantage of the proposed approach is the fact that it can be easily integrated into any other SVD implementation, regardless of additional parameters that may have been added to it. Preliminary experimental results on the MovieLens dataset are encouraging.
Physics inspired algorithms for (co)homology computation
Venue: arXiv cs.CE 2012
Year: 2012

The issue of computing (co)homology generators of a cell complex is gaining a pivotal role in various branches of science. While this issue can be rigorously solved in polynomial time, it is still overly demanding for large scale problems. Drawing inspiration from low-frequency electrodynamics, this paper presents a physics inspired algorithm for first cohomology group computations on three-dimensional complexes. The algorithm is general and exhibits orders of magnitude speed up with respect to competing ones, allowing to handle problems not addressable before. In particular, when generators are employed in the physical modeling of magneto-quasistatic problems, this algorithm solves one of the most long-lasting problems in low-frequency computational electromagnetics. In this case, the effectiveness of the algorithm and its ease of implementation may be even improved by introducing the novel concept of \textit{lazy cohomology generators}.
The Clustering of Author's Texts of English Fiction in the Vector Space of Semantic Fields
Venue: arXiv cs.CL 2012
Year: 2012

The clustering of text documents in the vector space of semantic fields and in the semantic space with orthogonal basis has been analysed. It is shown that using the vector space model with the basis of semantic fields is effective in the cluster analysis algorithms of author's texts in English fiction. The analysis of the author's texts distribution in cluster structure showed the presence of the areas of semantic space that represent the author's ideolects of individual authors. SVD factorization of the semantic fields matrix makes it possible to reduce significantly the dimension of the semantic space in the cluster analysis of author's texts.
Model Reduction using a Frequency-Limited H2-Cost
Venue: arXiv cs.SY 2012
Year: 2012

We propose a method for model reduction on a given frequency range, without the use of input and output filter weights. The method uses a nonlinear optimization approach to minimize a frequency limited H2 like cost function. An important contribution in the paper is the derivation of the gradient of the proposed cost function. The fact that we have a closed form expression for the gradient and that considerations have been taken to make the gradient computationally efficient to compute enables us to efficiently use off-the-shelf optimization software to solve the optimization problem.
The 2-valued case of makespan minimization with assignment constraints
Venue: arXiv cs.DS 2012
Year: 2012

We consider the following special case of minimizing makespan. A set of jobs $J$ and a set of machines $M$ are given. Each job $j \in J$ can be scheduled on a machine from a subset $M_j$ of $M$. The processing time of $j$ is the same on all machines in $M_j.$ The jobs are of two sizes, namely $b$ (big) and $s$ (small). We present a polynomial-time algorithm that approximates the value of the optimal makespan within a factor of 1.883 and some further improvements when every job can be scheduled on at most two machines.
Inferring Attitude in Online Social Networks Based On Quadratic Correlation
Venue: arXiv cs.SI 2012
Year: 2012

The structure of an online social network in most cases cannot be described just by links between its members. We study online social networks, in which members may have certain attitude, positive or negative toward each other, and so the network consists of a mixture of both positive and negative relationships. Our goal is to predict the sign of a given relationship based on the evidences provided in the current snapshot of the network. More precisely, using machine learning techniques we develop a model that after being trained on a particular network predicts the sign of an unknown or hidden link. The model uses relationships and influences from peers as evidences for the guess, however, the set of peers used is not predefined but rather learned during the training process. We use quadratic correlation between peer members to train the predictor. The model is tested on popular online datasets such as Epinions, Slashdot, and Wikipedia. In many cases it shows almost perfect prediction accuracy. Moreover, our model can also be efficiently updated as the underlaying social network evolves.
Trends in Combating Image Spam E-mails
Venue: arXiv cs.CR 2012
Year: 2012

With the rapid adoption of Internet as an easy way to communicate, the amount of unsolicited e-mails, known as spam e-mails, has been growing rapidly. The major problem of spam e-mails is the loss of productivity and a drain on IT resources. Today, we receive spam more rapidly than the legitimate e-mails. Initially, spam e-mails contained only textual messages which were easily detected by the text-based spam filters. To evade such detection, spammers came up with a new sophisticated technique called image spam. Image spam consists in embedding the advertisement text in images rather than in the body of the e-mail, yet the image contents are not detected by most spam filters. In this paper, we examine the motivations and the challenges in image spam filtering research, and we review the recent trends in combating image spam e-mails. The review indicates that spamming is a business model and spammers are becoming more sophisticated in their approach to adapt to all challenges, and hence, defeating the conventional spam filtering technologies. Therefore, image spam detection techniques should be scalable and adaptable to meet the future tactics of the spammers.