OpenRaiser/Intern-Atlas huggingface dataset:
On the Effective Capacity of Two-Hop Communication Systems
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, two-hop communication between a source and a destination with the aid of an intermediate relay node is considered. Both the source and intermediate relay node are assumed to operate under statistical quality of service (QoS) constraints imposed as limitations on the buffer overflow probabilities. It is further assumed that the nodes send the information at fixed power levels and have perfect channel side information. In this scenario, the maximum constant arrival rates that can be supported by this two-hop link are characterized by finding the effective capacity. Through this analysis, the impact upon the throughput of having buffer constraints at the source and intermediate-hop nodes is identified.
Low Power Reversible Parallel Binary Adder/Subtractor
Venue: arXiv cs.PF 2010
Year: 2010

In recent years, Reversible Logic is becoming more and more prominent technology having its applications in Low Power CMOS, Quantum Computing, Nanotechnology, and Optical Computing. Reversibility plays an important role when energy efficient computations are considered. In this paper, Reversible eight-bit Parallel Binary Adder/Subtractor with Design I, Design II and Design III are proposed. In all the three design approaches, the full Adder and Subtractors are realized in a single unit as compared to only full Subtractor in the existing design. The performance analysis is verified using number reversible gates, Garbage input/outputs and Quantum Cost. It is observed that Reversible eight-bit Parallel Binary Adder/Subtractor with Design III is efficient compared to Design I, Design II and existing design.
Mantis: Predicting System Performance through Program Analysis and Modeling
Venue: arXiv cs.PF 2010
Year: 2010

We present Mantis, a new framework that automatically predicts program performance with high accuracy. Mantis integrates techniques from programming language and machine learning for performance modeling, and is a radical departure from traditional approaches. Mantis extracts program features, which are information about program execution runs, through program instrumentation. It uses machine learning techniques to select features relevant to performance and creates prediction models as a function of the selected features. Through program analysis, it then generates compact code slices that compute these feature values for prediction. Our evaluation shows that Mantis can achieve more than 93% accuracy with less than 10% training data set, which is a significant improvement over models that are oblivious to program features. The system generates code slices that are cheap to compute feature values.
Spectral Control of Mobile Robot Networks
Venue: arXiv cs.MA 2010
Year: 2010

The eigenvalue spectrum of the adjacency matrix of a network is closely related to the behavior of many dynamical processes run over the network. In the field of robotics, this spectrum has important implications in many problems that require some form of distributed coordination within a team of robots. In this paper, we propose a continuous-time control scheme that modifies the structure of a position-dependent network of mobile robots so that it achieves a desired set of adjacency eigenvalues. For this, we employ a novel abstraction of the eigenvalue spectrum by means of the adjacency matrix spectral moments. Since the eigenvalue spectrum is uniquely determined by its spectral moments, this abstraction provides a way to indirectly control the eigenvalues of the network. Our construction is based on artificial potentials that capture the distance of the network's spectral moments to their desired values. Minimization of these potentials is via a gradient descent closed-loop system that, under certain convexity assumptions, ensures convergence of the network topology to one with the desired set of moments and, therefore, eigenvalues. We illustrate our approach in nontrivial computer simulations.
Multi-Agent Programming Contest 2010 - The Jason-DTU Team
Venue: arXiv cs.MA 2010
Year: 2010

We provide a brief description of the Jason-DTU system, including the methodology, the tools and the team strategy that we plan to use in the agent contest.
Comparative Performance of Tabu Search and Simulated Annealing Heuristics for the Quadratic Assignment Problem
Venue: arXiv cs.DS 2010
Year: 2010

For almost two decades the question of whether tabu search (TS) or simulated annealing (SA) performs better for the quadratic assignment problem has been unresolved. To answer this question satisfactorily, we compare performance at various values of targeted solution quality, running each heuristic at its optimal number of iterations for each target. We find that for a number of varied problem instances, SA performs better for higher quality targets while TS performs better for lower quality targets.
Oblivious Algorithms for the Maximum Directed Cut Problem
Venue: arXiv cs.DS 2010
Year: 2010

