OpenRaiser/Intern-Atlas huggingface dataset:
From Spectrum Pooling to Space Pooling: Opportunistic Interference Alignment in MIMO Cognitive Networks
Venue: arXiv cs.IT 2009
Year: 2009

We describe a non-cooperative interference alignment (IA) technique which allows an opportunistic multiple input multiple output (MIMO) link (secondary) to harmlessly coexist with another MIMO link (primary) in the same frequency band. Assuming perfect channel knowledge at the primary receiver and transmitter, capacity is achieved by transmiting along the spatial directions (SD) associated with the singular values of its channel matrix using a water-filling power allocation (PA) scheme. Often, power limitations lead the primary transmitter to leave some of its SD unused. Here, it is shown that the opportunistic link can transmit its own data if it is possible to align the interference produced on the primary link with such unused SDs. We provide both a processing scheme to perform IA and a PA scheme which maximizes the transmission rate of the opportunistic link. The asymptotes of the achievable transmission rates of the opportunistic link are obtained in the regime of large numbers of antennas. Using this result, it is shown that depending on the signal-to-noise ratio and the number of transmit and receive antennas of the primary and opportunistic links, both systems can achieve transmission rates of the same order.
Reducing Tile Complexity for the Self-Assembly of Scaled Shapes Through Temperature Programming
Venue: arXiv cs.CC 2009
Year: 2009

This paper concerns the self-assembly of scaled-up versions of arbitrary finite shapes. We work in the multiple temperature model that was introduced by Aggarwal, Cheng, Goldwasser, Kao, and Schweller (Complexities for Generalized Models of Self-Assembly, SODA 2004). The multiple temperature model is a natural generalization of Winfree's abstract tile assembly model, where the temperature of a tile system is allowed to be shifted up and down as self-assembly proceeds. We first exhibit two constant-size tile sets in which scaled-up versions of arbitrary shapes self-assemble. Our first tile set has the property that each scaled shape self-assembles via an asymptotically "Kolmogorov-optimum" temperature sequence but the scaling factor grows with the size of the shape being assembled. In contrast, our second tile set assembles each scaled shape via a temperature sequence whose length is proportional to the number of points in the shape but the scaling factor is a constant independent of the shape being assembled. We then show that there is no constant-size tile set that can uniquely assemble an arbitrary (non-scaled, connected) shape in the multiple temperature model, i.e., the scaling is necessary for self-assembly. This answers an open question of Kao and Schweller (Reducing Tile Complexity for Self-Assembly Through Temperature Programming, SODA 2006), who asked whether such a tile set existed.
PT-Scotch: A tool for efficient parallel graph ordering
Venue: arXiv cs.DC 2009
Year: 2009

The parallel ordering of large graphs is a difficult problem, because on the one hand minimum degree algorithms do not parallelize well, and on the other hand the obtainment of high quality orderings with the nested dissection algorithm requires efficient graph bipartitioning heuristics, the best sequential implementations of which are also hard to parallelize. This paper presents a set of algorithms, implemented in the PT-Scotch software package, which allows one to order large graphs in parallel, yielding orderings the quality of which is only slightly worse than the one of state-of-the-art sequential algorithms. Our implementation uses the classical nested dissection approach but relies on several novel features to solve the parallel graph bipartitioning problem. Thanks to these improvements, PT-Scotch produces consistently better orderings than ParMeTiS on large numbers of processors.
Theoretical Performance Analysis of Eigenvalue-based Detection
Venue: arXiv cs.IT 2009
Year: 2009

In this paper we develop a complete analytical framework based on Random Matrix Theory for the performance evaluation of Eigenvalue-based Detection. While, up to now, analysis was limited to false-alarm probability, we have obtained an analytical expression also for the probability of missed detection, by using the theory of spiked population models. A general scenario with multiple signals present at the same time is considered. The theoretical results of this paper allow to predict the error probabilities, and to set the decision threshold accordingly, by means of a few mathematical formulae. In this way the design of an eigenvalue-based detector is made conceptually identical to that of a traditional energy detector. As additional results, the paper discusses the conditions of signal identifiability for single and multiple sources. All the analytical results are validated through numerical simulations, covering also convergence, identifiabilty and non-Gaussian practical modulations.
Throughput Improvement and Its Tradeoff with The Queuing Delay in the Diamond Relay Networks
Venue: arXiv cs.IT 2009
Year: 2009

