OpenRaiser/Intern-Atlas huggingface dataset:
Throughput and Delay in Random Wireless Networks with Restricted Mobility
Venue: arXiv cs.IT 2005
Year: 2005

Grossglauser and Tse (2001) introduced a mobile random network model where each node moves independently on a unit disk according to a stationary uniform distribution and showed that a throughput of $Θ(1)$ is achievable. El Gamal, Mammen, Prabhakar and Shah (2004) showed that the delay associated with this throughput scales as $Θ(n\log n)$, when each node moves according to an independent random walk. In a later work, Diggavi, Grossglauser and Tse (2002) considered a random network on a sphere with a restricted mobility model, where each node moves along a randomly chosen great circle on the unit sphere. They showed that even with this one-dimensional restriction on mobility, constant throughput scaling is achievable. Thus, this particular mobility restriction does not affect the throughput scaling. This raises the question whether this mobility restriction affects the delay scaling. This paper studies the delay scaling at $Θ(1)$ throughput for a random network with restricted mobility. First, a variant of the scheme presented by Diggavi, Grossglauser and Tse (2002) is presented and it is shown to achieve $Θ(1)$ throughput using different (and perhaps simpler) techniques. The exact order of delay scaling for this scheme is determined, somewhat surprisingly, to be of $Θ(n\log n)$, which is the same as that without the mobility restriction. Thus, this particular mobility restriction \emph{does not} affect either the maximal throughput scaling or the corresponding delay scaling of the network. This happens because under this 1-D restriction, each node is in the proximity of every other node in essentially the same manner as without this restriction.
Modelling the Eulerian Path Problem using a String Matching Framework
Venue: arXiv cs.DS 2005
Year: 2005

The well-known Eulerian path problem can be solved in polynomial time (more exactly, there exists a linear time algorithm for this problem). In this paper, we model the problem using a string matching framework, and then initiate an algorithmic study on a variant of this problem, called the (2,1)-STRING-MATCH problem (which is actually a generalization of the Eulerian path problem). Then, we present a polynomial-time algorithm for the (2,1)-STRING-MATCH problem, which is the most important result of this paper. Specifically, we get a lower bound of Omega(n), and an upper bound of O(n^{2}).
New Upper Bounds on A(n,d)
Venue: arXiv cs.IT 2005
Year: 2005

Upper bounds on the maximum number of codewords in a binary code of a given length and minimum Hamming distance are considered. New bounds are derived by a combination of linear programming and counting arguments. Some of these bounds improve on the best known analytic bounds. Several new record bounds are obtained for codes with small lengths.
A study of set-sharing analysis via cliques
Venue: arXiv cs.LO 2005
Year: 2005

We study the problem of efficient, scalable set-sharing analysis of logic programs. We use the idea of representing sharing information as a pair of abstract substitutions, one of which is a worst-case sharing representation called a clique set, which was previously proposed for the case of inferring pair-sharing. We use the clique-set representation for (1) inferring actual set-sharing information, and (2) analysis within a top-down framework. In particular, we define the abstract functions required by standard top-down analyses, both for sharing alone and also for the case of including freeness in addition to sharing. Our experimental evaluation supports the conclusion that, for inferring set-sharing, as it was the case for inferring pair-sharing, precision losses are limited, while useful efficiency gains are obtained. At the limit, the clique-set representation allowed analyzing some programs that exceeded memory capacity using classical sharing representations.
Long-term neuronal behavior caused by two synaptic modification mechanisms
Venue: arXiv cs.NE 2005
Year: 2005

We report the first results of simulating the coupling of neuronal, astrocyte, and cerebrovascular activity. It is suggested that the dynamics of the system is different from systems that only include neurons. In the neuron-vascular coupling, distribution of synapse strengths affects neuronal behavior and thus balance of the blood flow; oscillations are induced in the neuron-to-astrocyte coupling.
How Good is Phase-Shift Keying for Peak-Limited Rayleigh Fading Channels in the Low-SNR Regime?
Venue: arXiv cs.IT 2005
Year: 2005

