OpenRaiser/Intern-Atlas huggingface dataset:
On the Overhead of Interference Alignment: Training, Feedback, and Cooperation
Venue: arXiv cs.IT 2012
Year: 2012

Interference alignment (IA) is a cooperative transmission strategy that, under some conditions, achieves the interference channel's maximum number of degrees of freedom. Realizing IA gains, however, is contingent upon providing transmitters with sufficiently accurate channel knowledge. In this paper, we study the performance of IA in multiple-input multiple-output systems where channel knowledge is acquired through training and analog feedback. We design the training and feedback system to maximize IA's effective sum-rate: a non-asymptotic performance metric that accounts for estimation error, training and feedback overhead, and channel selectivity. We characterize effective sum-rate with overhead in relation to various parameters such as signal-to-noise ratio, Doppler spread, and feedback channel quality. A main insight from our analysis is that, by properly designing the CSI acquisition process, IA can provide good sum-rate performance in a very wide range of fading scenarios. Another observation from our work is that such overhead-aware analysis can help solve a number of practical network design problems. To demonstrate the concept of overhead-aware network design, we consider the example problem of finding the optimal number of cooperative IA users based on signal power and mobility.
A distributed resource allocation algorithm for many processes
Venue: arXiv cs.DC 2012
Year: 2012

Resource allocation is the problem that a process may enter a critical section CS of its code only when its resource requirements are not in conflict with those of other processes in their critical sections. For each execution of CS, these requirements are given anew. In the resource requirements, levels can be distinguished, such as e.g. read access or write access. We allow infinitely many processes that communicate by reliable asynchronous messages and have finite memory. A simple starvation-free solution is presented. Processes only wait for one another when they have conflicting resource requirements. The correctness of the solution is argued with invariants and temporal logic. It has been verified with the proof assistant PVS.
Non-definability of languages by generalized first-order formulas over (N,+)
Venue: arXiv cs.LO 2012
Year: 2012

We consider first-order logic with monoidal quantifiers over words. We show that all languages with a neutral letter, definable using the addition numerical predicate are also definable with the order predicate as the only numerical predicate. Let S be a subset of monoids. Let LS be the logic closed under quantification over the monoids in S and N be the class of neutral letter languages. Then we show that: LS[<,+] cap N = LS[<] Our result can be interpreted as the Crane Beach conjecture to hold for the logic LS[<,+]. As a corollary of our result we get the result of Roy and Straubing that FO+MOD[<,+] collapses to FO+MOD[<]. For cyclic groups, we answer an open question of Roy and Straubing, proving that MOD[<,+] collapses to MOD[<]. Our result also shows that multiplication is necessary for Barrington's theorem to hold. All these results can be viewed as separation results for very uniform circuit classes. For example we separate FO[<,+]-uniform CC0 from FO[<,+]-uniform ACC0.
Efficient Video Indexing on the Web: A System that Leverages User Interactions with a Video Player
Venue: arXiv cs.MM 2012
Year: 2012

In this paper, we propose a user-based video indexing method, that automatically generates thumbnails of the most important scenes of an online video stream, by analyzing users' interactions with a web video player. As a test bench to verify our idea we have extended the YouTube video player into the VideoSkip system. In addition, VideoSkip uses a web-database (Google Application Engine) to keep a record of some important parameters, such as the timing of basic user actions (play, pause, skip). Moreover, we implemented an algorithm that selects representative thumbnails. Finally, we populated the system with data from an experiment with nine users. We found that the VideoSkip system indexes video content by leveraging implicit users interactions, such as pause and thirty seconds skip. Our early findings point toward improvements of the web video player and its thumbnail generation technique. The VideSkip system could compliment content-based algorithms, in order to achieve efficient video-indexing in difficult videos, such as lectures or sports.
Magic Sets for Disjunctive Datalog Programs
Venue: arXiv cs.AI 2012
Year: 2012

In this paper, a new technique for the optimization of (partially) bound queries over disjunctive Datalog programs with stratified negation is presented. The technique exploits the propagation of query bindings and extends the Magic Set (MS) optimization technique. An important feature of disjunctive Datalog is nonmonotonicity, which calls for nondeterministic implementations, such as backtracking search. A distinguishing characteristic of the new method is that the optimization can be exploited also during the nondeterministic phase. In particular, after some assumptions have been made during the computation, parts of the program may become irrelevant to a query under these assumptions. This allows for dynamic pruning of the search space. In contrast, the effect of the previously defined MS methods for disjunctive Datalog is limited to the deterministic portion of the process. In this way, the potential performance gain by using the proposed method can be exponential, as could be observed empirically. The correctness of MS is established thanks to a strong relationship between MS and unfounded sets that has not been studied in the literature before. This knowledge allows for extending the method also to programs with stratified negation in a natural way. The proposed method has been implemented in DLV and various experiments have been conducted. Experimental results on synthetic data confirm the utility of MS for disjunctive Datalog, and they highlight the computational gain that may be obtained by the new method w.r.t. the previously proposed MS methods for disjunctive Datalog programs. Further experiments on real-world data show the benefits of MS within an application scenario that has received considerable attention in recent years, the problem of answering user queries over possibly inconsistent databases originating from integration of autonomous sources of information.
"I Wanted to Predict Elections with Twitter and all I got was this Lousy Paper" -- A Balanced Survey on Election Prediction using Twitter Data
Venue: arXiv cs.CY 2012
Year: 2012