Diamond relay channel model, as a basic transmission model, has recently been attracting considerable attention in wireless Ad Hoc networks. Node cooperation and opportunistic scheduling scheme are two important techniques to improve the performance in wireless scenarios. In the paper we consider such a problem how to efficiently combine opportunistic scheduling and cooperative modes in the Rayleigh fading scenarios. To do so, we first compare the throughput of SRP (Spatial Reused Pattern) and AFP (Amplify Forwarding Pattern) in the half-duplex case with the assumption that channel side information is known to all and then come up with a new scheduling scheme. It will that that only switching between SRP and AFP simply does little help to obtain an expected improvement because SRP is always superior to AFP on average due to its efficient spatial reuse. To improve the throughput further, we put forward a new processing strategy in which buffers are employed at both relays in SRP mode. By efficiently utilizing the links with relatively higher gains, the throughput can be greatly improved at a cost of queuing delay. Furthermore, we shall quantitatively evaluate the queuing delay and the tradeoff between the throughput and the additional queuing delay. Finally, to realize our developed strategy and make sure it always run at stable status, we present two criteria and an algorithm on the selection and adjustment of the switching thresholds.
Automated Protein Structure Classification: A Survey
Venue: arXiv cs.CE 2009
Year: 2009

Classification of proteins based on their structure provides a valuable resource for studying protein structure, function and evolutionary relationships. With the rapidly increasing number of known protein structures, manual and semi-automatic classification is becoming ever more difficult and prohibitively slow. Therefore, there is a growing need for automated, accurate and efficient classification methods to generate classification databases or increase the speed and accuracy of semi-automatic techniques. Recognizing this need, several automated classification methods have been developed. In this survey, we overview recent developments in this area. We classify different methods based on their characteristics and compare their methodology, accuracy and efficiency. We then present a few open problems and explain future directions.
Refining interfaces: the case of the B method
Venue: arXiv cs.SE 2009
Year: 2009

Model-driven design of software for safety-critical applications often relies on mathematically grounded techniques such as the B method. Such techniques consist in the successive applications of refinements to derive a concrete implementation from an abstract specification. Refinement theory defines verification conditions to guarantee that such operations preserve the intended behaviour of the abstract specifications. One of these conditions requires however that concrete operations have exactly the same signatures as their abstract counterpart, which is not always a practical requirement. This paper shows how changes of signatures can be achieved while still staying within the bounds of refinement theory. This makes it possible to take advantage of the mathematical guarantees and tool support provided for the current refinement-based techniques, such as the B method.
A Type System For Call-By-Name Exceptions
Venue: arXiv cs.PL 2009
Year: 2009

We present an extension of System F with call-by-name exceptions. The type system is enriched with two syntactic constructs: a union type for programs whose execution may raise an exception at top level, and a corruption type for programs that may raise an exception in any evaluation context (not necessarily at top level). We present the syntax and reduction rules of the system, as well as its typing and subtyping rules. We then study its properties, such as confluence. Finally, we construct a realizability model using orthogonality techniques, from which we deduce that well-typed programs are weakly normalizing and that the ones who have the type of natural numbers really compute a natural number, without raising exceptions.
AWiMA: An architecture for Adhoc Wireless Mobile internet Access
Venue: arXiv cs.NI 2009
Year: 2009

This paper suggests a system architecture for wireless widearea- networking access using adhoc networking between a mobile Client node without direct connectivity to a wirelesswide- area-network and a mobile Service Provider node with connectivity to a wireless-wide-area-network. It provides a means for securely providing such adhoc wireless networking services using a Server for tunneling and routing, registration and authentication. The architecture also provides support for handoff of a Client node from one Service Provider to another with persistence of a tunnel between the Client and the Server enabling a soft-handoff. Different wireless protocols may be used for adhoc networking, with filtered interconnection of authenticated Clients implemented at a Service Provider node. The architecture is applicable across different wide-areanetwork protocols, and provides simultaneous support for multiple wide-area-network protocols.
Cooperation in Subset Team Games: Altruism and Selfishness
Venue: arXiv cs.GT 2009
Year: 2009

This paper extends the theory of subset team games, a generalization of cooperative game theory requiring a payoff function that is defined for all subsets of players. This subset utility is used to define both altruistic and selfish contributions of a player to the team. We investigate properties of these games, and analyze the implications of altruism and selfishness for general situations, for prisoner's dilemma, and for a specific game with a Cobb-Douglas utility.
Decompounding on compact Lie groups
Venue: arXiv cs.IT 2009
Year: 2009

Noncommutative harmonic analysis is used to solve a nonparametric estimation problem stated in terms of compound Poisson processes on compact Lie groups. This problem of decompounding is a generalization of a similar classical problem. The proposed solution is based on a char- acteristic function method. The treated problem is important to recent models of the physical inverse problem of multiple scattering.
Homogeneous formulas and symmetric polynomials
Venue: arXiv cs.CC 2009
Year: 2009

