OpenRaiser/Intern-Atlas huggingface dataset:
A Novel Grid Based Dynamic Energy Efficient Routing Approach for Highly Dense Mobile Ad Hoc Networks
Venue: arXiv cs.NI 2013
Year: 2013

We have proposed a novel Grid Based Dynamic Energy Efficient Routing (GBDEER) approach which is aimed to construct an energy efficient path from source to destination based on grid area, where each grid will have three deferent levels of transmission power.
Sequential Selection of Correlated Ads by POMDPs
Venue: arXiv cs.IR 2013
Year: 2013

Online advertising has become a key source of revenue for both web search engines and online publishers. For them, the ability of allocating right ads to right webpages is critical because any mismatched ads would not only harm web users' satisfactions but also lower the ad income. In this paper, we study how online publishers could optimally select ads to maximize their ad incomes over time. The conventional offline, content-based matching between webpages and ads is a fine start but cannot solve the problem completely because good matching does not necessarily lead to good payoff. Moreover, with the limited display impressions, we need to balance the need of selecting ads to learn true ad payoffs (exploration) with that of allocating ads to generate high immediate payoffs based on the current belief (exploitation). In this paper, we address the problem by employing Partially observable Markov decision processes (POMDPs) and discuss how to utilize the correlation of ads to improve the efficiency of the exploration and increase ad incomes in a long run. Our mathematical derivation shows that the belief states of correlated ads can be naturally updated using a formula similar to collaborative filtering. To test our model, a real world ad dataset from a major search engine is collected and categorized. Experimenting over the data, we provide an analyse of the effect of the underlying parameters, and demonstrate that our algorithms significantly outperform other strong baselines.
Energy-aware Application Scaling on a Cloud
Venue: arXiv cs.DC 2013
Year: 2013

Cloud elasticity - the ability to use as much resources as needed at any given time - and low cost - a user pays only for the resources it consumes - represent solid incentives for many organizations to migrate some of their computational activities to a public cloud. As the interest in cloud computing grows, so does the size of the cloud computing centers and their energy footprint. The realization that power consumption of cloud computing centers is significant and it is expected to increase substantially in the future motivates our interest in scheduling and scaling algorithms which minimize power consumption. We propose energy-aware application scaling and resource management algorithms. Though targeting primarily the Infrastructure as a Service (IaaS), the system models and the algorithms we propose can be applied to the other cloud delivery models and to private clouds.
Power efficient carry propagate adder
Venue: arXiv cs.AR 2013
Year: 2013

Here we describe the design details and performance of proposed Carry Propagate Adder based on GDI technique. GDI technique is power efficient technique for designing digital circuit that consumes less power as compare to most commonly used CMOS technique. GDI also has an advantage of minimum propagation delay, minimum area required and less complexity for designing any digital circuit. We designed Carry Propagate Adder using GDI technique and compared its performance with CMOS technique in terms of area, delay and power dissipation. Circuit designed using CADENCE EDA tool and simulated using SPECTRE VIRTUOSO tool at 0.18m technology. Comparative performance result shows that Carry Propagate Adder using GDI technique dissipated 55.6% less power as compare to Carry Propagate Adder using CMOS technique.
Dynamic networks reveal key players in aging
Venue: arXiv cs.CE 2013
Year: 2013

Motivation: Since susceptibility to diseases increases with age, studying aging gains importance. Analyses of gene expression or sequence data, which have been indispensable for investigating aging, have been limited to studying genes and their protein products in isolation, ignoring their connectivities. However, proteins function by interacting with other proteins, and this is exactly what biological networks (BNs) model. Thus, analyzing the proteins' BN topologies could contribute to understanding of aging. Current methods for analyzing systems-level BNs deal with their static representations, even though cells are dynamic. For this reason, and because different data types can give complementary biological insights, we integrate current static BNs with aging-related gene expression data to construct dynamic, age-specific BNs. Then, we apply sensitive measures of topology to the dynamic BNs to study cellular changes with age. Results: While global BN topologies do not significantly change with age, local topologies of a number of genes do. We predict such genes as aging-related. We demonstrate credibility of our predictions by: 1) observing significant overlap between our predicted aging-related genes and "ground truth" aging-related genes; 2) showing that our aging-related predictions group by functions and diseases that are different than functions and diseases of genes that are not predicted as aging-related; 3) observing significant overlap between functions and diseases that are enriched in our aging-related predictions and those that are enriched in "ground truth" aging-related data; 4) providing evidence that diseases which are enriched in our aging-related predictions are linked to human aging; and 5) validating all of our high-scoring novel predictions via manual literature search.
Agent Based Software Testing Framework (ABSTF) for Application Maintenance
Venue: arXiv cs.SE 2013
Year: 2013