This paper investigates the achievable information rate of phase-shift keying (PSK) over frequency non-selective Rayleigh fading channels without channel state information (CSI). The fading process exhibits general temporal correlation characterized by its spectral density function. We consider both discrete-time and continuous-time channels, and find their asymptotics at low signal-to-noise ratio (SNR). Compared to known capacity upper bounds under peak constraints, these asymptotics usually lead to negligible rate loss in the low-SNR regime for slowly time-varying fading channels. We further specialize to case studies of Gauss-Markov and Clarke's fading models.
Coding Schemes for Line Networks
Venue: arXiv cs.IT 2005
Year: 2005

We consider a simple network, where a source and destination node are connected with a line of erasure channels. It is well known that in order to achieve the min-cut capacity, the intermediate nodes are required to process the information. We propose coding schemes for this setting, and discuss each scheme in terms of complexity, delay, achievable rate, memory requirement, and adaptability to unknown channel parameters. We also briefly discuss how these schemes can be extended to more general networks.
Asymptotic Behavior of Error Exponents in the Wideband Regime
Venue: arXiv cs.IT 2005
Year: 2005

In this paper, we complement Verdú's work on spectral efficiency in the wideband regime by investigating the fundamental tradeoff between rate and bandwidth when a constraint is imposed on the error exponent. Specifically, we consider both AWGN and Rayleigh-fading channels. For the AWGN channel model, the optimal values of $R_z(0)$ and $\dot{R_z}(0)$ are calculated, where $R_z(1/B)$ is the maximum rate at which information can be transmitted over a channel with bandwidth $B/2$ when the error-exponent is constrained to be greater than or equal to $z.$ Based on this calculation, we say that a sequence of input distributions is near optimal if both $R_z(0)$ and $\dot{R_z}(0)$ are achieved. We show that QPSK, a widely-used signaling scheme, is near-optimal within a large class of input distributions for the AWGN channel. Similar results are also established for a fading channel where full CSI is available at the receiver.
Joint Equalization and Decoding for Nonlinear Two-Dimensional Intersymbol Interference Channels
Venue: arXiv cs.IT 2005
Year: 2005

An algorithm that performs joint equalization and decoding for channels with nonlinear two-dimensional intersymbol interference is presented. The algorithm performs sum-product message-passing on a factor graph that represents the underlying system. The two-dimensional optical storage (TwoDOS) technology is an example of a system with nonlinear two-dimensional intersymbol interference. Simulations for the nonlinear channel model of TwoDOS show significant improvement in performance over uncoded performance. Noise tolerance thresholds for the TwoDOS channel computed using density evolution are also presented.
Minimum Mean-Square-Error Equalization using Priors for Two-Dimensional Intersymbol Interference
Venue: arXiv cs.IT 2005
Year: 2005

Joint equalization and decoding schemes are described for two-dimensional intersymbol interference (ISI) channels. Equalization is performed using the minimum mean-square-error (MMSE) criterion. Low-density parity-check codes are used for error correction. The MMSE schemes are the extension of those proposed by Tuechler et al. (2002) for one-dimensional ISI channels. Extrinsic information transfer charts, density evolution, and bit-error rate versus signal-to-noise ratio curves are used to study the performance of the schemes.
K-Histograms: An Efficient Clustering Algorithm for Categorical Dataset
Venue: arXiv cs.AI 2005
Year: 2005

Clustering categorical data is an integral part of data mining and has attracted much attention recently. In this paper, we present k-histogram, a new efficient algorithm for clustering categorical data. The k-histogram algorithm extends the k-means algorithm to categorical domain by replacing the means of clusters with histograms, and dynamically updates histograms in the clustering process. Experimental results on real datasets show that k-histogram algorithm can produce better clustering results than k-modes algorithm, the one related with our work most closely.
Secure multiplex coding to attain the channel capacity in wiretap channels
Venue: arXiv cs.IT 2005
Year: 2005