This paper introduces a special family of randomized algorithms for Max DICUT that we call oblivious algorithms. Let the bias of a vertex be the ratio between the total weight of its outgoing edges and the total weight of all its edges. An oblivious algorithm selects at random in which side of the cut to place a vertex v, with probability that only depends on the bias of v, independently of other vertices. The reader may observe that the algorithm that ignores the bias and chooses each side with probability 1/2 has an approximation ratio of 1/4, whereas no oblivious algorithm can have an approximation ratio better than 1/2 (with an even directed cycle serving as a negative example). We attempt to characterize the best approximation ratio achievable by oblivious algorithms, and present results that are nearly tight. The paper also discusses natural extensions of the notion of oblivious algorithms, and extensions to the more general problem of Max 2-AND.
First results of the SOAP project. Open access publishing in 2010
Venue: arXiv cs.DL 2010
Year: 2010

The SOAP (Study of Open Access Publishing) project has compiled data on the present offer for open access publishing in online peer-reviewed journals. Starting from the Directory of Open Access Journals, several sources of data are considered, including inspection of journal web site and direct inquiries within the publishing industry. Several results are derived and discussed, together with their correlations: the number of open access journals and articles; their subject area; the starting date of open access journals; the size and business models of open access publishers; the licensing models; the presence of an impact factor; the uptake of hybrid open access.
Error Performance of Channel Coding in Random Access Communication
Venue: arXiv cs.IT 2010
Year: 2010

A new channel coding approach was proposed in [1] for random multiple access communication over the discrete-time memoryless channel. The coding approach allows users to choose their communication rates independently without sharing the rate information among each other or with the receiver. The receiver will either decode the message or report a collision depending on whether reliable message recovery is possible. It was shown that, asymptotically as the codeword length goes to infinity, the set of communication rates supporting reliable message recovery can be characterized by an achievable region which equals Shannon's information rate region possibly without a convex hull operation. In this paper, we derive achievable bounds on error probabilities, including the decoding error probability and the collision miss detection probability, of random multiple access systems with a finite codeword length. Achievable error exponents are obtained by taking the codeword length to infinity.
Robust H_infinity Filter Design for Lipschitz Nonlinear Systems via Multiobjective Optimization
Venue: arXiv cs.SY 2010
Year: 2010

In this paper, a new method of H_infinity observer design for Lipschitz nonlinear systems is proposed in the form of an LMI optimization problem. The proposed observer has guaranteed decay rate (exponential convergence) and is robust against unknown exogenous disturbance. In addition, thanks to the linearity of the proposed LMIs in the admissible Lipschitz constant, it can be maximized via LMI optimization. This adds an extra important feature to the observer, robustness against nonlinear uncertainty. Explicit bound on the tolerable nonlinear uncertainty is derived. The new LMI formulation also allows optimizations over the disturbance attenuation level (H_infinity cost). Then, the admissible Lipschitz constant and the disturbance attenuation level of the H_infinity filter are simultaneously optimized through LMI multiobjective optimization.
Reconstruction of Aggregation Tree in spite of Faulty Nodes in Wireless Sensor Networks
Venue: arXiv cs.DC 2010
Year: 2010

Recent advances in wireless sensor networks (WSNs) have led to many new promissing applications. However data communication between nodes consumes a large portion of the total energy of WSNs. Consequently efficient data aggregation technique can help greatly to reduce power consumption. Data aggregation has emerged as a basic approach in WSNs in order to reduce the number of transmissions of sensor nodes over {\it aggregation tree} and hence minimizing the overall power consumption in the network. If a sensor node fails during data aggregation then the aggregation tree is disconnected. Hence the WSNs rely on in-network aggregation for efficiency but a single faulty node can severely influence the outcome by contributing an arbitrary partial aggregate value. In this paper we have presented a distributed algorithm that reconstruct the aggregation tree from the initial aggregation tree excluding the faulty sensor node. This is a synchronous model that is completed in several rounds. Our proposed scheme can handle multiple number of faulty nodes as well.
Cut-Matching Games on Directed Graphs
Venue: arXiv cs.DS 2010
Year: 2010