Software testing framework can be stated as the process of verifying and validating that a computer program/application works as expected and meets the requirements of the user. Usually testing can be done manually or using tools. Manual testing can be time consuming and tedious, also it requires heavy investment of human resources. Testing tools in fact have many advantages and are widely used nowadays, but also has several disadvantages. One particular problem is that human intervention is no longer needed. Testing tools are of high cost and so, it cannot be used for small companies. Hence in this paper we propose Agent based testing, which is a fast growing approach in testing field. The proposed system (ABSTF) has to reduce the application testing moment, easily find out bug and solve the bug by Regression Testing. Here by we are going to use a safe efficient regression selection technique algorithm to selectively retest the modified program. We also use Traceability relation of completeness checking for agent oriented system, which identifies missing elements in entire application and classifies defect in the testing moment. With the ability of agents to act autonomously, monitoring code changes and generating test cases for the changed version of code can be done dynamically.
Energy-aware adaptive bi-Lipschitz embeddings
Venue: arXiv cs.LG 2013
Year: 2013

We propose a dimensionality reducing matrix design based on training data with constraints on its Frobenius norm and number of rows. Our design criteria is aimed at preserving the distances between the data points in the dimensionality reduced space as much as possible relative to their distances in original data space. This approach can be considered as a deterministic Bi-Lipschitz embedding of the data points. We introduce a scalable learning algorithm, dubbed AMUSE, and provide a rigorous estimation guarantee by leveraging game theoretic tools. We also provide a generalization characterization of our matrix based on our sample data. We use compressive sensing problems as an example application of our problem, where the Frobenius norm design constraint translates into the sensing energy.
A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage
Venue: arXiv cs.DS 2013
Year: 2013

We consider a problem which has received considerable attention in systems literature because of its applications to routing in delay tolerant networks and replica placement in distributed storage systems. In abstract terms the problem can be stated as follows: Given a random variable $X$ generated by a known product distribution over $\{0,1\}^n$ and a target value $0 \leq θ\leq 1$, output a non-negative vector $w$, with $\|w\|_1 \le 1$, which maximizes the probability of the event $w \cdot X \ge θ$. This is a challenging non-convex optimization problem for which even computing the value $\Pr[w \cdot X \ge θ]$ of a proposed solution vector $w$ is #P-hard. We provide an additive EPTAS for this problem which, for constant-bounded product distributions, runs in $ \poly(n) \cdot 2^{\poly(1/\eps)}$ time and outputs an $\eps$-approximately optimal solution vector $w$ for this problem. Our approach is inspired by, and extends, recent structural results from the complexity-theoretic study of linear threshold functions. Furthermore, in spite of the objective function being non-smooth, we give a \emph{unicriterion} PTAS while previous work for such objective functions has typically led to a \emph{bicriterion} PTAS. We believe our techniques may be applicable to get unicriterion PTAS for other non-smooth objective functions.
Minimum Error Rate Training and the Convex Hull Semiring
Venue: arXiv cs.LG 2013
Year: 2013

We describe the line search used in the minimum error rate training algorithm MERT as the "inside score" of a weighted proof forest under a semiring defined in terms of well-understood operations from computational geometry. This conception leads to a straightforward complexity analysis of the dynamic programming MERT algorithms of Macherey et al. (2008) and Kumar et al. (2009) and practical approaches to implementation.
A reduction of 3-SAT problem to Buchberger algorithm
Venue: arXiv cs.CC 2013
Year: 2013

There is a number of known NP class problems, and majority of them have been shown to be equivalent to others. In particular now it is clear that construction of a Gröbner basis (or Buchberger algorithm) must be one of equivalent problems, but there was no example. In the following paper the reduction is constructed.
Parallel Graph Decompositions Using Random Shifts
Venue: arXiv cs.DS 2013
Year: 2013

We show an improved parallel algorithm for decomposing an undirected unweighted graph into small diameter pieces with a small fraction of the edges in between. These decompositions form critical subroutines in a number of graph algorithms. Our algorithm builds upon the shifted shortest path approach introduced in [Blelloch, Gupta, Koutis, Miller, Peng, Tangwongsan, SPAA 2011]. By combining various stages of the previous algorithm, we obtain a significantly simpler algorithm with the same asymptotic guarantees as the best sequential algorithm.
Limiting Performance of Conventional and Widely Linear DFT-precoded-OFDM Receivers in Wideband Frequency Selective Channels
Venue: arXiv cs.IT 2013
Year: 2013

