OpenRaiser/Intern-Atlas huggingface dataset:
A Multi-Interference-Channel Matrix Pair Beamformer for CDMA Systems
Venue: arXiv cs.CE 2010
Year: 2010

Matrix pair beamformer (MPB) is a promising blind beamformer which exploits the temporal signature of the signal of interest (SOI) to acquire its spatial statistical information. It does not need any knowledge of directional information or training sequences. However, the major problem of the existing MPBs is that they have serious threshold effects and the thresholds will grow as the interference power increases or even approach infinity. In particular, this issue prevails in scenarios with structured interference, such as, periodically repeated white noise, tones, or MAIs in multipath channels. In this paper, we will first present the principles for designing the projection space of the MPB which are closely correlated with the ability of suppressing structured interference and system finite sample performance. Then a multiple-interference-channel based matrix pair beamformer (MIC-MPB) for CDMA systems is developed according to the principles. In order to adapt to dynamic channels, an adaptive algorithm for the beamformer is also proposed. Theoretical analysis and simulation results show that the proposed beamformer has a small and bounded threshold when the interference power increases. Performance comparisons of the MIC-MPB and the existing MPBs in various scenarios via a number of numerical examples are also presented.
Efficient Knowledge Base Management in DCSP
Venue: arXiv cs.AI 2010
Year: 2010

DCSP (Distributed Constraint Satisfaction Problem) has been a very important research area in AI (Artificial Intelligence). There are many application problems in distributed AI that can be formalized as DSCPs. With the increasing complexity and problem size of the application problems in AI, the required storage place in searching and the average searching time are increasing too. Thus, to use a limited storage place efficiently in solving DCSP becomes a very important problem, and it can help to reduce searching time as well. This paper provides an efficient knowledge base management approach based on general usage of hyper-resolution-rule in consistence algorithm. The approach minimizes the increasing of the knowledge base by eliminate sufficient constraint and false nogood. These eliminations do not change the completeness of the original knowledge base increased. The proofs are given as well. The example shows that this approach decrease both the new nogoods generated and the knowledge base greatly. Thus it decreases the required storage place and simplify the searching process.
Channel Coding over Multiple Coherence Blocks with Queueing Constraints
Venue: arXiv cs.IT 2010
Year: 2010

This paper investigates the performance of wireless systems that employ finite-blocklength channel codes for transmission and operate under queueing constraints in the form of limitations on buffer overflow probabilities. A block fading model, in which fading stays constant in each coherence block and change independently between blocks, is considered. It is assumed that channel coding is performed over multiple coherence blocks. An approximate lower bound on the transmission rate is obtained from Feintein's Lemma. This lower bound is considered as the service rate and is incorporated into the effective capacity formulation, which characterizes the maximum constant arrival rate that can be supported under statistical queuing constraints. Performances of variable-rate and fixed-rate transmissions are studied. The optimum error probability for variable rate transmission and the optimum coding rate for fixed rate transmission are shown to be unique. Moreover, the tradeoff between the throughput and the number of blocks over which channel coding is performed is identified.
Implementing Lego Agents Using Jason
Venue: arXiv cs.MA 2010
Year: 2010

Since many of the currently available multi-agent frameworks are generally mostly intended for research, it can be difficult to built multi-agent systems using physical robots. In this report I describe a way to combine the multi-agent framework Jason, an extended version of the agent-oriented programming language AgentSpeak, with Lego robots to address this problem. By extending parts of the Jason reasoning cycle I show how Lego robots are able to complete tasks such as following lines on a floor and communicating to be able to avoid obstacles with minimal amount of coding. The final implementation is a functional extension that is able to built multi-agent systems using Lego agents, however there are some issues that have not been addressed. If the agents are highly dependent on percepts from their sensors, they are required to move quite slowly, because there currently is a high delay in the reasoning cycle, when it is combined with a robot. Overall the system is quite robust and can be used to make simple Lego robots perform tasks of an advanced agent in a multi-agent environment.
Reed-Muller Codes for Peak Power Control in Multicarrier CDMA
Venue: arXiv cs.IT 2010
Year: 2010

