OpenRaiser/Intern-Atlas huggingface dataset:
A High-Throughput Cross-Layer Scheme for Distributed Wireless Ad Hoc Networks
Venue: arXiv cs.IT 2007
Year: 2007

In wireless ad hoc networks, distributed nodes can collaboratively form an antenna array for long-distance communications to achieve high energy efficiency. In recent work, Ochiai, et al., have shown that such collaborative beamforming can achieve a statistically nice beampattern with a narrow main lobe and low sidelobes. However, the process of collaboration introduces significant delay, since all collaborating nodes need access to the same information. In this paper, a technique that significantly reduces the collaboration overhead is proposed. It consists of two phases. In the first phase, nodes transmit locally in a random access fashion. Collisions, when they occur, are viewed as linear mixtures of the collided packets. In the second phase, a set of cooperating nodes acts as a distributed antenna system and beamform the received analog waveform to one or more faraway destinations. This step requires multiplication of the received analog waveform by a complex number, which is independently computed by each cooperating node, and which enables separation of the collided packets based on their final destination. The scheme requires that each node has global knowledge of the network coordinates. The proposed scheme can achieve high throughput, which in certain cases exceeds one.
Modern Coding Theory: The Statistical Mechanics and Computer Science Point of View
Venue: arXiv cs.IT 2007
Year: 2007

These are the notes for a set of lectures delivered by the two authors at the Les Houches Summer School on `Complex Systems' in July 2006. They provide an introduction to the basic concepts in modern (probabilistic) coding theory, highlighting connections with statistical mechanics. We also stress common concepts with other disciplines dealing with similar problems that can be generically referred to as `large graphical models'. While most of the lectures are devoted to the classical channel coding problem over simple memoryless channels, we present a discussion of more complex channel models. We conclude with an overview of the main open challenges in the field.
Recommending Related Papers Based on Digital Library Access Records
Venue: arXiv cs.DL 2007
Year: 2007

An important goal for digital libraries is to enable researchers to more easily explore related work. While citation data is often used as an indicator of relatedness, in this paper we demonstrate that digital access records (e.g. http-server logs) can be used as indicators as well. In particular, we show that measures based on co-access provide better coverage than co-citation, that they are available much sooner, and that they are more accurate for recent papers.
Using Access Data for Paper Recommendations on ArXiv.org
Venue: arXiv cs.DL 2007
Year: 2007

This thesis investigates in the use of access log data as a source of information for identifying related scientific papers. This is done for arXiv.org, the authority for publication of e-prints in several fields of physics. Compared to citation information, access logs have the advantage of being immediately available, without manual or automatic extraction of the citation graph. Because of that, a main focus is on the question, how far user behavior can serve as a replacement for explicit meta-data, which potentially might be expensive or completely unavailable. Therefore, we compare access, content, and citation-based measures of relatedness on different recommendation tasks. As a final result, an online recommendation system has been built that can help scientists to find further relevant literature, without having to search for them actively.
Detection of two-sided alternatives in a Brownian motion model
Venue: arXiv cs.IT 2007
Year: 2007

This work examines the problem of sequential detection of a change in the drift of a Brownian motion in the case of two-sided alternatives. Applications to real life situations in which two-sided changes can occur are discussed. Traditionally, 2-CUSUM stopping rules have been used for this problem due to their asymptotically optimal character as the mean time between false alarms tends to $\infty$. In particular, attention has focused on 2-CUSUM harmonic mean rules due to the simplicity in calculating their first moments. In this paper, we derive closed-form expressions for the first moment of a general 2-CUSUM stopping rule. We use these expressions to obtain explicit upper and lower bounds for it. Moreover, we derive an expression for the rate of change of this first moment as one of the threshold parameters changes. Based on these expressions we obtain explicit upper and lower bounds to this rate of change. Using these expressions we are able to find the best 2-CUSUM stopping rule with respect to the extended Lorden criterion. In fact, we demonstrate not only the existence but also the uniqueness of the best 2-CUSUM stopping both in the case of a symmetric change and in the case of a non-symmetric case. Furthermore, we discuss the existence of a modification of the 2-CUSUM stopping rule that has a strictly better performance than its classical 2-CUSUM counterpart for small values of the mean time between false alarms. We conclude with a discussion on the open problem of strict optimality in the case of two-sided alternatives.
Alternative axiomatics and complexity of deliberative STIT theories
Venue: arXiv cs.LO 2007
Year: 2007

