OpenRaiser/Intern-Atlas huggingface dataset:
The Gaussian Many-to-1 Interference Channel with Confidential Messages
Venue: arXiv cs.IT 2010
Year: 2010

The many-to-one interference channel has received interest by virtue of embodying the essence of an interference network while being more tractable than the general K-user interference channel. In this paper, we introduce information theoretic secrecy to this model and consider the many-to-one interference channel with confidential messages, in which each receiver, in particular, the one subject to interference, is also one from which the interfering users' messages need to be kept secret from. We derive the achievable secrecy sum rate for this channel using nested lattice codes, as well as an upper bound on the secrecy sum rate for all possible channel gain configurations. We identify several nontrivial cases where the gap between the upper bound and the achieved secrecy sum rate is only a function of the number of the users K, and is uniform over all possible channel gain configurations in each case. In addition, we identify the secure degree of freedom for this channel and show it to be equivalent to its degree of freedom, i.e., the secrecy in high SNR comes for free.
The B-Skip-List: A Simpler Uniquely Represented Alternative to B-Trees
Venue: arXiv cs.DS 2010
Year: 2010

In previous work, the author introduced the B-treap, a uniquely represented B-tree analogue, and proved strong performance guarantees for it. However, the B-treap maintains complex invariants and is very complex to implement. In this paper we introduce the B-skip-list, which has most of the guarantees of the B-treap, but is vastly simpler and easier to implement. Like the B-treap, the B-skip-list may be used to construct strongly history-independent index structures and filesystems; such constructions reveal no information about the historical sequence of operations that led to the current logical state. For example, a uniquely represented filesystem would support the deletion of a file in a way that, in a strong information-theoretic sense, provably removes all evidence that the file ever existed. Like the B-tree, the B-skip-list has depth O(log_B (n)) where B is the block transfer size of the external memory, uses linear space with high probability, and supports efficient one-dimensional range queries.
A Linear-time Algorithm for Sparsification of Unweighted Graphs
Venue: arXiv cs.DS 2010
Year: 2010

Given an undirected graph $G$ and an error parameter $ε> 0$, the {\em graph sparsification} problem requires sampling edges in $G$ and giving the sampled edges appropriate weights to obtain a sparse graph $G_ε$ with the following property: the weight of every cut in $G_ε$ is within a factor of $(1\pm ε)$ of the weight of the corresponding cut in $G$. If $G$ is unweighted, an $O(m\log n)$-time algorithm for constructing $G_ε$ with $O(n\log n/ε^2)$ edges in expectation, and an $O(m)$-time algorithm for constructing $G_ε$ with $O(n\log^2 n/ε^2)$ edges in expectation have recently been developed (Hariharan-Panigrahi, 2010). In this paper, we improve these results by giving an $O(m)$-time algorithm for constructing $G_ε$ with $O(n\log n/ε^2)$ edges in expectation, for unweighted graphs. Our algorithm is optimal in terms of its time complexity; further, no efficient algorithm is known for constructing a sparser $G_ε$. Our algorithm is Monte-Carlo, i.e. it produces the correct output with high probability, as are all efficient graph sparsification algorithms.
From Skew-Cyclic Codes to Asymmetric Quantum Codes
Venue: arXiv cs.IT 2010
Year: 2010

We introduce an additive but not $\mathbb{F}_4$-linear map $S$ from $\mathbb{F}_4^{n}$ to $\mathbb{F}_4^{2n}$ and exhibit some of its interesting structural properties. If $C$ is a linear $[n,k,d]_4$-code, then $S(C)$ is an additive $(2n,2^{2k},2d)_4$-code. If $C$ is an additive cyclic code then $S(C)$ is an additive quasi-cyclic code of index $2$. Moreover, if $C$ is a module $θ$-cyclic code, a recently introduced type of code which will be explained below, then $S(C)$ is equivalent to an additive cyclic code if $n$ is odd and to an additive quasi-cyclic code of index $2$ if $n$ is even. Given any $(n,M,d)_4$-code $C$, the code $S(C)$ is self-orthogonal under the trace Hermitian inner product. Since the mapping $S$ preserves nestedness, it can be used as a tool in constructing additive asymmetric quantum codes.
Structural Solutions For Additively Coupled Sum Constrained Games
Venue: arXiv cs.GT 2010
Year: 2010