We give O(log^2 n)-approximation algorithm based on the cut-matching framework of [10, 13, 14] for computing the sparsest cut on directed graphs. Our algorithm uses only O(log^2 n) single commodity max-flow computations and thus breaks the multicommodity-flow barrier for computing the sparsest cut on directed graphs
Deterministic and Energy-Optimal Wireless Synchronization
Venue: arXiv cs.DC 2010
Year: 2010

We consider the problem of clock synchronization in a wireless setting where processors must power-down their radios in order to save energy. Energy efficiency is a central goal in wireless networks, especially if energy resources are severely limited. In the current setting, the problem is to synchronize clocks of $m$ processors that wake up in arbitrary time points, such that the maximum difference between wake up times is bounded by a positive integer $n$, where time intervals are appropriately discretized. Currently, the best-known results for synchronization for single-hop networks of $m$ processors is a randomized algorithm due to \cite{BKO09} of O(\sqrt {n /m} \cdot poly-log(n)) awake times per processor and a lower bound of Omega(\sqrt{n/m}) of the number of awake times needed per processor \cite{BKO09}. The main open question left in their work is to close the poly-log gap between the upper and the lower bound and to de-randomize their probabilistic construction and eliminate error probability. This is exactly what we do in this paper. That is, we show a {deterministic} algorithm with radio use of Theta(\sqrt {n /m}) that never fails. We stress that our upper bound exactly matches the lower bound proven in \cite{BKO09}, up to a small multiplicative constant. Therefore, our algorithm is {optimal} in terms of energy efficiency and completely resolves a long sequence of works in this area. In order to achieve these results we devise a novel {adaptive} technique that determines the times when devices power their radios on and off. In addition, we prove several lower bounds on the energy efficiency of algorithms for {multi-hop networks}. Specifically, we show that any algorithm for multi-hop networks must have radio use of Omega(\sqrt n) per processor.
XML Query Processing and Query Languges: A Survey
Venue: arXiv cs.DB 2010
Year: 2010

Today's database is associated with interoperability between different domains and applications. This consequently results in the importance of data portability in database. XML format fits the requirements and it has been increasingly used for serving applications across different domains and purposes. However, querying XML document effectively and efficiently is still a challenging issue. This paper discusses query processing issues on XML and reviews proposed solutions for querying XML databases by various authors.
Error Exponent for Multiple-Access Channels:Lower Bounds
Venue: arXiv cs.IT 2010
Year: 2010

A unified framework to obtain all known lower bounds (random coding, typical random coding and expurgated bound) on the reliability function of a point-to-point discrete memoryless channel (DMC) is presented. By using a similar idea for a two-user discrete memoryless (DM) multiple-access channel (MAC), three lower bounds on the reliability function are derived. The first one (random coding) is identical to the best known lower bound on the reliability function of DM-MAC. It is shown that the random coding bound is the performance of the average code in the constant composition code ensemble. The second bound (Typical random coding) is the typical performance of the constant composition code ensemble. To derive the third bound (expurgated), we eliminate some of the codewords from the codebook with larger rate. This is the first bound of this type that explicitly uses the method of expurgation for MACs. It is shown that the exponent of the typical random coding and the expurgated bounds are greater than or equal to the exponent of the known random coding bounds for all rate pairs. Moreover, an example is given where the exponent of the expurgated bound is strictly larger. All these bounds can be universally obtained for all discrete memoryless MACs with given input and output alphabets.
Improved Combinatorial Algorithms for Wireless Information Flow
Venue: arXiv cs.IT 2010
Year: 2010