We investigate the arithmetic formula complexity of the elementary symmetric polynomials S(k,n). We show that every multilinear homogeneous formula computing S(k,n) has size at least k^(Omega(log k))n, and that product-depth d multilinear homogeneous formulas for S(k,n) have size at least 2^(Omega(k^{1/d}))n. Since S(n,2n) has a multilinear formula of size O(n^2), we obtain a superpolynomial separation between multilinear and multilinear homogeneous formulas. We also show that S(k,n) can be computed by homogeneous formulas of size k^(O(log k))n, answering a question of Nisan and Wigderson. Finally, we present a superpolynomial separation between monotone and non-monotone formulas in the noncommutative setting, answering a question of Nisan.
Finding Fullerene Patches in Polynomial Time
Venue: arXiv cs.DM 2009
Year: 2009

We consider the following question, motivated by the enumeration of fullerenes. A fullerene patch is a 2-connected plane graph G in which inner faces have length 5 or 6, non-boundary vertices have degree 3, and boundary vertices have degree 2 or 3. The degree sequence along the boundary is called the boundary code of G. We show that the question whether a given sequence S is a boundary code of some fullerene patch can be answered in polynomial time when such patches have at most five 5-faces. We conjecture that our algorithm gives the correct answer for any number of 5-faces, and sketch how to extend the algorithm to the problem of counting the number of different patches with a given boundary code.
General Spectrum Sensing in Cognitive Radio Networks
Venue: arXiv cs.IT 2009
Year: 2009

The successful operation of cognitive radio (CR) between CR transmitter and CR receiver (CR link) relies on reliable spectrum sensing. To network CRs requires spectrum sensing at CR transmitter and further information regarding the spectrum availability at CR receiver. Redefining the spectrum sensing along with statistical inference suitable for cognitive radio networks (CRN), we mathematically derive conditions to allow CR transmitter forwarding packets to CR receiver under guaranteed outage probability, and prove that the correlation of localized spectrum availability between a cooperative node and CR receiver determines effectiveness of the cooperative scheme. Applying our novel mathematical model to potential hidden terminals in CRN, we illustrate that the allowable transmission region of a CR, defined as neighborhood, is no longer circular shape even in a pure path loss channel model. This results in asymmetric CR links to make bidirectional links generally inappropriate in CRN, though this challenge can be alleviated by cooperative sensing. Therefore, spectrum sensing capability determines CRN topology. For multiple cooperative nodes, to fully utilize spectrum availability, the selection methodology of cooperative nodes is developed due to limited overhead of information exchange. Defining reliability as information of spectrum availability at CR receiver provided by a cooperative node and by applying neighborhood area, we can compare sensing capability of cooperative nodes from both link and network perspectives. In addition, due to lack of centralized coordination in dynamic CRN, CRs can only acquire local and partial information within limited sensing duration, robust spectrum sensing is therefore proposed. Limits of cooperative schemes and their impacts on network operation are also derived.
4G Wireless Networks: Opportunities and Challenges
Venue: arXiv cs.NI 2009
Year: 2009

With the major wireless service providers planning to start deployment of 4G wireless networks by mid 2010, research and industry communities are racing against time to find solutions for some of the prominent still open issues in 4G networks. The growing interest in 4G networks is driven by the set of new services will be made available for the first time such as accessing the Internet anytime from anywhere, global roaming, and wider support for multimedia applications. In this paper describe some of the key opportunities will be made available by 4G networks, present key challenges and point to some proposed solutions.
The Single Machine Total Weighted Tardiness Problem - Is it (for Metaheuristics) a Solved Problem ?
Venue: arXiv cs.AI 2009
Year: 2009

The article presents a study of rather simple local search heuristics for the single machine total weighted tardiness problem (SMTWTP), namely hillclimbing and Variable Neighborhood Search. In particular, we revisit these approaches for the SMTWTP as there appears to be a lack of appropriate/challenging benchmark instances in this case. The obtained results are impressive indeed. Only few instances remain unsolved, and even those are approximated within 1% of the optimal/best known solutions. Our experiments support the claim that metaheuristics for the SMTWTP are very likely to lead to good results, and that, before refining search strategies, more work must be done with regard to the proposition of benchmark data. Some recommendations for the construction of such data sets are derived from our investigations.
Graph Theory and Optimization Problems for Very Large Networks
Venue: arXiv cs.NI 2009
Year: 2009

Graph theory provides a primary tool for analyzing and designing computer communication networks. In the past few decades, Graph theory has been used to study various types of networks, including the Internet, wide Area Networks, Local Area Networks, and networking protocols such as border Gateway Protocol, Open shortest Path Protocol, and Networking Networks. In this paper, we present some key graph theory concepts used to represent different types of networks. Then we describe how networks are modeled to investigate problems related to network protocols. Finally, we present some of the tools used to generate graph for representing practical networks.
Population Protocols that Correspond to Symmetric Games
Venue: arXiv cs.GT 2009
Year: 2009