We propose and analyze a broad family of games played by resource-constrained players, which are characterized by the following central features: 1) each user has a multi-dimensional action space, subject to a single sum resource constraint; 2) each user's utility in a particular dimension depends on an additive coupling between the user's action in the same dimension and the actions of the other users; and 3) each user's total utility is the sum of the utilities obtained in each dimension. Familiar examples of such multi-user environments in communication systems include power control over frequency-selective Gaussian interference channels and flow control in Jackson networks. In settings where users cannot exchange messages in real-time, we study how users can adjust their actions based on their local observations. We derive sufficient conditions under which a unique Nash equilibrium exists and the best-response algorithm converges globally and linearly to the Nash equilibrium. In settings where users can exchange messages in real-time, we focus on user choices that optimize the overall utility. We provide the convergence conditions of two distributed action update mechanisms, gradient play and Jacobi update.
Buffer Management Algorithm Design and Implementation Based on Network Processors
Venue: arXiv cs.NI 2010
Year: 2010

To solve the parameter sensitive issue of the traditional RED (random early detection) algorithm, an adaptive buffer management algorithm called PAFD (packet adaptive fair dropping) is proposed. This algorithm supports DiffServ (differentiated services) model of QoS (quality of service). In this algorithm, both of fairness and throughput are considered. The smooth buffer occupancy rate function is adopted to adjust the parameters. By implementing buffer management and packet scheduling on Intel IXP2400, the viability of QoS mechanisms on NPs (network processors) is verified. The simulation shows that the PAFD smoothes the flow curve, and achieves better balance between fairness and network throughput. It also demonstrates that this algorithm meets the requirements of fast data packet processing, and the hardware resource utilization of NPs is higher.
George Forsythe's last paper
Venue: arXiv cs.NA 2010
Year: 2010

We describe von Neumann's elegant idea for sampling from the exponential distribution, Forsythe's generalization for sampling from a probability distribution whose density has the form exp(-G(x)), where G(x) is easy to compute (e.g. a polynomial), and my refinement of these ideas to give an efficient algorithm for generating pseudo-random numbers with a normal distribution. Later developments are also mentioned.
Tunable Multifunction Filter Using Current Conveyor
Venue: arXiv cs.OH 2010
Year: 2010

The paper presents a current tunable multifunction filter using current conveyor. The proposed circuit can be realized as on chip tunable low pass, high pass, band pass and elliptical notch filter. The circuit employs two current conveyors, one OTA, four resistors and two grounded capacitors, ideal for integration. It has only one output terminal and the number of input terminals may be used. Further, there is no requirement for component matching in the circuit. The resonance frequency (ω0) and bandwidth (ω0 /Q) enjoy orthogonal tuning. The cutoff frequency of the filter is tunable by changing the bias current, which makes it on chip tunable filter. The circuit is realized by using commercially available current conveyor AD844 and OTA LM13700. A HSPICE simulation of circuit is also studied for the verification of theoretical results.
Round-Trip Voronoi Diagrams and Doubling Density in Geographic Networks
Venue: arXiv cs.DS 2010
Year: 2010

The round-trip distance function on a geographic network (such as a road network, flight network, or utility distribution grid) defines the "distance" from a single vertex to a pair of vertices as the minimum length tour visiting all three vertices and ending at the starting vertex. Given a geographic network and a subset of its vertices called "sites" (for example a road network with a list of grocery stores), a two-site round-trip Voronoi diagram labels each vertex in the network with the pair of sites that minimizes the round-trip distance from that vertex. Alternatively, given a geographic network and two sets of sites of different types (for example grocery stores and coffee shops), a two-color round-trip Voronoi diagram labels each vertex with the pair of sites of different types minimizing the round-trip distance. In this paper, we prove several new properties of two-site and two-color round-trip Voronoi diagrams in a geographic network, including a relationship between the "doubling density" of sites and an upper bound on the number of non-empty Voronoi regions. We show how those lemmas can be used in new algorithms asymptotically more efficient than previous known algorithms when the networks have reasonable distribution properties related to doubling density, and we provide experimental data suggesting that road networks with standard point-of-interest sites have these properties.
Coordination and Bargaining over the Gaussian Interference Channel
Venue: arXiv cs.IT 2010
Year: 2010