The work of Avestimehr et al. '07 has recently proposed a deterministic model for wireless networks and characterized the unicast capacity C of such networks as the minimum rank of the adjacency matrices describing all possible source-destination cuts. Amaudruz & Fragouli first proposed a polynomial-time algorithm for finding the unicast capacity of a linear deterministic wireless network in their 2009 paper. In this work, we improve upon Amaudruz & Fragouli's work and further reduce the computational complexity of the algorithm by fully exploring the useful combinatorial features intrinsic in the problem. Our improvement applies generally with any size of finite fields associated with the channel model. Comparing with other algorithms on solving the same problem, our improved algorithm is very competitive in terms of complexity.
Optimizing Monotone Functions Can Be Difficult
Venue: arXiv cs.NE 2010
Year: 2010

Extending previous analyses on function classes like linear functions, we analyze how the simple (1+1) evolutionary algorithm optimizes pseudo-Boolean functions that are strictly monotone. Contrary to what one would expect, not all of these functions are easy to optimize. The choice of the constant $c$ in the mutation probability $p(n) = c/n$ can make a decisive difference. We show that if $c < 1$, then the (1+1) evolutionary algorithm finds the optimum of every such function in $Θ(n \log n)$ iterations. For $c=1$, we can still prove an upper bound of $O(n^{3/2})$. However, for $c > 33$, we present a strictly monotone function such that the (1+1) evolutionary algorithm with overwhelming probability does not find the optimum within $2^{Ω(n)}$ iterations. This is the first time that we observe that a constant factor change of the mutation probability changes the run-time by more than constant factors.
Communicating Under Channel Uncertainty
Venue: arXiv cs.IT 2010
Year: 2010

For a single transmit and receive antenna system, a new constellation design is proposed to combat errors in the phase estimate of the channel coefficient. The proposed constellation is a combination of PSK and PAM constellations, where PSK is used to provide protection against phase errors, while PAM is used to increase the transmission rate using the knowledge of the magnitude of the channel coefficient. The performance of the proposed constellation is shown to be significantly better than the widely used QAM in terms of probability of error. The proposed strategy can also be extended to systems using multiple transmit and receive antennas.
Proactive Resource Allocation: Turning Predictable Behavior into Spectral Gain
Venue: arXiv cs.IT 2010
Year: 2010

This paper introduces the novel concept of proactive resource allocation in which the predictability of user behavior is exploited to balance the wireless traffic over time, and hence, significantly reduce the bandwidth required to achieve a given blocking/outage probability. We start with a simple model in which the smart wireless devices are assumed to predict the arrival of new requests and submit them to the network T time slots in advance. Using tools from large deviation theory, we quantify the resulting prediction diversity gain to establish that the decay rate of the outage event probabilities increases linearly with the prediction duration T. This model is then generalized to incorporate the effect of prediction errors and the randomness in the prediction lookahead time T. Remarkably, we also show that, in the cognitive networking scenario, the appropriate use of proactive resource allocation by the primary users results in more spectral opportunities for the secondary users at a marginal, or no, cost in the primary network outage. Finally, we conclude by a discussion of the new research questions posed under the umbrella of the proposed proactive (non-causal) wireless networking framework.
Hierarchical Multiclass Decompositions with Application to Authorship Determination
Venue: arXiv cs.AI 2010
Year: 2010

This paper is mainly concerned with the question of how to decompose multiclass classification problems into binary subproblems. We extend known Jensen-Shannon bounds on the Bayes risk of binary problems to hierarchical multiclass problems and use these bounds to develop a heuristic procedure for constructing hierarchical multiclass decomposition for multinomials. We test our method and compare it to the well known "all-pairs" decomposition. Our tests are performed using a new authorship determination benchmark test of machine learning authors. The new method consistently outperforms the all-pairs decomposition when the number of classes is small and breaks even on larger multiclass problems. Using both methods, the classification accuracy we achieve, using an SVM over a feature set consisting of both high frequency single tokens and high frequency token-pairs, appears to be exceptionally high compared to known results in authorship determination.
A Wideband Spectrum Sensing Method for Cognitive Radio using Sub-Nyquist Sampling
Venue: arXiv cs.IT 2010
Year: 2010