Predicting X from Twitter is a popular fad within the Twitter research subculture. It seems both appealing and relatively easy. Among such kind of studies, electoral prediction is maybe the most attractive, and at this moment there is a growing body of literature on such a topic. This is not only an interesting research problem but, above all, it is extremely difficult. However, most of the authors seem to be more interested in claiming positive results than in providing sound and reproducible methods. It is also especially worrisome that many recent papers seem to only acknowledge those studies supporting the idea of Twitter predicting elections, instead of conducting a balanced literature review showing both sides of the matter. After reading many of such papers I have decided to write such a survey myself. Hence, in this paper, every study relevant to the matter of electoral prediction using social media is commented. From this review it can be concluded that the predictive power of Twitter regarding elections has been greatly exaggerated, and that hard research problems still lie ahead.
Active Contour with A Tangential Component
Venue: arXiv cs.CV 2012
Year: 2012

Conventional edge-based active contours often require the normal component of an edge indicator function on the optimal contours to approximate zero, while the tangential component can still be significant. In real images, the full gradients of the edge indicator function along the object boundaries are often small. Hence, the curve evolution of edge-based active contours can terminate early before converging to the object boundaries with a careless contour initialization. We propose a novel Geodesic Snakes (GeoSnakes) active contour that requires the full gradients of the edge indicator to vanish at the optimal solution. Besides, the conventional curve evolution approach for minimizing active contour energy cannot fully solve the Euler-Lagrange (EL) equation of our GeoSnakes active contour, causing a Pseudo Stationary Phenomenon (PSP). To address the PSP problem, we propose an auxiliary curve evolution equation, named the equilibrium flow (EF) equation. Based on the EF and the conventional curve evolution, we obtain a solution to the full EL equation of GeoSnakes active contour. Experimental results validate the proposed geometrical interpretation of the early termination problem, and they also show that the proposed method overcomes the problem.
Recovery of Low-Rank Plus Compressed Sparse Matrices with Application to Unveiling Traffic Anomalies
Venue: arXiv cs.IT 2012
Year: 2012

Given the superposition of a low-rank matrix plus the product of a known fat compression matrix times a sparse matrix, the goal of this paper is to establish deterministic conditions under which exact recovery of the low-rank and sparse components becomes possible. This fundamental identifiability issue arises with traffic anomaly detection in backbone networks, and subsumes compressed sensing as well as the timely low-rank plus sparse matrix recovery tasks encountered in matrix decomposition problems. Leveraging the ability of $\ell_1$- and nuclear norms to recover sparse and low-rank matrices, a convex program is formulated to estimate the unknowns. Analysis and simulations confirm that the said convex program can recover the unknowns for sufficiently low-rank and sparse enough components, along with a compression matrix possessing an isometry property when restricted to operate on sparse vectors. When the low-rank, sparse, and compression matrices are drawn from certain random ensembles, it is established that exact recovery is possible with high probability. First-order algorithms are developed to solve the nonsmooth convex optimization problem with provable iteration complexity guarantees. Insightful tests with synthetic and real network data corroborate the effectiveness of the novel approach in unveiling traffic anomalies across flows and time, and its ability to outperform existing alternatives.
A note on: No need to choose: How to get both a PTAS and Sublinear Query Complexity
Venue: arXiv cs.CC 2012
Year: 2012

We revisit various PTAS's (Polynomial Time Approximation Schemes) for minimization versions of dense problems, and show that they can be performed with sublinear query complexity. This means that not only do we obtain a (1+eps)-approximation to the NP-Hard problems in polynomial time, but also avoid reading the entire input. This setting is particularly advantageous when the price of reading parts of the input is high, as is the case, for examples, where humans provide the input. Trading off query complexity with approximation is the raison d'etre of the field of learning theory, and of the ERM (Empirical Risk Minimization) setting in particular. A typical ERM result, however, does not deal with computational complexity. We discuss two particular problems for which (a) it has already been shown that sublinear querying is sufficient for obtaining a (1 + eps)-approximation using unlimited computational power (an ERM result), and (b) with full access to input, we could get a (1+eps)-approximation in polynomial time (a PTAS). Here we show that neither benefit need be sacrificed. We get a PTAS with efficient query complexity.
The Anatomy of a Grid portal
Venue: arXiv cs.DC 2012
Year: 2012