Reed-Muller codes are studied for peak power control in multicarrier code-division multiple access (MC-CDMA) communication systems. In a coded MC-CDMA system, the information data multiplexed from users is encoded by a Reed-Muller subcode and the codeword is fully-loaded to Walsh-Hadamard spreading sequences. The polynomial representation of a coded MC-CDMA signal is established for theoretical analysis of the peak-to-average power ratio (PAPR). The Reed-Muller subcodes are defined in a recursive way by the Boolean functions providing the transmitted MC-CDMA signals with the bounded PAPR as well as the error correction capability. A connection between the code rates and the maximum PAPR is theoretically investigated in the coded MC-CDMA. Simulation results present the statistical evidence that the PAPR of the coded MC-CDMA signal is not only theoretically bounded, but also statistically reduced. In particular, the coded MC-CDMA solves the major PAPR problem of uncoded MC-CDMA by dramatically reducing its PAPR for the small number of users. Finally, the theoretical and statistical studies show that the Reed-Muller subcodes are effective coding schemes for peak power control in MC-CDMA with small and moderate numbers of users, subcarriers, and spreading factors.
Two-User Gaussian Interference Channel with Finite Constellation Input and FDMA
Venue: arXiv cs.IT 2010
Year: 2010

In the two-user Gaussian Strong Interference Channel (GSIC) with finite constellation inputs, it is known that relative rotation between the constellations of the two users enlarges the Constellation Constrained (CC) capacity region. In this paper, a metric for finding the approximate angle of rotation (with negligibly small error) to maximally enlarge the CC capacity for the two-user GSIC is presented. In the case of Gaussian input alphabets with equal powers for both the users and the modulus of both the cross-channel gains being equal to unity, it is known that the FDMA rate curve touches the capacity curve of the GSIC. It is shown that, with unequal powers for both the users also, when the modulus of one of the cross-channel gains being equal to one and the modulus of the other cross-channel gain being greater than or equal to one, the FDMA rate curve touches the capacity curve of the GSIC. On the contrary, it is shown that, under finite constellation inputs, with both the users using the same constellation, the FDMA rate curve strictly lies within (never touches) the enlarged CC capacity region throughout the strong-interference regime. This means that using FDMA it is impossible to go close to the CC capacity. It is well known that for the Gaussian input alphabets, the FDMA inner-bound, at the optimum sum-rate point, is always better than the simultaneous-decoding inner-bound throughout the weak-interference regime. For a portion of the weak interference regime, it is shown that with identical finite constellation inputs for both the users, the simultaneous-decoding inner-bound, enlarged by relative rotation between the constellations, is strictly better than the FDMA inner-bound.
On TCP-based Session Initiation Protocol (SIP) Server Overload Control
Venue: arXiv cs.NI 2010
Year: 2010

The Session Initiation Protocol (SIP) server overload management has attracted interest since SIP is being widely deployed in the Next Generation Networks (NGN) as a core signaling protocol. Yet all existing SIP overload control work is focused on SIP-over-UDP, despite the fact that TCP is increasingly seen as the more viable choice of SIP transport. This paper answers the following questions: is the existing TCP flow control capable of handling the SIP overload problem? If not, why and how can we make it work? We provide a comprehensive explanation of the default SIP-over-TCP overload behavior through server instrumentation. We also propose and implement novel but simple overload control algorithms without any kernel or protocol level modification. Experimental evaluation shows that with our mechanism the overload performance improves from its original zero throughput to nearly full capacity. Our work leads to the important general insight that the traditional notion of TCP flow control alone is incapable of managing overload for time-critical session-based applications, which would be applicable not only to SIP, but also to a wide range of other common applications such as database servers.
A New Approach in Packet Scheduling in the Vanet
Venue: arXiv cs.NI 2010
Year: 2010

Vehicular Ad hoc Networks (VANET) are expected to have great potential to improve both traffic safety and comfort in the future. When many vehicles want to access data through roadside unit, data scheduling become an important issue. In this paper, we identify some challenges in roadside based data access. To address these challenges we first review some existing scheduling schemes. We then propose a priority scheduling and finally show that using this idea can increase QOS compare to previous algorithms.
Strong direct product conjecture holds for all relations in public coin randomized one-way communication complexity
Venue: arXiv cs.CC 2010
Year: 2010

Let f subset of X x Y x Z be a relation. Let the public coin one-way communication complexity of f, with worst case error 1/3, be denoted R^{1,pub}_{1/3}(f). We show that if for computing f^k (k independent copies of f), o(k R^{1,pub}_{1/3}(f)) communication is provided, then the success is exponentially small in k. This settles the strong direct product conjecture for all relations in public coin one-way communication complexity. We show a new tight characterization of public coin one-way communication complexity which strengthens on the tight characterization shown in [J., Klauck, Nayak 08]. We use the new characterization to show our direct product result and this may also be of independent interest.
Analyzing Network Coding Gossip Made Easy
Venue: arXiv cs.DC 2010
Year: 2010