This work considers coordination and bargaining between two selfish users over a Gaussian interference channel using game theory. The usual information theoretic approach assumes full cooperation among users for codebook and rate selection. In the scenario investigated here, each selfish user is willing to coordinate its actions only when an incentive exists and benefits of cooperation are fairly allocated. To improve communication rates, the two users are allowed to negotiate for the use of a simple Han-Kobayashi type scheme with fixed power split and conditions for which users have incentives to cooperate are identified. The Nash bargaining solution (NBS) is used as a tool to get fair information rates. The operating point is obtained as a result of an optimization problem and compared with a TDM-based one in the literature.
Quantum Complexity: restrictions on algorithms and architectures
Venue: arXiv cs.CC 2010
Year: 2010

A dissertation submitted to the University of Bristol in accordance with the requirements of the degree of Doctor of Philosophy (PhD) in the Faculty of Engineering, Department of Computer Science, July 2009.
Classification via Incoherent Subspaces
Venue: arXiv cs.CV 2010
Year: 2010

This article presents a new classification framework that can extract individual features per class. The scheme is based on a model of incoherent subspaces, each one associated to one class, and a model on how the elements in a class are represented in this subspace. After the theoretical analysis an alternate projection algorithm to find such a collection is developed. The classification performance and speed of the proposed method is tested on the AR and YaleB databases and compared to that of Fisher's LDA and a recent approach based on on $\ell_1$ minimisation. Finally connections of the presented scheme to already existing work are discussed and possible ways of extensions are pointed out.
Computation using Noise-based Logic: Efficient String Verification over a Slow Communication Channel
Venue: arXiv cs.IT 2010
Year: 2010