Spectrum sensing is a fundamental component in cognitive radio. A major challenge in this area is the requirement of a high sampling rate in the sensing of a wideband signal. In this paper a wideband spectrum sensing model is presented that utilizes a sub-Nyquist sampling scheme to bring substantial savings in terms of the sampling rate. The correlation matrix of a finite number of noisy samples is computed and used by a subspace estimator to detect the occupied and vacant channels of the spectrum. In contrast with common methods, the proposedmethod does not need the knowledge of signal properties that mitigates the uncertainty problem. We evaluate the performance of this method by computing the probability of detecting signal occupancy in terms of the number of samples and the SNR of randomly generated signals. The results show a reliable detection even in low SNR and small number of samples.
Splitting schemes for hyperbolic heat conduction equation
Venue: arXiv cs.NA 2010
Year: 2010

Rapid processes of heat transfer are not described by the standard heat conduction equation. To take into account a finite velocity of heat transfer, we use the hyperbolic model of heat conduction, which is connected with the relaxation of heat fluxes. In this case, the mathematical model is based on a hyperbolic equation of second order or a system of equations for the temperature and heat fluxes. In this paper we construct for the hyperbolic heat conduction equation the additive schemes of splitting with respect to directions. Unconditional stability of locally one-dimensional splitting schemes is established. New splitting schemes are proposed and studied for a system of equations written in terms of the temperature and heat fluxes.
Enabling Data Discovery through Virtual Internet Repositories
Venue: arXiv cs.DL 2010
Year: 2010

Mercury is a federated metadata harvesting, search and retrieval tool based on both open source and software developed at Oak Ridge National Laboratory. It was originally developed for NASA, and the Mercury development consortium now includes funding from NASA, USGS, and DOE. A major new version of Mercury was developed during 2007. This new version provides orders of magnitude improvements in search speed, support for additional metadata formats, integration with Google Maps for spatial queries, support for RSS delivery of search results, among other features. Mercury provides a single portal to information contained in disparate data management systems. It collects metadata and key data from contributing project servers distributed around the world and builds a centralized index. The Mercury search interfaces then allow the users to perform simple, fielded, spatial and temporal searches across these metadata sources. This centralized repository of metadata with distributed data sources provides extremely fast search results to the user, while allowing data providers to advertise the availability of their data and maintain complete control and ownership of that data.
Virtual Full-Duplex Wireless Communication via Rapid On-Off-Division Duplex
Venue: arXiv cs.IT 2010
Year: 2010

This paper introduces a novel paradigm for design- ing the physical and medium access control (MAC) layers of mobile ad hoc or peer-to-peer networks formed by half-duplex radios. A node equipped with such a radio cannot simultaneously transmit and receive useful signals at the same frequency. Unlike in conventional designs, where a node's transmission frames are scheduled away from its reception, each node transmits its signal through a randomly generated on-off duplex mask (or signature) over every frame interval, and receive a signal through each of its own off-slots. This is called rapid on-off- division duplex (RODD). Over the period of a single frame, every node can transmit a message to some or all of its peers, and may simultaneously receive a message from each peer. Thus RODD achieves virtual full-duplex communication using half-duplex radios and can simplify the design of higher layers of a network protocol stack significantly. The throughput of RODD is evaluated under some general settings, which is significantly larger than that of ALOHA. RODD is especially efficient in case the dominant traffic is simultaneous broadcast from nodes to their one-hop peers, such as in spontaneous wireless social networks, emergency situations or on battlefield. Important design issues of peer discovery, distribution of on-off signatures, synchronization and error-control coding are also addressed.