We give a new technique to analyze the stopping time of gossip protocols that are based on random linear network coding (RLNC). Our analysis drastically simplifies, extends and strengthens previous results. We analyze RLNC gossip in a general framework for network and communication models that encompasses and unifies the models used previously in this context. We show, in most settings for the first time, that it converges with high probability in the information-theoretically optimal time. Most stopping times are of the form O(k + T) where k is the number of messages to be distributed and T is the time it takes to disseminate one message. This means RLNC gossip achieves "perfect pipelining". Our analysis directly extends to highly dynamic networks in which the topology can change completely at any time. This remains true even if the network dynamics are controlled by a fully adaptive adversary that knows the complete network state. Virtually nothing besides simple O(kT) sequential flooding protocols was previously known for such a setting. While RLNC gossip works in this wide variety of networks its analysis remains the same and extremely simple. This contrasts with more complex proofs that were put forward to give less strong results for various special cases.
A strong direct product theorem for two-way public coin communication complexity
Venue: arXiv cs.CC 2010
Year: 2010

We show a direct product result for two-way public coin communication complexity of all relations in terms of a new complexity measure that we define. Our new measure is a generalization to non-product distributions of the two-way product subdistribution bound of [J, Klauck and Nayak 08], thereby our result implying their direct product result in terms of the two-way product subdistribution bound. We show that our new complexity measure gives tight lower bound for the set-disjointness problem, as a result we reproduce strong direct product result for this problem, which was previously shown by [Klauck 00].
Interference Alignment with Limited Feedback on Two-cell Interfering Two-User MIMO-MAC
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we consider a two-cell interfering two-user multiple-input multiple-output multiple access channel (MIMO-MAC) with limited feedback. We first investigate the multiplexing gain of such channel when users have perfect channel state information at transmitter (CSIT) by exploiting an interference alignment scheme. In addition, we propose a feedback framework for the interference alignment in the limited feedback system. On the basis of the proposed feedback framework, we analyze the rate gap loss and it is shown that in order to keep the same multiplexing gain with the case of perfect CSIT, the number of feedback bits per receiver scales as $B \geq (M\!-1\!)\!\log_{2}(\textsf{SNR})+C$, where $M$ and $C$ denote the number of transmit antennas and a constant, respectively. Throughout the simulation results, it is shown that the sum-rate performance coincides with the derived results.
Approche Multicritère pour le Problème de Ramassage et de Livraison avec Fenêtres de Temps à Plusieurs Véhicules
Venue: arXiv cs.NE 2010
Year: 2010

Nowadays, the transport goods problem occupies an important place in the economic life of modern societies. The pickup and delivery problem with time windows (PDPTW) is one of the problems which a large part of the research was interested. In this paper, we present a a brief literature review of the VRP and the PDPTW, propose our multicriteria approach based on genetic algorithms which allows minimize the compromise between the vehicles number, the total tardiness time and the total travel cost. And this, by treating the case where a customer can have multiple suppliers and one supplier can have multiple customers
Stealing Reality
Venue: arXiv cs.SI 2010
Year: 2010

In this paper we discuss the threat of malware targeted at extracting information about the relationships in a real-world social network as well as characteristic information about the individuals in the network, which we dub Stealing Reality. We present Stealing Reality, explain why it differs from traditional types of network attacks, and discuss why its impact is significantly more dangerous than that of other attacks. We also present our initial analysis and results regarding the form that an SR attack might take, with the goal of promoting the discussion of defending against such an attack, or even just detecting the fact that one has already occurred.
Exact Hamming Distortion Analysis of Viterbi Encoded Trellis Coded Quantizers
Venue: arXiv cs.IT 2010
Year: 2010

Let G be a finite strongly connected aperiodic directed graph in which each edge carries a label from a finite alphabet A. Then G induces a trellis coded quantizer for encoding an alphabet A memoryless source. A source sequence of long finite length is encoded by finding a path in G of that length whose sequence of labels is closest in Hamming distance to the source sequence; finding the minimum distance path is a dynamic programming problem that is solved using the Viterbi algorithm. We show how a Markov chain can be used to obtain a closed form expression for the asymptotic expected Hamming distortion per sample that results as the number of encoded source samples increases without bound.
A New Upper Bound on the Average Error Exponent for Multiple-Access Channels
Venue: arXiv cs.IT 2010
Year: 2010

A new lower bound for the average probability or error for a two-user discrete memoryless (DM) multiple-access channel (MAC) is derived. This bound has a structure very similar to the well-known sphere packing packing bound derived by Haroutunian. However, since explicitly imposes independence of the users' input distributions (conditioned on the time-sharing auxiliary variable) results in a tighter sphere-packing exponent in comparison to Haroutunian's. Also, the relationship between average and maximal error probabilities is studied. Finally, by using a known sphere packing bound on the maximal probability of error, a lower bound on the average error probability is derived.
On the Full Column-Rank Condition of the Channel Estimation Matrix in Doubly-Selective MIMO-OFDM Systems
Venue: arXiv cs.IT 2010
Year: 2010