In this paper we introduce a new way to deal with Grid portals referring to our implementation. L-GRID is a light portal to access the EGEE/EGI Grid infrastructure via Web, allowing users to submit their jobs from a common Web browser in a few minutes, without any knowledge about the Grid infrastructure. It provides the control over the complete lifecycle of a Grid Job, from its submission and status monitoring, to the output retrieval. The system, implemented as client-server architecture, is based on the Globus Grid middleware. The client side application is based on a java applet; the server relies on a Globus User Interface. There is no need of user registration on the server side, and the user needs only his own X.509 personal certificate. The system is user-friendly, secure (it uses SSL protocol, mechanism for dynamic delegation and identity creation in public key infrastructures), highly customizable, open source, and easy to install. The X.509 personal certificate does not get out from the local machine. It allows to reduce the time spent for the job submission, granting at the same time a higher efficiency and a better security level in proxy delegation and management.
Elimination of Glass Artifacts and Object Segmentation
Venue: arXiv cs.CV 2012
Year: 2012

Many images nowadays are captured from behind the glasses and may have certain stains discrepancy because of glass and must be processed to make differentiation between the glass and objects behind it. This research paper proposes an algorithm to remove the damaged or corrupted part of the image and make it consistent with other part of the image and to segment objects behind the glass. The damaged part is removed using total variation inpainting method and segmentation is done using kmeans clustering, anisotropic diffusion and watershed transformation. The final output is obtained by interpolation. This algorithm can be useful to applications in which some part of the images are corrupted due to data transmission or needs to segment objects from an image for further processing.
On the Locality of Some NP-Complete Problems
Venue: arXiv cs.DC 2012
Year: 2012

We consider the distributed message-passing {LOCAL} model. In this model a communication network is represented by a graph where vertices host processors, and communication is performed over the edges. Computation proceeds in synchronous rounds. The running time of an algorithm is the number of rounds from the beginning until all vertices terminate. Local computation is free. An algorithm is called {local} if it terminates within a constant number of rounds. The question of what problems can be computed locally was raised by Naor and Stockmayer \cite{NS93} in their seminal paper in STOC'93. Since then the quest for problems with local algorithms, and for problems that cannot be computed locally, has become a central research direction in the field of distributed algorithms \cite{KMW04,KMW10,LOW08,PR01}. We devise the first local algorithm for an {NP-complete} problem. Specifically, our randomized algorithm computes, with high probability, an O(n^{1/2 + epsilon} \cdot chi)-coloring within O(1) rounds, where epsilon > 0 is an arbitrarily small constant, and chi is the chromatic number of the input graph. (This problem was shown to be NP-complete in \cite{Z07}.) On our way to this result we devise a constant-time algorithm for computing (O(1), O(n^{1/2 + epsilon}))-network-decompositions. Network-decompositions were introduced by Awerbuch et al. \cite{AGLP89}, and are very useful for solving various distributed problems. The best previously-known algorithm for network-decomposition has a polylogarithmic running time (but is applicable for a wider range of parameters) \cite{LS93}. We also devise a Delta^{1 + epsilon}-coloring algorithm for graphs with sufficiently large maximum degree Delta that runs within O(1) rounds. It improves the best previously-known result for this family of graphs, which is O(\log-star n) \cite{SW10}.
Energy Efficient Service Delivery in Clouds in Compliance with the Kyoto Protocol
Venue: arXiv cs.DC 2012
Year: 2012

Cloud computing is revolutionizing the ICT landscape by providing scalable and efficient computing resources on demand. The ICT industry - especially data centers, are responsible for considerable amounts of CO2 emissions and will very soon be faced with legislative restrictions, such as the Kyoto protocol, defining caps at different organizational levels (country, industry branch etc.) A lot has been done around energy efficient data centers, yet there is very little work done in defining flexible models considering CO2. In this paper we present a first attempt of modeling data centers in compliance with the Kyoto protocol. We discuss a novel approach for trading credits for emission reductions across data centers to comply with their constraints. CO2 caps can be integrated with Service Level Agreements and juxtaposed to other computing commodities (e.g. computational power, storage), setting a foundation for implementing next-generation schedulers and pricing models that support Kyoto-compliant CO2 trading schemes.
The Design and Algorithms of a Verification Condition Generator
Venue: arXiv cs.SE 2012
Year: 2012