This paper describes the limiting behavior of linear and decision feedback equalizers (DFEs) in single/multiple antenna systems employing real/complex-valued modulation alphabets. The wideband frequency selective channel is modeled using a Rayleigh fading channel model with infinite number of time domain channel taps. Using this model, we show that the considered equalizers offer a fixed post signal-to-noise-ratio (post-SNR) at the equalizer output that is close to the matched filter bound (MFB). General expressions for the post-SNR are obtained for zero-forcing (ZF) based conventional receivers as well as for the case of receivers employing widely linear (WL) processing. Simulation is used to study the bit error rate (BER) performance of both MMSE and ZF based receivers. Results show that the considered receivers advantageously exploit the rich frequency selective channel to mitigate both fading and inter-symbol-interference (ISI) while offering a performance comparable to the MFB.
The Network Improvement Problem for Equilibrium Routing
Venue: arXiv cs.GT 2013
Year: 2013

In routing games, agents pick their routes through a network to minimize their own delay. A primary concern for the network designer in routing games is the average agent delay at equilibrium. A number of methods to control this average delay have received substantial attention, including network tolls, Stackelberg routing, and edge removal. A related approach with arguably greater practical relevance is that of making investments in improvements to the edges of the network, so that, for a given investment budget, the average delay at equilibrium in the improved network is minimized. This problem has received considerable attention in the literature on transportation research and a number of different algorithms have been studied. To our knowledge, none of this work gives guarantees on the output quality of any polynomial-time algorithm. We study a model for this problem introduced in transportation research literature, and present both hardness results and algorithms that obtain nearly optimal performance guarantees. - We first show that a simple algorithm obtains good approximation guarantees for the problem. Despite its simplicity, we show that for affine delays the approximation ratio of 4/3 obtained by the algorithm cannot be improved. - To obtain better results, we then consider restricted topologies. For graphs consisting of parallel paths with affine delay functions we give an optimal algorithm. However, for graphs that consist of a series of parallel links, we show the problem is weakly NP-hard. - Finally, we consider the problem in series-parallel graphs, and give an FPTAS for this case. Our work thus formalizes the intuition held by transportation researchers that the network improvement problem is hard, and presents topology-dependent algorithms that have provably tight approximation guarantees.
Chaotic Characteristics of Discrete-time Linear Inclusion Dynamical Systems
Venue: arXiv cs.SY 2013
Year: 2013

In this paper, we study the chaotic behavior of a discrete-time linear inclusion.
Thermal analysis of 3D associative processor
Venue: arXiv cs.AR 2013
Year: 2013

Thermal density and hot spots limit three-dimensional (3D) implementation of massively-parallel SIMD processors and prohibit stacking DRAM dies above them. This study proposes replacing SIMD by an Associative Processor (AP). AP exhibits close to uniform thermal distribution with reduced hot spots. Additionally, AP may outperform SIMD processor when the data set size is sufficiently large, while dissipating less power. Comparative performance and thermal analysis supported by simulation confirm that AP might be preferable over SIMD for 3D implementation of large scale massively parallel processing engines combined with 3D DRAM integration.
Solving the Parity Problem with Rule 60 in Array Size of the Power of Two
Venue: arXiv cs.OH 2013
Year: 2013

In the parity problem, a given cellular automaton has to classify any initial configuration into two classes according to its parity. Elementary cellular automaton rule 60 can solve the parity problem in periodic boundary conditions with array size of the power of two. The spectral analysis of the configurations of rule 60 at each time step in the evolution reveals that spatial periodicity emerges as the evolution proceeds and the patterns with longer period split into the ones with shorter period. This phenomenon is analogous to the cascade process in which large scale eddies split into smaller ones in turbulence. By measuring the Lempel-Ziv complexity of configuration, we found the stepping decrease of the complexity during the evolution. This result might imply that a decision problem solving process is accompanied with the decline of complexity of configuration.
Some Improvements to Total Degree Tests
Venue: arXiv cs.CC 2013
Year: 2013

A low-degree test is a collection of simple, local rules for checking the proximity of an arbitrary function to a low-degree polynomial. Each rule depends on the function's values at a small number of places. If a function satisfies many rules then it is close to a low-degree polynomial. Low-degree tests play an important role in the development of probabilistically checkable proofs. In this paper we present two improvements to the efficiency of low-degree tests. Our first improvement concerns the smallest field size over which a low-degree test can work. We show how to test that a function is a degree $d$ polynomial over prime fields of size only $d+2$. Our second improvement shows a better efficiency of the low-degree test of Rubinfeld and Sudan (Proc. SODA 1992) than previously known. We show concrete applications of this improvement via the notion of "locally checkable codes". This improvement translates into better tradeoffs on the size versus probe complexity of probabilistically checkable proofs than previously known.
Self-Interference Cancellation with Phase Noise Induced ICI Suppression for Full-Duplex Systems
Venue: arXiv cs.IT 2013
Year: 2013