Population protocols have been introduced by Angluin et {al.} as a model of networks consisting of very limited mobile agents that interact in pairs but with no control over their own movement. A collection of anonymous agents, modeled by finite automata, interact pairwise according to some rules that update their states. The model has been considered as a computational model in several papers. Input values are initially distributed among the agents, and the agents must eventually converge to the the correct output. Predicates on the initial configurations that can be computed by such protocols have been characterized under various hypotheses. In an orthogonal way, several distributed systems have been termed in literature as being realizations of games in the sense of game theory. In this paper, we investigate under which conditions population protocols, or more generally pairwise interaction rules, can be considered as the result of a symmetric game. We prove that not all rules can be considered as symmetric games.% We prove that some basic protocols can be realized using symmetric games. As a side effect of our study, we also prove that any population protocol can be simulated by a symmetric one (but not necessarily a game).
Fully Automatic 3D Reconstruction of Histological Images
Venue: arXiv cs.CV 2009
Year: 2009

In this paper, we propose a computational framework for 3D volume reconstruction from 2D histological slices using registration algorithms in feature space. To improve the quality of reconstructed 3D volume, first, intensity variations in images are corrected by an intensity standardization process which maps image intensity scale to a standard scale where similar intensities correspond to similar tissues. Second, a subvolume approach is proposed for 3D reconstruction by dividing standardized slices into groups. Third, in order to improve the quality of the reconstruction process, an automatic best reference slice selection algorithm is developed based on an iterative assessment of image entropy and mean square error of the registration process. Finally, we demonstrate that the choice of the reference slice has a significant impact on registration quality and subsequent 3D reconstruction.
Inter Genre Similarity Modelling For Automatic Music Genre Classification
Venue: arXiv cs.SD 2009
Year: 2009

Music genre classification is an essential tool for music information retrieval systems and it has been finding critical applications in various media platforms. Two important problems of the automatic music genre classification are feature extraction and classifier design. This paper investigates inter-genre similarity modelling (IGS) to improve the performance of automatic music genre classification. Inter-genre similarity information is extracted over the mis-classified feature population. Once the inter-genre similarity is modelled, elimination of the inter-genre similarity reduces the inter-genre confusion and improves the identification rates. Inter-genre similarity modelling is further improved with iterative IGS modelling(IIGS) and score modelling for IGS elimination(SMIGS). Experimental results with promising classification improvements are provided.
Gentzen-Prawitz Natural Deduction as a Teaching Tool
Venue: arXiv cs.LO 2009
Year: 2009

We report a four-years experiment in teaching reasoning to undergraduate students, ranging from weak to gifted, using Gentzen-Prawitz's style natural deduction. We argue that this pedagogical approach is a good alternative to the use of Boolean algebra for teaching reasoning, especially for computer scientists and formal methods practionners.
Image Sampling with Quasicrystals
Venue: arXiv cs.CV 2009
Year: 2009

We investigate the use of quasicrystals in image sampling. Quasicrystals produce space-filling, non-periodic point sets that are uniformly discrete and relatively dense, thereby ensuring the sample sites are evenly spread out throughout the sampled image. Their self-similar structure can be attractive for creating sampling patterns endowed with a decorative symmetry. We present a brief general overview of the algebraic theory of cut-and-project quasicrystals based on the geometry of the golden ratio. To assess the practical utility of quasicrystal sampling, we evaluate the visual effects of a variety of non-adaptive image sampling strategies on photorealistic image reconstruction and non-photorealistic image rendering used in multiresolution image representations. For computer visualization of point sets used in image sampling, we introduce a mosaic rendering technique.
Decidability of higher-order matching
Venue: arXiv cs.LO 2009
Year: 2009

We show that the higher-order matching problem is decidable using a game-theoretic argument.
A Secure Wireless Routing Protocol Using Enhanced Chain Signatures
Venue: arXiv cs.CR 2009
Year: 2009

We propose a routing protocol for wireless networks. Wireless routing protocols allow hosts within a network to have some knowledge of the topology in order to know when to forward a packet (via broadcast) and when to drop it. Since a routing protocol forms the backbone of a network, it is a lucrative target for many attacks, all of which attempt to disrupt network traffic by corrupting routing tables of neighboring routers using false updates. Secure routing protocols designed for wired networks (such as S-BGP) are not scalable in an ad-hoc wireless environment because of two main drawbacks: (1) the need to maintain knowledge about all immediate neighbors (which requires a discovery protocol), and (2) the need to transmit the same update several times, one for each neighbor. Although information about neighbors is readily available in a fairly static and wired network, such information is often not updated or available in an ad-hoc wireless network with mobile devices. Our protocol is a variant of S-BGP called SS-BGP and allows a single broadcast for routing updates without having the need to be aware of every neighboring router. The protocol is based on a novel authentication primitive called Enhanced Chain Signatures (ECS).