We propose two alternatives to Xu's axiomatization of the Chellas STIT. The first one also provides an alternative axiomatization of the deliberative STIT. The second one starts from the idea that the historic necessity operator can be defined as an abbreviation of operators of agency, and can thus be eliminated from the logic of the Chellas STIT. The second axiomatization also allows us to establish that the problem of deciding the satisfiability of a STIT formula without temporal operators is NP-complete in the single-agent case, and is NEXPTIME-complete in the multiagent case, both for the deliberative and the Chellas' STIT.
Coalition Games with Cooperative Transmission: A Cure for the Curse of Boundary Nodes in Selfish Packet-Forwarding Wireless Networks
Venue: arXiv cs.IT 2007
Year: 2007

In wireless packet-forwarding networks with selfish nodes, applications of a repeated game can induce the nodes to forward each others' packets, so that the network performance can be improved. However, the nodes on the boundary of such networks cannot benefit from this strategy, as the other nodes do not depend on them. This problem is sometimes known as the curse of the boundary nodes. To overcome this problem, an approach based on coalition games is proposed, in which the boundary nodes can use cooperative transmission to help the backbone nodes in the middle of the network. In return, the backbone nodes are willing to forward the boundary nodes' packets. The stability of the coalitions is studied using the concept of a core. Then two types of fairness, namely, the min-max fairness using nucleolus and the average fairness using the Shapley function are investigated. Finally, a protocol is designed using both repeated games and coalition games. Simulation results show how boundary nodes and backbone nodes form coalitions together according to different fairness criteria. The proposed protocol can improve the network connectivity by about 50%, compared with pure repeated game schemes.
Capacity of a Class of Modulo-Sum Relay Channels
Venue: arXiv cs.IT 2007
Year: 2007

This paper characterizes the capacity of a class of modulo additive noise relay channels, in which the relay observes a corrupted version of the noise and has a separate channel to the destination. The capacity is shown to be strictly below the cut-set bound in general and achievable using a quantize-and-forward strategy at the relay. This result confirms a conjecture by Ahlswede and Han about the capacity of channels with rate limited state information at the destination for this particular class of channels.
Capacity Gain from Two-Transmitter and Two-Receiver Cooperation
Venue: arXiv cs.IT 2007
Year: 2007

Capacity improvement from transmitter and receiver cooperation is investigated in a two-transmitter, two-receiver network with phase fading and full channel state information available at all terminals. The transmitters cooperate by first exchanging messages over an orthogonal transmitter cooperation channel, then encoding jointly with dirty paper coding. The receivers cooperate by using Wyner-Ziv compress-and-forward over an analogous orthogonal receiver cooperation channel. To account for the cost of cooperation, the allocation of network power and bandwidth among the data and cooperation channels is studied. It is shown that transmitter cooperation outperforms receiver cooperation and improves capacity over non-cooperative transmission under most operating conditions when the cooperation channel is strong. However, a weak cooperation channel limits the transmitter cooperation rate; in this case receiver cooperation is more advantageous. Transmitter-and-receiver cooperation offers sizable additional capacity gain over transmitter-only cooperation at low SNR, whereas at high SNR transmitter cooperation alone captures most of the cooperative capacity improvement.
The Long Term Fate of Our Digital Belongings: Toward a Service Model for Personal Archives
Venue: arXiv cs.DL 2007
Year: 2007

