OpenRaiser/Intern-Atlas huggingface dataset:
Zero-Gradient-Sum Algorithms for Distributed Convex Optimization: The Continuous-Time Case
Venue: arXiv cs.SY 2011
Year: 2011

This paper presents a set of continuous-time distributed algorithms that solve unconstrained, separable, convex optimization problems over undirected networks with fixed topologies. The algorithms are developed using a Lyapunov function candidate that exploits convexity, and are called Zero-Gradient-Sum (ZGS) algorithms as they yield nonlinear networked dynamical systems that evolve invariantly on a zero-gradient-sum manifold and converge asymptotically to the unknown optimizer. We also describe a systematic way to construct ZGS algorithms, show that a subset of them actually converge exponentially, and obtain lower and upper bounds on their convergence rates in terms of the network topologies, problem characteristics, and algorithm parameters, including the algebraic connectivity, Laplacian spectral radius, and function curvatures. The findings of this paper may be regarded as a natural generalization of several well-known algorithms and results for distributed consensus, to distributed convex optimization.
Optimal coding for the deletion channel with small deletion probability
Venue: arXiv cs.IT 2011
Year: 2011

The deletion channel is the simplest point-to-point communication channel that models lack of synchronization. Input bits are deleted independently with probability d, and when they are not deleted, they are not affected by the channel. Despite significant effort, little is known about the capacity of this channel, and even less about optimal coding schemes. In this paper we develop a new systematic approach to this problem, by demonstrating that capacity can be computed in a series expansion for small deletion probability. We compute three leading terms of this expansion, and find an input distribution that achieves capacity up to this order. This constitutes the first optimal coding result for the deletion channel. The key idea employed is the following: We understand perfectly the deletion channel with deletion probability d=0. It has capacity 1 and the optimal input distribution is i.i.d. Bernoulli(1/2). It is natural to expect that the channel with small deletion probabilities has a capacity that varies smoothly with d, and that the optimal input distribution is obtained by smoothly perturbing the i.i.d. Bernoulli(1/2) process. Our results show that this is indeed the case. We think that this general strategy can be useful in a number of capacity calculations.
Topology Control and Routing in Mobile Ad Hoc Networks with Cognitive Radios
Venue: arXiv cs.IT 2011
Year: 2011

Cognitive radio (CR) technology will have significant impacts on upper layer performance in mobile ad hoc networks (MANETs). In this paper, we study topology control and routing in CR-MANETs. We propose a distributed Prediction-based Cognitive Topology Control (PCTC) scheme to provision cognition capability to routing in CR-MANETs. PCTC is a midware-like cross-layer module residing between CR module and routing. The proposed PCTC scheme uses cognitive link availability prediction, which is aware of the interference to primary users, to predict the available duration of links in CR-MANETs. Based on the link prediction, PCTC constructs an efficient and reliable topology, which is aimed at mitigating re-routing frequency and improving end-to-end network performance such as throughput and delay. Simulation results are presented to show the effectiveness of the proposed scheme.
Towards joint decoding of binary Tardos fingerprinting codes
Venue: arXiv cs.IT 2011
Year: 2011

The class of joint decoder of probabilistic fingerprinting codes is of utmost importance in theoretical papers to establish the concept of fingerprint capacity. However, no implementation supporting a large user base is known to date. This article presents an iterative decoder which is, as far as we are aware of, the first practical attempt towards joint decoding. The discriminative feature of the scores benefits on one hand from the side-information of previously accused users, and on the other hand, from recently introduced universal linear decoders for compound channels. Neither the code construction nor the decoder make precise assumptions about the collusion (size or strategy). The extension to incorporate soft outputs from the watermarking layer is straightforward. An extensive experimental work benchmarks the very good performance and offers a clear comparison with previous state-of-the-art decoders.
Adaptive Probabilistic Flooding for Multipath Routing
Venue: arXiv cs.NI 2011
Year: 2011

In this work, we develop a distributed source routing algorithm for topology discovery suitable for ISP transport networks, that is however inspired by opportunistic algorithms used in ad hoc wireless networks. We propose a plug-and-play control plane, able to find multiple paths toward the same destination, and introduce a novel algorithm, called adaptive probabilistic flooding, to achieve this goal. By keeping a small amount of state in routers taking part in the discovery process, our technique significantly limits the amount of control messages exchanged with flooding -- and, at the same time, it only minimally affects the quality of the discovered multiple path with respect to the optimal solution. Simple analytical bounds, confirmed by results gathered with extensive simulation on four realistic topologies, show our approach to be of high practical interest.
On the Spectrum Handoff for Cognitive Radio Ad Hoc Networks without Common Control Channel
Venue: arXiv cs.IT 2011
Year: 2011