It is known that a message can be transmitted safely against any wiretapper via a noisy channel without a secret key if the coding rate is less than the so-called secrecy capacity $C_S$, which is usually smaller than the channel capacity $C$. In order to remove the loss $C - C_S$, we propose a multiplex coding scheme with plural independent messages. In this paper, it is shown that the proposed multiplex coding scheme can attain the channel capacity as the total rate of the plural messages and the perfect secrecy for each message. The coding theorem is proved by extending Hayashi's proof, in which the coding of the channel resolvability is applied to wiretap channels.
On the Achievable Information Rates of CDMA Downlink with Trivial Receivers
Venue: arXiv cs.IT 2005
Year: 2005

A noisy CDMA downlink channel operating under a strict complexity constraint on the receiver is introduced. According to this constraint, detected bits, obtained by performing hard decisions directly on the channel's matched filter output, must be the same as the transmitted binary inputs. This channel setting, allowing the use of the simplest receiver scheme, seems to be worthless, making reliable communication at any rate impossible. However, recently this communication paradigm was shown to yield valuable information rates in the case of a noiseless channel. This finding calls for the investigation of this attractive complexity-constrained transmission scheme for the more practical noisy channel case. By adopting the statistical mechanics notion of metastable states of the renowned Hopfield model, it is proved that under a bounded noise assumption such complexity-constrained CDMA channel gives rise to a non-trivial Shannon-theoretic capacity, rigorously analyzed and corroborated using finite-size channel simulations. For unbounded noise the channel's outage capacity is addressed and specifically described for the popular additive white Gaussian noise.
Underwater Hacker Missile Wars: A Cryptography and Engineering Contest
Venue: arXiv cs.CR 2005
Year: 2005

For a recent student conference, the authors developed a day-long design problem and competition suitable for engineering, mathematics and science undergraduates. The competition included a cryptography problem, for which a workshop was run during the conference. This paper describes the competition, focusing on the cryptography problem and the workshop. Notes from the workshop and code for the computer programs are made available via the Internet. The results of a personal self-evaluation (PSE) are described.
Pairing-based identification schemes
Venue: arXiv cs.CR 2005
Year: 2005

We propose four different identification schemes that make use of bilinear pairings, and prove their security under certain computational assumptions. Each of the schemes is more efficient and/or more secure than any known pairing-based identification scheme.
Cluster Computing and the Power of Edge Recognition
Venue: arXiv cs.CC 2005
Year: 2005

We study the robustness--the invariance under definition changes--of the cluster class CL#P [HHKW05]. This class contains each #P function that is computed by a balanced Turing machine whose accepting paths always form a cluster with respect to some length-respecting total order with efficient adjacency checks. The definition of CL#P is heavily influenced by the defining paper's focus on (global) orders. In contrast, we define a cluster class, CLU#P, to capture what seems to us a more natural model of cluster computing. We prove that the naturalness is costless: CL#P = CLU#P. Then we exploit the more natural, flexible features of CLU#P to prove new robustness results for CL#P and to expand what is known about the closure properties of CL#P. The complexity of recognizing edges--of an ordered collection of computation paths or of a cluster of accepting computation paths--is central to this study. Most particularly, our proofs exploit the power of unique discovery of edges--the ability of nondeterministic functions to, in certain settings, discover on exactly one (in some cases, on at most one) computation path a critical piece of information regarding edges of orderings or clusters.
Business intelligence systems and user's parameters: an application to a documents' database
Venue: arXiv cs.DB 2005
Year: 2005

This article presents earlier results of our research works in the area of modeling Business Intelligence Systems. The basic idea of this research area is presented first. We then show the necessity of including certain users' parameters in Information systems that are used in Business Intelligence systems in order to integrate a better response from such systems. We identified two main types of attributes that can be missing from a base and we showed why they needed to be included. A user model that is based on a cognitive user evolution is presented. This model when used together with a good definition of the information needs of the user (decision maker) will accelerate his decision making process.
Automatic extraction of paraphrastic phrases from medium size corpora
Venue: arXiv cs.CL 2005
Year: 2005