We conducted a preliminary field study to understand the current state of personal digital archiving in practice. Our aim is to design a service for the long-term storage, preservation, and access of digital belongings by examining how personal archiving needs intersect with existing and emerging archiving technologies, best practices, and policies. Our findings not only confirmed that experienced home computer users are creating, receiving, and finding an increasing number of digital belongings, but also that they have already lost irreplaceable digital artifacts such as photos, creative efforts, and records. Although participants reported strategies such as backup and file replication for digital safekeeping, they were seldom able to implement them consistently. Four central archiving themes emerged from the data: (1) people find it difficult to evaluate the worth of accumulated materials; (2) personal storage is highly distributed both on- and offline; (3) people are experiencing magnified curatorial problems associated with managing files in the aggregate, creating appropriate metadata, and migrating materials to maintainable formats; and (4) facilities for long-term access are not supported by the current desktop metaphor. Four environmental factors further complicate archiving in consumer settings: the pervasive influence of malware; consumer reliance on ad hoc IT providers; an accretion of minor system and registry inconsistencies; and strong consumer beliefs about the incorruptibility of digital forms, the reliability of digital technologies, and the social vulnerability of networked storage.
Network statistics on early English Syntax: Structural criteria
Venue: arXiv cs.CL 2007
Year: 2007

This paper includes a reflection on the role of networks in the study of English language acquisition, as well as a collection of practical criteria to annotate free-speech corpora from children utterances. At the theoretical level, the main claim of this paper is that syntactic networks should be interpreted as the outcome of the use of the syntactic machinery. Thus, the intrinsic features of such machinery are not accessible directly from (known) network properties. Rather, what one can see are the global patterns of its use and, thus, a global view of the power and organization of the underlying grammar. Taking a look into more practical issues, the paper examines how to build a net from the projection of syntactic relations. Recall that, as opposed to adult grammars, early-child language has not a well-defined concept of structure. To overcome such difficulty, we develop a set of systematic criteria assuming constituency hierarchy and a grammar based on lexico-thematic relations. At the end, what we obtain is a well defined corpora annotation that enables us i) to perform statistics on the size of structures and ii) to build a network from syntactic relations over which we can perform the standard measures of complexity. We also provide a detailed example.
A Game-Theoretic Approach to Energy-Efficient Modulation in CDMA Networks with Delay Constraints
Venue: arXiv cs.IT 2007
Year: 2007

A game-theoretic framework is used to study the effect of constellation size on the energy efficiency of wireless networks for M-QAM modulation. A non-cooperative game is proposed in which each user seeks to choose its transmit power (and possibly transmit symbol rate) as well as the constellation size in order to maximize its own utility while satisfying its delay quality-of-service (QoS) constraint. The utility function used here measures the number of reliable bits transmitted per joule of energy consumed, and is particularly suitable for energy-constrained networks. The best-response strategies and Nash equilibrium solution for the proposed game are derived. It is shown that in order to maximize its utility (in bits per joule), a user must choose the lowest constellation size that can accommodate the user's delay constraint. Using this framework, the tradeoffs among energy efficiency, delay, throughput and constellation size are also studied and quantified. The effect of trellis-coded modulation on energy efficiency is also discussed.
Energy-Efficient Resource Allocation in Wireless Networks with Quality-of-Service Constraints
Venue: arXiv cs.IT 2007
Year: 2007

A game-theoretic model is proposed to study the cross-layer problem of joint power and rate control with quality of service (QoS) constraints in multiple-access networks. In the proposed game, each user seeks to choose its transmit power and rate in a distributed manner in order to maximize its own utility while satisfying its QoS requirements. The user's QoS constraints are specified in terms of the average source rate and an upper bound on the average delay where the delay includes both transmission and queuing delays. The utility function considered here measures energy efficiency and is particularly suitable for wireless networks with energy constraints. The Nash equilibrium solution for the proposed non-cooperative game is derived and a closed-form expression for the utility achieved at equilibrium is obtained. It is shown that the QoS requirements of a user translate into a "size" for the user which is an indication of the amount of network resources consumed by the user. Using this competitive multiuser framework, the tradeoffs among throughput, delay, network capacity and energy efficiency are studied. In addition, analytical expressions are given for users' delay profiles and the delay performance of the users at Nash equilibrium is quantified.
Optimal Delay-Throughput Trade-offs in Mobile Ad-Hoc Networks: Hybrid Random Walk and One-Dimensional Mobility Models
Venue: arXiv cs.NI 2007
Year: 2007