One of the main bottlenecks in practical full-duplex systems is the oscillator phase noise, which bounds the possible cancellable self-interference power. In this paper, a digitaldomain self-interference cancellation scheme for full-duplex orthogonal frequency division multiplexing systems is proposed. The proposed scheme increases the amount of cancellable selfinterference power by suppressing the effect of both transmitter and receiver oscillator phase noise. The proposed scheme consists of two main phases, an estimation phase and a cancellation phase. In the estimation phase, the minimum mean square error estimator is used to jointly estimate the transmitter and receiver phase noise associated with the incoming self-interference signal. In the cancellation phase, the estimated phase noise is used to suppress the intercarrier interference caused by the phase noise associated with the incoming self-interference signal. The performance of the proposed scheme is numerically investigated under different operating conditions. It is demonstrated that the proposed scheme could achieve up to 9dB more self-interference cancellation than the existing digital-domain cancellation schemes that ignore the intercarrier interference suppression.
A Comparative Study of CPU Scheduling Algorithms
Venue: arXiv cs.OS 2013
Year: 2013

Developing CPU scheduling algorithms and understanding their impact in practice can be difficult and time consuming due to the need to modify and test operating system kernel code and measure the resulting performance on a consistent workload of real applications. As processor is the important resource, CPU scheduling becomes very important in accomplishing the operating system (OS) design goals. The intention should be allowed as many as possible running processes at all time in order to make best use of CPU. This paper presents a state diagram that depicts the comparative study of various scheduling algorithms for a single CPU and shows which algorithm is best for the particular situation. Using this representation, it becomes much easier to understand what is going on inside the system and why a different set of processes is a candidate for the allocation of the CPU at different time. The objective of the study is to analyze the high efficient CPU scheduler on design of the high quality scheduling algorithms which suits the scheduling goals. Key Words:-Scheduler, State Diagrams, CPU-Scheduling, Performance
The State of Information and Communication Technology in Hungary, A Comparative Analysis
Venue: arXiv cs.CY 2013
Year: 2013

A novel comparative research and analysis method is proposed and applied on the Hungarian economic sectors. The question of what factors have an effect on their net income is essential for enterprises. First, the potential indicators related to economic sectors were studied and then compared to the net income of the surveyed enterprises. The data resulting from the comparison showed that the growing penetration of electronic marketpalces contributed to the change of the net income of enterprises in various economic sectors to the extent of 37%. Among all the potential indicators, only the indicator of electronic marketplaces has a direct influence on the net income of enterprises. Two clusters based on the potential indicators were indicated.
A Data-driven Study of Influences in Twitter Communities
Venue: arXiv cs.SI 2013
Year: 2013

This paper presents a quantitative study of Twitter, one of the most popular micro-blogging services, from the perspective of user influence. We crawl several datasets from the most active communities on Twitter and obtain 20.5 million user profiles, along with 420.2 million directed relations and 105 million tweets among the users. User influence scores are obtained from influence measurement services, Klout and PeerIndex. Our analysis reveals interesting findings, including non-power-law influence distribution, strong reciprocity among users in a community, the existence of homophily and hierarchical relationships in social influences. Most importantly, we observe that whether a user retweets a message is strongly influenced by the first of his followees who posted that message. To capture such an effect, we propose the first influencer (FI) information diffusion model and show through extensive evaluation that compared to the widely adopted independent cascade model, the FI model is more stable and more accurate in predicting influence spreads in Twitter communities.
An Alternative Proof of the Exponential Monotone Complexity of the Clique Function
Venue: arXiv cs.CC 2013
Year: 2013

In 1985, Razborov discovered a proof that the monotone circuit complexity of the clique problem is super-polynomial. Alon and Boppana improved the result into exponential lower bound exp(Ω(n / \log n)^{1/3})) of a monotone circuit C to compute cliques of size (1/4) (n / log n)^{2/3}, where n is the number of vertices in a graph. Both proofs are based on the method of approximations and Erdos and Rado's sunflower lemma. There has been an interest in further generalization of the proof scheme. In this paper, we present a new approach to show the exponential monotone complexity. Unlike the standard method, it dynamically constructs a counter example: Assuming a monotone circuit C of sub-exponential size to compute k-cliques c, an algorithm finds an edge set t containing no c in the disjunctive normal form constructed at the root of C. We call such t a shift. The proof shows that t is disjoint from an edge set z whose removal leaves no k-cliques. We explore the set theoretical nature of computation by Boolean circuits. We develop a theory by finding topological properties of the Hamming space 2^{[n]} where [n]={1, 2, ..., n}. A structural theorem is presented, which is closely related to the sunflower lemma and claims a stronger statement in most cases. The theory lays the foundation of the above shift method. It also shows the existence of a sunflower with small core in a family of sets, which is not an obvious consequence of the sunflower lemma. Lastly, we point out that the new methodology has potential to apply to a general circuit computing cliques due to the dynamic selection of t and z, and to improve the Alon-Boppana bound exp(Ω(n / \log n)^{1/3})).