Utilizing the hyperspace of noise-based logic, we show two string verification methods with low communication complexity. One of them is based on continuum noise-based logic. The other one utilizes noise-based logic with random telegraph signals where a mathematical analysis of the error probability is also given. The last operation can also be interpreted as computing universal hash functions with noise-based logic and using them for string comparison. To find out with 10^-25 error probability that two strings with arbitrary length are different (this value is similar to the error probability of an idealistic gate in today's computer) Alice and Bob need to compare only 83 bits of the noise-based hyperspace.
Interference Alignment in Regenerating Codes for Distributed Storage: Necessity and Code Constructions
Venue: arXiv cs.IT 2010
Year: 2010

Regenerating codes are a class of recently developed codes for distributed storage that, like Reed-Solomon codes, permit data recovery from any arbitrary k of n nodes. However regenerating codes possess in addition, the ability to repair a failed node by connecting to any arbitrary d nodes and downloading an amount of data that is typically far less than the size of the data file. This amount of download is termed the repair bandwidth. Minimum storage regenerating (MSR) codes are a subclass of regenerating codes that require the least amount of network storage; every such code is a maximum distance separable (MDS) code. Further, when a replacement node stores data identical to that in the failed node, the repair is termed as exact. The four principal results of the paper are (a) the explicit construction of a class of MDS codes for d = n-1 >= 2k-1 termed the MISER code, that achieves the cut-set bound on the repair bandwidth for the exact-repair of systematic nodes, (b) proof of the necessity of interference alignment in exact-repair MSR codes, (c) a proof showing the impossibility of constructing linear, exact-repair MSR codes for d < 2k-3 in the absence of symbol extension, and (d) the construction, also explicit, of MSR codes for d = k+1. Interference alignment (IA) is a theme that runs throughout the paper: the MISER code is built on the principles of IA and IA is also a crucial component to the non-existence proof for d < 2k-3. To the best of our knowledge, the constructions presented in this paper are the first, explicit constructions of regenerating codes that achieve the cut-set bound.
Advanced Radio Resource Management for Multi Antenna Packet Radio Systems
Venue: arXiv cs.NI 2010
Year: 2010

In this paper, we propose fairness-oriented packet scheduling (PS) schemes with power-efficient control mechanism for future packet radio systems. In general, the radio resource management functionality plays an important role in new OFDMA based networks. The control of the network resource division among the users is performed by packet scheduling functionality based on maximizing cell coverage and capacity satisfying, and certain quality of service requirements. Moreover, multiantenna transmit-receive schemes provide additional flexibility to packet scheduler functionality. In order to mitigate inter-cell and co-channel interference problems in OFDMA cellular networks soft frequency reuse with different power masks patterns is used. Stemming from the earlier enhanced proportional fair scheduler studies for single-input multiple-output (SIMO) and multiple-input multipleoutput (MIMO) systems, we extend the development of efficient packet scheduling algorithms by adding transmit power considerations in the overall priority metrics calculations and scheduling decisions. Furthermore, we evaluate the proposed scheduling schemes by simulating practical orthogonal frequency division multiple access (OFDMA) based packet radio system in terms of throughput, coverage and fairness distribution among users. As a concrete example, under reduced overall transmit power constraint and unequal power distribution for different sub-bands, we demonstrate that by using the proposed power-aware multi-user scheduling schemes, significant coverage and fairness improvements in the order of 70% and 20%, respectively, can be obtained, at the expense of average throughput loss of only 15%.
Lattice model refinement of protein structures
Venue: arXiv cs.CE 2010
Year: 2010

To find the best lattice model representation of a given full atom protein structure is a hard computational problem. Several greedy methods have been suggested where results are usually biased and leave room for improvement. In this paper we formulate and implement a Constraint Programming method to refine such lattice structure models. We show that the approach is able to provide better quality solutions. The prototype is implemented in COLA and is based on limited discrepancy search. Finally, some promising extensions based on local search are discussed.
Information Hiding Using Improper Frame Padding
Venue: arXiv cs.CR 2010
Year: 2010

Hiding information in network traffic may lead to leakage of confidential information. In this paper we introduce a new steganographic system: the PadSteg (Padding Steganography). To authors' best knowledge it is the first information hiding solution which represents interprotocol steganography i.e. usage of relation between two or more protocols from the TCP/IP stack to enable secret communication. PadSteg utilizes ARP and TCP protocols together with an Etherleak vulnerability (improper Ethernet frame padding) to facilitate secret communication for hidden groups in LANs (Local Area Networks). Basing on real network traces we confirm that PadSteg is feasible in today's networks and we estimate what steganographic bandwidth is achievable while limiting the chance of disclosure. We also point at possible countermeasures against PadSteg.
Scalable Probabilistic Databases with Factor Graphs and MCMC
Venue: arXiv cs.DB 2010
Year: 2010

Probabilistic databases play a crucial role in the management and understanding of uncertain data. However, incorporating probabilities into the semantics of incomplete databases has posed many challenges, forcing systems to sacrifice modeling power, scalability, or restrict the class of relational algebra formula under which they are closed. We propose an alternative approach where the underlying relational database always represents a single world, and an external factor graph encodes a distribution over possible worlds; Markov chain Monte Carlo (MCMC) inference is then used to recover this uncertainty to a desired level of fidelity. Our approach allows the efficient evaluation of arbitrary queries over probabilistic databases with arbitrary dependencies expressed by graphical models with structure that changes during inference. MCMC sampling provides efficiency by hypothesizing {\em modifications} to possible worlds rather than generating entire worlds from scratch. Queries are then run over the portions of the world that change, avoiding the onerous cost of running full queries over each sampled world. A significant innovation of this work is the connection between MCMC sampling and materialized view maintenance techniques: we find empirically that using view maintenance techniques is several orders of magnitude faster than naively querying each sampled world. We also demonstrate our system's ability to answer relational queries with aggregation, and demonstrate additional scalability through the use of parallelization.
A Multi-agent Framework for Performance Tuning in Distributed Environment
Venue: arXiv cs.DC 2010
Year: 2010

This paper presents the overall design of a multi-agent framework for tuning the performance of an application executing in a distributed environment. The multi-agent framework provides services like resource brokering, analyzing performance monitoring data, local tuning and also rescheduling in case of any performance problem on a specific resource provider. The paper also briefly describes the implementation of some part of the framework. In particular, job migration on the basis of performance monitoring data is particularly highlighted in this paper.
An Integrated Framework for Performance Analysis and Tuning in Grid Environment
Venue: arXiv cs.DC 2010
Year: 2010

In a heterogeneous, dynamic environment, like Grid, post-mortem analysis is of no use and data needs to be collected and analysed in real time. Novel techniques are also required for dynamically tuning the application's performance and resource brokering in order to maintain the desired QoS. The objective of this paper is to propose an integrated framework for performance analysis and tuning of the application, and rescheduling the application, if necessary, to some other resources in order to adapt to the changing resource usage scenario in a dynamic environment.
Arboricity, h-Index, and Dynamic Algorithms
Venue: arXiv cs.DS 2010
Year: 2010

In this paper we present a modification of a technique by Chiba and Nishizeki [Chiba and Nishizeki: Arboricity and Subgraph Listing Algorithms, SIAM J. Comput. 14(1), pp. 210--223 (1985)]. Based on it, we design a data structure suitable for dynamic graph algorithms. We employ the data structure to formulate new algorithms for several problems, including counting subgraphs of four vertices, recognition of diamond-free graphs, cop-win graphs and strongly chordal graphs, among others. We improve the time complexity for graphs with low arboricity or h-index.
Worldwide topology of the scientific subject profile: a macro approach on the country level
Venue: arXiv cs.DL 2010
Year: 2010

Models for the production of knowledge and systems of innovation and science are key elements for characterizing a country in view of its scientific thematic profile. With regard to scientific output and publication in journals of international visibility, the countries of the world may be classified into three main groups according to their thematic bias. This paper aims to classify the countries of the world in several broad groups, described in terms of behavioural models that attempt to sum up the characteristics of their systems of knowledge and innovation. We perceive three clusters in our analysis: 1) the biomedical cluster, 2) the basic science & engineering cluster, and 3) the agricultural cluster. The countries are conceptually associated with the clusters via Principal Component Analysis (PCA), and a Multidimensional Scaling (MDS) map with all the countries is presented.
A Fast Compressive Channel Estimation with Modified Smoothed L0 Algorithm
Venue: arXiv cs.IT 2010
Year: 2010