Cognitive radio (CR) technology is a promising solution to enhance the spectrum utilization by enabling unlicensed users to exploit the spectrum in an opportunistic manner. Since unlicensed users are temporary visitors to the licensed spectrum, they are required to vacate the spectrum when a licensed user reclaims it. Due to the randomness of the appearance of licensed users, disruptions to both licensed and unlicensed communications are often difficult to prevent. In this chapter, a proactive spectrum handoff framework for CR ad hoc networks is proposed to address these concerns. In the proposed framework, channel switching policies and a proactive spectrum handoff protocol are proposed to let unlicensed users vacate a channel before a licensed user utilizes it to avoid unwanted interference. Network coordination schemes for unlicensed users are also incorporated into the spectrum handoff protocol design to realize channel rendezvous. Moreover, a distributed channel selection scheme to eliminate collisions among unlicensed users is proposed. In our proposed framework, unlicensed users coordinate with each other without using a common control channel. We compare our proposed proactive spectrum handoff protocol with a reactive spectrum handoff protocol, under which unlicensed users switch channels after collisions with licensed transmissions occur. Simulation results show that our proactive spectrum handoff outperforms the reactive spectrum handoff approach in terms of higher throughput and fewer collisions to licensed users. In addition, we propose a novel three dimensional discrete-time Markov chain to characterize the process of reactive spectrum handoffs and analyze the performance of unlicensed users. We validate the numerical results obtained from our proposed Markov model against simulation and investigate other parameters of interest in the spectrum handoff scenario.
Methods of Hierarchical Clustering
Venue: arXiv cs.IR 2011
Year: 2011

We survey agglomerative hierarchical clustering algorithms and discuss efficient implementations that are available in R and other software environments. We look at hierarchical self-organizing maps, and mixture models. We review grid-based clustering, focusing on hierarchical density-based approaches. Finally we describe a recently developed very efficient (linear time) hierarchical clustering algorithm, which can also be viewed as a hierarchical grid-based algorithm.
Optimized Performance Evaluation of LTE Hard Handover Algorithm with Average RSRP Constraint
Venue: arXiv cs.NI 2011
Year: 2011

Hard handover mechanism is adopted to be used in 3GPP Long Term Evolution (3GPP LTE) in order to reduce the complexity of the LTE network architecture. This mechanism comes with degradation in system throughput as well as a higher system delay. This paper proposes a new handover algorithm known as LTE Hard Handover Algorithm with Average Received Signal Reference Power (RSRP) Constraint (LHHAARC) in order to minimize number of handovers and the system delay as well as maximize the system throughput. An optimized system performance of the LHHAARC is evaluated and compared with three well-known handover algorithms via computer simulation. The simulation results show that the LHHAARC outperforms three well-known handover algorithms by having less number of average handovers per UE per second, shorter total system delay whilst maintaining a higher total system throughput.
Net Neutrality and Quality of Service
Venue: arXiv cs.NI 2011
Year: 2011

2010 has witnessed many public consultations around the world concerning Net neutrality. A second legislative phase that may follow, could involve various structural changes in the Internet. The status that the Internet access has in Europe as a universal service evolves as the level of quality of service (QoS) to be offered improves. If guarantees on QoS are to be imposed, as requested by several economic actors, it would require introducing new indicators of quality of services, as well as regulation legislation and monitoring of the offered levels of QoS. This tendency in Europe may change the nature of the Internet from a best effort network to, perhaps, a more expensive one, that offers guaranteed performance. This paper presents an overview of the above issues as well as an overview of recent research on net-neutrality, with an emphasis on game theoretical approaches.
WSR Maximized Resource Allocation in Multiple DF Relays Aided OFDMA Downlink Transmission
Venue: arXiv cs.IT 2011
Year: 2011

This paper considers the weighted sum rate (WSR) maximized resource allocation (RA) constrained by a system sum power in an orthogonal frequency division multiple access (OFDMA) downlink transmission system assisted by multiple decode-and-forward (DF) relays. In particular, multiple relays may cooperate with the source for every relay-aided transmission. A two-step algorithm is proposed to find the globally optimum RA. In the first step, the optimum source/relay power and assisting relays that maximize the rate is found for every combination of subcarrier and destination, assuming a sum power is allocated to the transmission at that subcarrier to that destination in the relay-aided transmission mode and the direct mode, respectively. In the second step, a convex-optimization based algorithm is designed to find the globally optimum assignment of destination, transmission mode, and sum power for each subcarrier to maximize the WSR. Combining the RAs found in the two steps, the globally optimum RA can be found. In addition, we show that the optimum RA in the second step can readily be derived when the system sum power is very high. The effectiveness of the proposed algorithm is illustrated by numerical experiments.
Self-Repairing Codes for Distributed Storage - A Projective Geometric Construction
Venue: arXiv cs.DC 2011
Year: 2011