Optimal delay-throughput trade-offs for two-dimensional i.i.d mobility models have been established in [23], where we showed that the optimal trade-offs can be achieved using rate-less codes when the required delay guarantees are sufficient large. In this paper, we extend the results to other mobility models including two-dimensional hybrid random walk model, one-dimensional i.i.d. mobility model and one-dimensional hybrid random walk model. We consider both fast mobiles and slow mobiles, and establish the optimal delay-throughput trade-offs under some conditions. Joint coding-scheduling algorithms are also proposed to achieve the optimal trade-offs.
Edges and Switches, Tunnels and Bridges
Venue: arXiv cs.DS 2007
Year: 2007

Edge casing is a well-known method to improve the readability of drawings of non-planar graphs. A cased drawing orders the edges of each edge crossing and interrupts the lower edge in an appropriate neighborhood of the crossing. Certain orders will lead to a more readable drawing than others. We formulate several optimization criteria that try to capture the concept of a "good" cased drawing. Further, we address the algorithmic question of how to turn a given drawing into an optimal cased drawing. For many of the resulting optimization problems, we either find polynomial time algorithms or NP-hardness results.
Multiresolution Approximation of Polygonal Curves in Linear Complexity
Venue: arXiv cs.CV 2007
Year: 2007

We propose a new algorithm to the problem of polygonal curve approximation based on a multiresolution approach. This algorithm is suboptimal but still maintains some optimality between successive levels of resolution using dynamic programming. We show theoretically and experimentally that this algorithm has a linear complexity in time and space. We experimentally compare the outcomes of our algorithm to the optimal "full search" dynamic programming solution and finally to classical merge and split approaches. The experimental evaluations confirm the theoretical derivations and show that the proposed approach evaluated on 2D coastal maps either show a lower time complexity or provide polygonal approximations closer to the input discrete curves.
OCB: A Generic Benchmark to Evaluate the Performances of Object-Oriented Database Systems
Venue: arXiv cs.DB 2007
Year: 2007

We present in this paper a generic object-oriented benchmark (the Object Clustering Benchmark) that has been designed to evaluate the performances of clustering policies in object-oriented databases. OCB is generic because its sample database may be customized to fit the databases introduced by the main existing benchmarks (e.g., OO1). OCB's current form is clustering-oriented because of its clustering-oriented workload, but it can be easily adapted to other purposes. Lastly, OCB's code is compact and easily portable. OCB has been implemented in a real system (Texas, running on a Sun workstation), in order to test a specific clustering policy called DSTC. A few results concerning this test are presented.
MIMO detection employing Markov Chain Monte Carlo
Venue: arXiv cs.GL 2007
Year: 2007

We propose a soft-output detection scheme for Multiple-Input-Multiple-Output (MIMO) systems. The detector employs Markov Chain Monte Carlo method to compute bit reliabilities from the signals received and is thus suited for coded MIMO systems. It offers a good trade-off between achievable performance and algorithmic complexity.
Equivalence of LP Relaxation and Max-Product for Weighted Matching in General Graphs
Venue: arXiv cs.IT 2007
Year: 2007