Broadband wireless channel is a time dispersive and becomes strongly frequency selective. In most cases, the channel is composed of a few dominant coefficients and a large part of coefficients is approximately zero or zero. To exploit the sparsity of multi-path channel (MPC), there are various methods have been proposed. They are, namely, greedy algorithms, iterative algorithms, and convex program. The former two algorithms are easy to be implemented but not stable; on the other hand, the last method is stable but difficult to be implemented as practical channel estimation problems because of computational complexity. In this paper, we proposed a novel channel estimation strategy by using modified smoothed (MSL0) algorithm which combines stable and low complexity. Computer simulations confirm the effectiveness of the introduced algorithm comparisons with the existing methods. We also give
Likelihood that a pseudorandom sequence generator has optimal properties
Venue: arXiv cs.CR 2010
Year: 2010

The authors prove that the probability of choosing a nonlinear filter of m-sequences with optimal properties, that is, maximum period and maximum linear complexity, tends assymptotically to 1 as the linear feedback shift register length increases.
Some comments on C. S. Wallace's random number generators
Venue: arXiv cs.MS 2010
Year: 2010

We outline some of Chris Wallace's contributions to pseudo-random number generation. In particular, we consider his idea for generating normally distributed variates without relying on a source of uniform random numbers, and compare it with more conventional methods for generating normal random numbers. Implementations of Wallace's idea can be very fast (approximately as fast as good uniform generators). We discuss the statistical quality of the output, and mention how certain pitfalls can be avoided.