Self-Repairing Codes (SRC) are codes designed to suit the need of coding for distributed networked storage: they not only allow stored data to be recovered even in the presence of node failures, they also provide a repair mechanism where as little as two live nodes can be contacted to regenerate the data of a failed node. In this paper, we propose a new instance of self-repairing codes, based on constructions of spreads coming from projective geometry. We study some of their properties to demonstrate the suitability of these codes for distributed networked storage.
Faster Gossiping in Bidirectional Radio Networks with Large Labels
Venue: arXiv cs.DC 2011
Year: 2011

We consider unknown ad-hoc radio networks, when the underlying network is bidirectional and nodes can have polynomially large labels. For this model, we present a deterministic protocol for gossiping which takes $O(n \lg^2 n \lg \lg n)$ rounds. This improves upon the previous best result for deterministic gossiping for this model by [Gasienec, Potapov, Pagourtizis, Deterministic Gossiping in Radio Networks with Large labels, ESA (2002)], who present a protocol of round complexity $O(n \lg^3 n \lg \lg n)$ for this problem. This resolves open problem posed in [Gasienec, Efficient gossiping in radio networks, SIROCCO (2009)], who cite bridging gap between lower and upper bounds for this problem as an important objective. We emphasize that a salient feature of our protocol is its simplicity, especially with respect to the previous best known protocol for this problem.
If more than Analytical Modeling is Needed to Predict Real Agents' Strategic Interaction
Venue: arXiv cs.GT 2011
Year: 2011

This paper presents the research on the interdisciplinary research infrastructure for understanding human reasoning in game-theoretic terms. Strategic reasoning is considered to impact human decision making in social, economical and competitive interactions. The provided introduction explains and connects concepts from AI, game theory and psychology. First result is a concept of interdisciplinary game description language as a part of the focused interdisciplinary research infrastructure. The need of this domain-specific language is motivated and is aimed to accelerate the current developments. As second result, the paper provides a summary of ongoing research and its significance.
Transition Systems for Model Generators - A Unifying Approach
Venue: arXiv cs.AI 2011
Year: 2011

A fundamental task for propositional logic is to compute models of propositional formulas. Programs developed for this task are called satisfiability solvers. We show that transition systems introduced by Nieuwenhuis, Oliveras, and Tinelli to model and analyze satisfiability solvers can be adapted for solvers developed for two other propositional formalisms: logic programming under the answer-set semantics, and the logic PC(ID). We show that in each case the task of computing models can be seen as "satisfiability modulo answer-set programming," where the goal is to find a model of a theory that also is an answer set of a certain program. The unifying perspective we develop shows, in particular, that solvers CLASP and MINISATID are closely related despite being developed for different formalisms, one for answer-set programming and the latter for the logic PC(ID).
Model Checking of Boolean Process Models
Venue: arXiv cs.LO 2011
Year: 2011

In the field of Business Process Management formal models for the control flow of business processes have been designed since more than 15 years. Which methods are best suited to verify the bulk of these models? The first step is to select a formal language which fixes the semantics of the models. We adopt the language of Boolean systems as reference language for Boolean process models. Boolean systems form a simple subclass of coloured Petri nets. Their characteristics are low tokens to model explicitly states with a subsequent skipping of activations and arbitrary logical rules of type AND, XOR, OR etc. to model the split and join of the control flow. We apply model checking as a verification method for the safeness and liveness of Boolean systems. Model checking of Boolean systems uses the elementary theory of propositional logic, no modal operators are needed. Our verification builds on a finite complete prefix of a certain T-system attached to the Boolean system. It splits the processes of the Boolean system into a finite set of base processes of bounded length. Their behaviour translates to formulas from propositional logic. Our verification task consists in checking the satisfiability of these formulas. In addition we have implemented our model checking algorithm as a java program. The time needed to verify a given Boolean system depends critically on the number of initial tokens. Because the algorithm has to solve certain SAT-problems, polynomial complexity cannot be expected. The paper closes with the model checking of some Boolean process models which have been designed as Event-driven Process Chains.
The LOFAR Beam Former: Implementation and Performance Analysis
Venue: arXiv cs.DC 2011
Year: 2011