Recently, this journal has published a paper which dealt with basis expansion model (BEM) based least-squares (LS) channel estimation in doubly-selective orthogonal frequency-division multiplexing (DS-OFDM) systems. The least-squares channel estimator computes the pseudo-inverse of a channel estimation matrix. For the existence of the pseudo-inverse, it is necessary that the channel estimation matrix be of full column rank. In this paper, we investigate the conditions that need to be satisfied that ensures the full column-rank condition of the channel estimation matrix. In particular, we derive conditions that the BEM and pilot pattern designs should satisfy to ensure that the channel estimation matrix is of full column rank. We explore the polynomial BEM (P-BEM), complex exponential BEM (CE-BEM), Slepian BEM (S-BEM) and generalized complex exponential BEM (GCE-BEM). We present one possible way to design the pilot patterns which satisfy the full column-rank conditions. Furthermore, the proposed method is extended to the case of multiple-input multiple-output (MIMO) DS-OFDM systems as well. Examples of pilot pattern designs are presented, that ensure the channel estimation matrix is of full column rank for a large DS-MIMO-OFDM system with as many as six transmitters, six receivers and 1024 subcarriers.
Computational Complexity of Avalanches in the Kadanoff two-dimensional Sandpile Model
Venue: arXiv cs.DM 2010
Year: 2010

In this paper we prove that the avalanche problem for Kadanoff sandpile model (KSPM) is P-complete for two-dimensions. Our proof is based on a reduction from the monotone circuit value problem by building logic gates and wires which work with configurations in KSPM. The proof is also related to the known prediction problem for sandpile which is in NC for one-dimensional sandpiles and is P-complete for dimension 3 or greater. The computational complexity of the prediction problem remains open for two-dimensional sandpiles.
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem
Venue: arXiv cs.CC 2010
Year: 2010

We present a simple deterministic gap-preserving reduction from SAT to the Minimum Distance of Code Problem over $\F_2$. We also show how to extend the reduction to work over any finite field. Previously a randomized reduction was known due to Dumer, Micciancio, and Sudan, which was recently derandomized by Cheng and Wan. These reductions rely on highly non-trivial coding theoretic constructions whereas our reduction is elementary. As an additional feature, our reduction gives a constant factor hardness even for asymptotically good codes, i.e., having constant rate and relative distance. Previously it was not known how to achieve deterministic reductions for such codes.
Mapping XML Data to Relational Data: A DOM-Based Approach
Venue: arXiv cs.DB 2010
Year: 2010

XML has emerged as the standard for representing and exchanging data on the World Wide Web. It is critical to have efficient mechanisms to store and query XML data to exploit the full power of this new technology. Several researchers have proposed to use relational databases to store and query XML data. While several algorithms of schema mapping and query mapping have been proposed, the problem of mapping XML data to relational data, i.e., mapping an XML INSERT statement to a sequence of SQL INSERT statements, has not been addressed thoroughly in the literature. In this paper, we propose an efficient linear algorithm for mapping XML data to relational data. This algorithm is based on our previous proposed inlining algorithm for mapping DTDs to relational schemas and can be easily adapted to other inlining algorithms.
Modified Bully Algorithm using Election Commission
Venue: arXiv cs.DC 2010
Year: 2010

Electing leader is a vital issue not only in distributed computing but also in communication network [1, 2, 3, 4, 5], centralized mutual exclusion algorithm [6, 7], centralized control IPC, etc. A leader is required to make synchronization between different processes. And different election algorithms are used to elect a coordinator among the available processes in the system such a way that there will be only one coordinator at any time. Bully election algorithm is one of the classical and well-known approaches in coordinator election process. This paper will present a modified version of bully election algorithm using a new concept called election commission. This approach will not only reduce redundant elections but also minimize total number of elections and hence it will minimize message passing, network traffic, and complexity of the existing system.
Implications of Inter-Rater Agreement on a Student Information Retrieval Evaluation
Venue: arXiv cs.IR 2010
Year: 2010

This paper is about an information retrieval evaluation on three different retrieval-supporting services. All three services were designed to compensate typical problems that arise in metadata-driven Digital Libraries, which are not adequately handled by a simple tf-idf based retrieval. The services are: (1) a co-word analysis based query expansion mechanism and re-ranking via (2) Bradfordizing and (3) author centrality. The services are evaluated with relevance assessments conducted by 73 information science students. Since the students are neither information professionals nor domain experts the question of inter-rater agreement is taken into consideration. Two important implications emerge: (1) the inter-rater agreement rates were mainly fair to moderate and (2) after a data-cleaning step which erased the assessments with poor agreement rates the evaluation data shows that the three retrieval services returned disjoint but still relevant result sets.