This dissertation discusses several problems loosely related, because they all involve a verification condition generator. The Boogie language is introduced; the architecture of a verification-generator is described. Then come more interesting parts. (1) Moving to a passive form representation can be seen as an automatic transformation into a pure functional language. How to formalize this transformation and what is its complexity? (2) How do various ways of describing the semantics of procedural languages (predicate transformers, operational semantics) relate to each other? (3) How to do incremental verification? That is, how to work less when re-verifying a program that changed only a little since the verifier was last run. (4) How to detect unreachable code, taking into account formal specifications?
Specification and Verification of Uplink Framework for Application of Software Engineering using RM-ODP
Venue: arXiv cs.OH 2012
Year: 2012

This paper present a survey and discussion of the Reference Model for Open Distributed Processing (RM-ODP) viewpoints; oriented approaches to requirements engineering viewpoint and a presentation of new work in the application wireless mobile phone, this area which has been designed with practical application using the Unified Modelling Language (UML)/VHDL_AMS (VHSIC Hardware Description Language Analog and Mixed-Signal). We mainly focus on rising and fulling time, action, uplink behaviour constraints (sequentiality, non determinism and concurrency constraints).We discuss the practical problems of introducing viewpoint; oriented requirements engineering into industrial software engineering practice and why these have prevented the widespread use of existing approaches. The goal of this article is to check the uplink path using the MIC (Microphone amplifier) with all analog inputs, and check the amplifier gain. This paper provides an example of using the Uplink Framework to build a comprehensive, good solution for Application Wireless Mobile Phone. Finally, we discuss how well this approach addresses some outstanding problems in requirements engineering (RE) and the practical industrial problems of introducing new requirements engineering methods.
jpf-concurrent: An extension of Java PathFinder for java.util.concurrent
Venue: arXiv cs.SE 2012
Year: 2012

One of the main challenges when verifying multi-threaded Java applications is the state space explosion problem. Due to thread interleavings, the number of states that the model checker has to verify can grow rapidly and impede the feasibility of verification. In the Java language, the source of thread interleavings can be the system under test as well as the Java Development Kit (JDK) itself. In our paper, we propose a method to minimize the state space explosion problem for applications verified under the Java PathFinder (JPF) model checker. Our method is based on abstracting the state of the application to a smaller domain and implementing application behavior using the Model Java Interface (MJI) of JPF. To show the capabilities of our approach, we have created a JPF extension called jpf-concurrent which abstracts classes from the Java Concurrency Utilities. Several benchmarks proved the usefulness of our approach. In all cases, our implementation was faster than the JDK implementation when running under the JPF model checker. Moreover, our implementation led to significantly smaller state spaces.
Migration of data for iKnow application at EURM - a case study
Venue: arXiv cs.SE 2012
Year: 2012

Software evolves. After many revisions and improvements software gets retired and replaced. When replacement takes place, one needs to migrate the data from the old database into the new database, so the new application can replace the old application. Student administration application (SAA) currently used by European University (EURM) has been outgrown by the university, and needs replacement. iKnow application developed as part of the iKnow Tempus project is scheduled to replace the existing Student Administration application at EURM. This paper describes the problems that were encountered while migrating the data from the old databases of SAA to the new database designed for the iKnow application. The problems were resolved using the well-known solutions typical for an ETL process, since data migration can be considered as a type of ETL process. In this paper we describe the solutions for the problems that we encountered while migrating the data.
On one-sided interval edge colorings of biregular bipartite graphs
Venue: arXiv cs.DM 2012
Year: 2012

A proper edge $t$-coloring of a graph $G$ is a coloring of edges of $G$ with colors $1,2,...,t$ such that all colors are used, and no two adjacent edges receive the same color. The set of colors of edges incident with a vertex $x$ is called a spectrum of $x$. An arbitrary nonempty subset of consecutive integers is called an interval. We say that a proper edge $t$-coloring of a graph $G$ is interval in the vertex $x$ if the spectrum of $x$ is an interval. We say that a proper edge $t$-coloring $φ$ of a graph $G$ is interval on a subset $R_0$ of vertices of $G$, if for an arbitrary $x\in R_0$, $φ$ is interval in $x$. We say that a subset $R$ of vertices of $G$ has an $i$-property if there is a proper edge $t$-coloring of $G$ which is interval on $R$. If $G$ is a graph, and a subset $R$ of its vertices has an $i$-property, then the minimum value of $t$ for which there is a proper edge $t$-coloring of $G$ interval on $R$ is denoted by $w_R(G)$. In this paper, for some bipartite graphs, we estimate the value of this parameter in that cases when $R$ coincides with the set of all vertices of one part of the graph.