This paper presents a versatile system intended to acquire paraphrastic phrases from a representative corpus. In order to decrease the time spent on the elaboration of resources for NLP system (for example Information Extraction, IE hereafter), we suggest to use a machine learning system that helps defining new templates and associated resources. This knowledge is automatically derived from the text collection, in interaction with a large semantic network.
Taylor series expansions for the entropy rate of Hidden Markov Processes
Venue: arXiv cs.IT 2005
Year: 2005

Finding the entropy rate of Hidden Markov Processes is an active research topic, of both theoretical and practical importance. A recently used approach is studying the asymptotic behavior of the entropy rate in various regimes. In this paper we generalize and prove a previous conjecture relating the entropy rate to entropies of finite systems. Building on our new theorems, we establish series expansions for the entropy rate in two different regimes. We also study the radius of convergence of the two series expansions.
Network Inference from TraceRoute Measurements: Internet Topology `Species'
Venue: arXiv cs.NI 2005
Year: 2005

Internet mapping projects generally consist in sampling the network from a limited set of sources by using traceroute probes. This methodology, akin to the merging of spanning trees from the different sources to a set of destinations, leads necessarily to a partial, incomplete map of the Internet. Accordingly, determination of Internet topology characteristics from such sampled maps is in part a problem of statistical inference. Our contribution begins with the observation that the inference of many of the most basic topological quantities -- including network size and degree characteristics -- from traceroute measurements is in fact a version of the so-called `species problem' in statistics. This observation has important implications, since species problems are often quite challenging. We focus here on the most fundamental example of a traceroute internet species: the number of nodes in a network. Specifically, we characterize the difficulty of estimating this quantity through a set of analytical arguments, we use statistical subsampling principles to derive two proposed estimators, and we illustrate the performance of these estimators on networks with various topological characteristics.
Diophantus' 20th Problem and Fermat's Last Theorem for n=4: Formalization of Fermat's Proofs in the Coq Proof Assistant
Venue: arXiv cs.LO 2005
Year: 2005

We present the proof of Diophantus' 20th problem (book VI of Diophantus' Arithmetica), which consists in wondering if there exist right triangles whose sides may be measured as integers and whose surface may be a square. This problem was negatively solved by Fermat in the 17th century, who used the "wonderful" method (ipse dixit Fermat) of infinite descent. This method, which is, historically, the first use of induction, consists in producing smaller and smaller non-negative integer solutions assuming that one exists; this naturally leads to a reductio ad absurdum reasoning because we are bounded by zero. We describe the formalization of this proof which has been carried out in the Coq proof assistant. Moreover, as a direct and no less historical application, we also provide the proof (by Fermat) of Fermat's last theorem for n=4, as well as the corresponding formalization made in Coq.
Partial fillup and search time in LC tries
Venue: arXiv cs.DS 2005
Year: 2005

Andersson and Nilsson introduced in 1993 a level-compressed trie (in short: LC trie) in which a full subtree of a node is compressed to a single node of degree being the size of the subtree. Recent experimental results indicated a 'dramatic improvement' when full subtrees are replaced by partially filled subtrees. In this paper, we provide a theoretical justification of these experimental results showing, among others, a rather moderate improvement of the search time over the original LC tries. For such an analysis, we assume that n strings are generated independently by a binary memoryless source with p denoting the probability of emitting a 1. We first prove that the so called alpha-fillup level (i.e., the largest level in a trie with alpha fraction of nodes present at this level) is concentrated on two values with high probability. We give these values explicitly up to O(1), and observe that the value of alpha (strictly between 0 and 1) does not affect the leading term. This result directly yields the typical depth (search time) in the alpha-LC tries with p not equal to 1/2, which turns out to be C loglog n for an explicitly given constant C (depending on p but not on alpha). This should be compared with recently found typical depth in the original LC tries which is C' loglog n for a larger constant C'. The search time in alpha-LC tries is thus smaller but of the same order as in the original LC tries.
A decision support system for ship identification based on the curvature scale space representation
Venue: arXiv cs.CV 2005
Year: 2005