Max-product belief propagation is a local, iterative algorithm to find the mode/MAP estimate of a probability distribution. While it has been successfully employed in a wide variety of applications, there are relatively few theoretical guarantees of convergence and correctness for general loopy graphs that may have many short cycles. Of these, even fewer provide exact ``necessary and sufficient'' characterizations. In this paper we investigate the problem of using max-product to find the maximum weight matching in an arbitrary graph with edge weights. This is done by first constructing a probability distribution whose mode corresponds to the optimal matching, and then running max-product. Weighted matching can also be posed as an integer program, for which there is an LP relaxation. This relaxation is not always tight. In this paper we show that \begin{enumerate} \item If the LP relaxation is tight, then max-product always converges, and that too to the correct answer. \item If the LP relaxation is loose, then max-product does not converge. \end{enumerate} This provides an exact, data-dependent characterization of max-product performance, and a precise connection to LP relaxation, which is a well-studied optimization technique. Also, since LP relaxation is known to be tight for bipartite graphs, our results generalize other recent results on using max-product to find weighted matchings in bipartite graphs.
Performance Comparison of Energy-Efficient Power Control for CDMA and Multiuser UWB Networks
Venue: arXiv cs.GT 2007
Year: 2007

This paper studies the performance of a wireless data network using energy-efficient power control techniques when different multiple access schemes, namely direct-sequence code division multiple access (DS-CDMA) and impulse-radio ultrawideband (IR-UWB), are considered. Due to the large bandwidth of the system, the multipath channel is assumed to be frequency-selective. By making use of noncooperative game-theoretic models and large-system analysis tools, explicit expressions for the achieved utilities at the Nash equilibrium are derived in terms of the network parameters. A measure of the loss of DS-CDMA with respect to IR-UWB is proposed, which proves substantial equivalence between the two schemes. Simulation results are provided to validate the analysis.
Improved Analysis of Kannan's Shortest Lattice Vector Algorithm
Venue: arXiv cs.CR 2007
Year: 2007

The security of lattice-based cryptosystems such as NTRU, GGH and Ajtai-Dwork essentially relies upon the intractability of computing a shortest non-zero lattice vector and a closest lattice vector to a given target vector in high dimensions. The best algorithms for these tasks are due to Kannan, and, though remarkably simple, their complexity estimates have not been improved since more than twenty years. Kannan's algorithm for solving the shortest vector problem is in particular crucial in Schnorr's celebrated block reduction algorithm, on which are based the best known attacks against the lattice-based encryption schemes mentioned above. Understanding precisely Kannan's algorithm is of prime importance for providing meaningful key-sizes. In this paper we improve the complexity analyses of Kannan's algorithms and discuss the possibility of improving the underlying enumeration strategy.
Artificial Neural Networks and Support Vector Machines for Water Demand Time Series Forecasting
Venue: arXiv cs.AI 2007
Year: 2007

Water plays a pivotal role in many physical processes, and most importantly in sustaining human life, animal life and plant life. Water supply entities therefore have the responsibility to supply clean and safe water at the rate required by the consumer. It is therefore necessary to implement mechanisms and systems that can be employed to predict both short-term and long-term water demands. The increasingly growing field of computational intelligence techniques has been proposed as an efficient tool in the modelling of dynamic phenomena. The primary objective of this paper is to compare the efficiency of two computational intelligence techniques in water demand forecasting. The techniques under comparison are the Artificial Neural Networks (ANNs) and the Support Vector Machines (SVMs). In this study it was observed that the ANNs perform better than the SVMs. This performance is measured against the generalisation ability of the two.
Fuzzy Artmap and Neural Network Approach to Online Processing of Inputs with Missing Values
Venue: arXiv cs.AI 2007
Year: 2007

An ensemble based approach for dealing with missing data, without predicting or imputing the missing values is proposed. This technique is suitable for online operations of neural networks and as a result, is used for online condition monitoring. The proposed technique is tested in both classification and regression problems. An ensemble of Fuzzy-ARTMAPs is used for classification whereas an ensemble of multi-layer perceptrons is used for the regression problem. Results obtained using this ensemble-based technique are compared to those obtained using a combination of auto-associative neural networks and genetic algorithms and findings show that this method can perform up to 9% better in regression problems. Another advantage of the proposed technique is that it eliminates the need for finding the best estimate of the data, and hence, saves time.