Traditional radio telescopes use large, steel dishes to observe radio sources. The LOFAR radio telescope is different, and uses tens of thousands of fixed, non-movable antennas instead, a novel design that promises ground-breaking research in astronomy. The antennas observe omnidirectionally, and sky sources are observed by signal-processing techniques that combine the data from all antennas. Another new feature of LOFAR is the elaborate use of software to do signal processing in real time, where traditional telescopes use custom-built hardware. The use of software leads to an instrument that is inherently more flexible. However, the enormous data rate (198 Gb/s of input data) and processing requirements compel the use of a supercomputer: we use an IBM Blue Gene/P. This paper presents a collection of new processing pipelines, collectively called the beam-forming pipelines, that greatly enhance the functionality of the telescope. Where our first pipeline could only correlate data to create sky images, the new pipelines allow the discovery of unknown pulsars, observations of known pulsars, and (in the future), to observe cosmic rays and study transient events. Unlike traditional telescopes, we can observe in hundreds of directions simultaneously. This is useful, for example, to search the sky for new pulsars. The use of software allows us to quickly add new functionality and to adapt to new insights that fully exploit the novel features and the power of our unique instrument. We also describe our optimisations to use the Blue Gene/P at very high efficiencies, maximising the effectiveness of the entire telescope. A thorough performance study identifies the limits of our system.
Complex-Valued Random Vectors and Channels: Entropy, Divergence, and Capacity
Venue: arXiv cs.IT 2011
Year: 2011

Recent research has demonstrated significant achievable performance gains by exploiting circularity/non-circularity or propeness/improperness of complex-valued signals. In this paper, we investigate the influence of these properties on important information theoretic quantities such as entropy, divergence, and capacity. We prove two maximum entropy theorems that strengthen previously known results. The proof of the former theorem is based on the so-called circular analog of a given complex-valued random vector. Its introduction is supported by a characterization theorem that employs a minimum Kullback-Leibler divergence criterion. In the proof of latter theorem, on the other hand, results about the second-order structure of complex-valued random vectors are exploited. Furthermore, we address the capacity of multiple-input multiple-output (MIMO) channels. Regardless of the specific distribution of the channel parameters (noise vector and channel matrix, if modeled as random), we show that the capacity-achieving input vector is circular for a broad range of MIMO channels (including coherent and noncoherent scenarios). Finally, we investigate the situation of an improper and Gaussian distributed noise vector. We compute both capacity and capacity-achieving input vector and show that improperness increases capacity, provided that the complementary covariance matrix is exploited. Otherwise, a capacity loss occurs, for which we derive an explicit expression.
A Simplest Undecidable Modal Logic
Venue: arXiv cs.LO 2011
Year: 2011

Modal logics are widely used in computer science. The complexity of their satisfiability problems has been an active field of research since the 1970s. We prove that even very "simple" modal logics can be undecidable: We show that there is an undecidable modal logic that can be obtained by restricting the allowed models with a first-order formula in which only universal quantifiers appear.
A Month in the Life of Groupon
Venue: arXiv cs.SI 2011
Year: 2011

Groupon has become the latest Internet sensation, providing daily deals to customers in the form of discount offers for restaurants, ticketed events, appliances, services, and other items. We undertake a study of the economics of daily deals on the web, based on a dataset we compiled by monitoring Groupon over several weeks. We use our dataset to characterize Groupon deal purchases, and to glean insights about Groupon's operational strategy. Our focus is on purchase incentives. For the primary purchase incentive, price, our regression model indicates that demand for coupons is relatively inelastic, allowing room for price-based revenue optimization. More interestingly, mining our dataset, we find evidence that Groupon customers are sensitive to other, "soft", incentives, e.g., deal scheduling and duration, deal featuring, and limited inventory. Our analysis points to the importance of considering incentives other than price in optimizing deal sites and similar systems.
Universal Emergence of PageRank
Venue: arXiv cs.IR 2011
Year: 2011

The PageRank algorithm enables to rank the nodes of a network through a specific eigenvector of the Google matrix, using a damping parameter $α\in ]0,1[$. Using extensive numerical simulations of large web networks, with a special accent on British University networks, we determine numerically and analytically the universal features of PageRank vector at its emergence when $α\rightarrow 1$. The whole network can be divided into a core part and a group of invariant subspaces. For $ α\rightarrow 1$ the PageRank converges to a universal power law distribution on the invariant subspaces whose size distribution also follows a universal power law. The convergence of PageRank at $ α\rightarrow 1$ is controlled by eigenvalues of the core part of the Google matrix which are extremely close to unity leading to large relaxation times as for example in spin glasses.
Multilingual lexicon design tool and database management system for MT
Venue: arXiv cs.CL 2011
Year: 2011

The paper presents the design and development of English-Lithuanian-English dictionarylexicon tool and lexicon database management system for MT. The system is oriented to support two main requirements: to be open to the user and to describe much more attributes of speech parts as a regular dictionary that are required for the MT. Programming language Java and database management system MySql is used to implement the designing tool and lexicon database respectively. This solution allows easily deploying this system in the Internet. The system is able to run on various OS such as: Windows, Linux, Mac and other OS where Java Virtual Machine is supported. Since the modern lexicon database managing system is used, it is not a problem accessing the same database for several users.