In this paper, a decision support system for ship identification is presented. The system receives as input a silhouette of the vessel to be identified, previously extracted from a side view of the object. This view could have been acquired with imaging sensors operating at different spectral ranges (CCD, FLIR, image intensifier). The input silhouette is preprocessed and compared to those stored in a database, retrieving a small number of potential matches ranked by their similarity to the target silhouette. This set of potential matches is presented to the system operator, who makes the final ship identification. This system makes use of an evolved version of the Curvature Scale Space (CSS) representation. In the proposed approach, it is curvature extrema, instead of zero crossings, that are tracked during silhouette evolution, hence improving robustness and enabling to cope successfully with cases where the standard CCS representation is found to be unstable. Also, the use of local curvature was replaced with the more robust concept of lobe concavity, with significant additional gains in performance. Experimental results on actual operational imagery prove the excellent performance and robustness of the developed method.
Geo-aggregation permits low stretch and routing tables of logarithmical size
Venue: arXiv cs.NI 2005
Year: 2005

This article first addresses applicability of Euclidean models to the domain of Internet routing. Those models are found (limitedly) applicable. Then a simplistic model of routing is constructed for Euclidean plane densely covered with points-routers. The model guarantees low stretch and logarithmical size of routing tables at any node. The paper concludes with a discussion on applicability of the model to real-world Internet routing.
Coding for the Optical Channel: the Ghost-Pulse Constraint
Venue: arXiv cs.IT 2005
Year: 2005

We consider a number of constrained coding techniques that can be used to mitigate a nonlinear effect in the optical fiber channel that causes the formation of spurious pulses, called ``ghost pulses.'' Specifically, if $b_1 b_2 ... b_{n}$ is a sequence of bits sent across an optical channel, such that $b_k=b_l=b_m=1$ for some $k,l,m$ (not necessarily all distinct) but $b_{k+l-m} = 0$, then the ghost-pulse effect causes $b_{k+l-m}$ to change to 1, thereby creating an error. We design and analyze several coding schemes using binary and ternary sequences constrained so as to avoid patterns that give rise to ghost pulses. We also discuss the design of encoders and decoders for these coding schemes.
Cybercars : Past, Present and Future of the Technology
Venue: arXiv cs.RO 2005
Year: 2005

Automobile has become the dominant transport mode in the world in the last century. In order to meet a continuously growing demand for transport, one solution is to change the control approach for vehicle to full driving automation, which removes the driver from the control loop to improve efficiency and reduce accidents. Recent work shows that there are several realistic paths towards this deployment : driving assistance on passenger cars, automated commercial vehicles on dedicated infrastructures, and new forms of urban transport (car-sharing and cybercars). Cybercars have already been put into operation in Europe, and it seems that this approach could lead the way towards full automation on most urban, and later interurban infrastructures. The European project CyberCars has brought many improvements in the technology needed to operate cybercars over the last three years. A new, larger European project is now being prepared to carry this work further in order to meet more ambitious objectives in terms of safety and efficiency. This paper will present past and present technologies and will focus on the future developments.
Markerless Human Motion Capture for Gait Analysis
Venue: arXiv cs.AI 2005
Year: 2005

The aim of our study is to detect balance disorders and a tendency towards the falls in the elderly, knowing gait parameters. In this paper we present a new tool for gait analysis based on markerless human motion capture, from camera feeds. The system introduced here, recovers the 3D positions of several key points of the human body while walking. Foreground segmentation, an articulated body model and particle filtering are basic elements of our approach. No dynamic model is used thus this system can be described as generic and simple to implement. A modified particle filtering algorithm, which we call Interval Particle Filtering, is used to reorganise and search through the model's configurations search space in a deterministic optimal way. This algorithm was able to perform human movement tracking with success. Results from the treatment of a single cam feeds are shown and compared to results obtained using a marker based human motion capture system.