OpenRaiser/Intern-Atlas huggingface dataset:
On the complexity of computing the capacity of codes that avoid forbidden difference patterns
Venue: arXiv cs.IT 2006
Year: 2006

We consider questions related to the computation of the capacity of codes that avoid forbidden difference patterns. The maximal number of $n$-bit sequences whose pairwise differences do not contain some given forbidden difference patterns increases exponentially with $n$. The exponent is the capacity of the forbidden patterns, which is given by the logarithm of the joint spectral radius of a set of matrices constructed from the forbidden difference patterns. We provide a new family of bounds that allows for the approximation, in exponential time, of the capacity with arbitrary high degree of accuracy. We also provide a polynomial time algorithm for the problem of determining if the capacity of a set is positive, but we prove that the same problem becomes NP-hard when the sets of forbidden patterns are defined over an extended set of symbols. Finally, we prove the existence of extremal norms for the sets of matrices arising in the capacity computation. This result makes it possible to apply a specific (even though non polynomial) approximation algorithm. We illustrate this fact by computing exactly the capacity of codes that were only known approximately.
Removing Redundant Arguments Automatically
Venue: arXiv cs.PL 2006
Year: 2006

The application of automatic transformation processes during the formal development and optimization of programs can introduce encumbrances in the generated code that programmers usually (or presumably) do not write. An example is the introduction of redundant arguments in the functions defined in the program. Redundancy of a parameter means that replacing it by any expression does not change the result. In this work, we provide methods for the analysis and elimination of redundant arguments in term rewriting systems as a model for the programs that can be written in more sophisticated languages. On the basis of the uselessness of redundant arguments, we also propose an erasure procedure which may avoid wasteful computations while still preserving the semantics (under ascertained conditions). A prototype implementation of these methods has been undertaken, which demonstrates the practicality of our approach.
New Technologies for Sustainable Urban Transport in Europe
Venue: arXiv cs.RO 2006
Year: 2006

In the past few years, the European Commission has financed several projects to examine how new technologies could improve the sustainability of European cities. These technologies concern new public transportation modes such as guided buses to form high capacity networks similar to light rail but at a lower cost and better flexibility, PRT (Personal Rapid Transit) and cybercars (small urban vehicles with fully automatic driving capabilities to be used in carsharing mode, mostly as a complement to mass transport). They also concern private vehicles with technologies which could improve the efficiency of the vehicles as well as their safety (Intelligent Speed Adaptation, Adaptive Cruise >.Control, Stop&Go, Lane Keeping,...) and how these new vehicles can complement mass transport in the form of car-sharing services.
Oblivious channels
Venue: arXiv cs.IT 2006
Year: 2006

Let C = {x_1,...,x_N} \subset {0,1}^n be an [n,N] binary error correcting code (not necessarily linear). Let e \in {0,1}^n be an error vector. A codeword x in C is said to be "disturbed" by the error e if the closest codeword to x + e is no longer x. Let A_e be the subset of codewords in C that are disturbed by e. In this work we study the size of A_e in random codes C (i.e. codes in which each codeword x_i is chosen uniformly and independently at random from {0,1}^n). Using recent results of Vu [Random Structures and Algorithms 20(3)] on the concentration of non-Lipschitz functions, we show that |A_e| is strongly concentrated for a wide range of values of N and ||e||. We apply this result in the study of communication channels we refer to as "oblivious". Roughly speaking, a channel W(y|x) is said to be oblivious if the error distribution imposed by the channel is independent of the transmitted codeword x. For example, the well studied Binary Symmetric Channel is an oblivious channel. In this work, we define oblivious and partially oblivious channels and present lower bounds on their capacity. The oblivious channels we define have connections to Arbitrarily Varying Channels with state constraints.
Undeniable Signature Schemes Using Braid Groups
Venue: arXiv cs.CR 2006
Year: 2006

Artin's braid groups have been recently suggested as a new source for public-key cryptography. In this paper we propose the first undeniable signature schemes using the conjugacy problem and the decomposition problem in the braid groups which are believed to be hard problems.
Optimal Point-to-Point Trajectory Tracking of Redundant Manipulators using Generalized Pattern Search
Venue: arXiv cs.RO 2006
Year: 2006

Optimal point-to-point trajectory planning for planar redundant manipulator is considered in this study. The main objective is to minimize the sum of the position error of the end-effector at each intermediate point along the trajectory so that the end-effector can track the prescribed trajectory accurately. An algorithm combining Genetic Algorithm and Pattern Search as a Generalized Pattern Search GPS is introduced to design the optimal trajectory. To verify the proposed algorithm, simulations for a 3-D-O-F planar manipulator with different end-effector trajectories have been carried out. A comparison between the Genetic Algorithm and the Generalized Pattern Search shows that The GPS gives excellent tracking performance.
Fast Enumeration of Combinatorial Objects
Venue: arXiv cs.CC 2006
Year: 2006

The problem of ranking can be described as follows. We have a set of combinatorial objects $S$, such as, say, the k-subsets of n things, and we can imagine that they have been arranged in some list, say lexicographically, and we want to have a fast method for obtaining the rank of a given object in the list. This problem is widely known in Combinatorial Analysis, Computer Science and Information Theory. Ranking is closely connected with the hashing problem, especially with perfect hashing and with generating of random combinatorial objects. In Information Theory the ranking problem is closely connected with so-called enumerative encoding, which may be described as follows: there is a set of words $S$ and an enumerative code has to one-to-one encode every $s \in S$ by a binary word $code(s)$. The length of the $code(s)$ must be the same for all $s \in S$. Clearly, $|code (s)|\geq \log |S|$. (Here and below $\log x=\log_{2}x)$.) The suggested method allows the exponential growth of the speed of encoding and decoding for all combinatorial problems of enumeration which are considered, including the enumeration of permutations, compositions and others.
A Theory of Routing for Large-Scale Wireless Ad-Hoc Networks
Venue: arXiv cs.IT 2006
Year: 2006

In this work we develop a new theory to analyse the process of routing in large-scale ad-hoc wireless networks. We use a path integral formulation to examine the properties of the paths generated by different routing strategies in these kinds of networks. Using this theoretical framework, we calculate the statistical distribution of the distances between any source to any destination in the network, hence we are able to deduce a length parameter that is unique for each routing strategy. This parameter, defined as the {\it effective radius}, effectively encodes the routing information required by a node. Analysing the aforementioned statistical distribution for different routing strategies, we obtain a threefold result for practical Large-Scale Wireless Ad-Hoc Networks: 1) We obtain the distribution of the lengths of all the paths in a network for any given routing strategy, 2) We are able to identify "good" routing strategies depending on the evolution of its effective radius as the number of nodes, $N$, increases to infinity, 3) For any routing strategy with finite effective radius, we demonstrate that, in a large-scale network, is equivalent to a random routing strategy and that its transport capacity scales as $Θ(\sqrt{N})$ bit-meters per second, thus retrieving the scaling law that Gupta and Kumar (2000) obtained as the limit for single-route large-scale wireless networks.
Multilevel Coding for Channels with Non-uniform Inputs and Rateless Transmission over the BSC
Venue: arXiv cs.IT 2006
Year: 2006

We consider coding schemes for channels with non-uniform inputs (NUI), where standard linear block codes can not be applied directly. We show that multilevel coding (MLC) with a set of linear codes and a deterministic mapper can achieve the information rate of the channel with NUI. The mapper, however, does not have to be one-to-one. As an application of the proposed MLC scheme, we present a rateless transmission scheme over the binary symmetric channel (BSC).
Stability of Scheduled Message Communication over Degraded Broadcast Channels
Venue: arXiv cs.IT 2006
Year: 2006

We consider scheduled message communication over a discrete memoryless degraded broadcast channel. The framework we consider here models both the random message arrivals and the subsequent reliable communication by suitably combining techniques from queueing theory and information theory. The channel from the transmitter to each of the receivers is quasi-static, flat, and with independent fades across the receivers. Requests for message transmissions are assumed to arrive according to an i.i.d. arrival process. Then, (i) we derive an outer bound to the region of message arrival vectors achievable by the class of stationary scheduling policies, (ii) we show for any message arrival vector that satisfies the outerbound, that there exists a stationary ``state-independent'' policy that results in a stable system for the corresponding message arrival process, and (iii) under two asymptotic regimes, we show that the stability region of nat arrival rate vectors has information-theoretic capacity region interpretation.
Google Web APIs - an Instrument for Webometric Analyses?
Venue: arXiv cs.IR 2006
Year: 2006

This paper introduces Google Web APIs (Google APIs) as an instrument and playground for webometric studies. Several examples of Google APIs implementations are given. Our examples show that this Google Web Service can be used successfully for informetric Internet based studies albeit with some restrictions.
The Perceptron Algorithm: Image and Signal Decomposition, Compression, and Analysis by Iterative Gaussian Blurring
Venue: arXiv cs.CV 2006
Year: 2006

A novel algorithm for tunable compression to within the precision of reproduction targets, or storage, is proposed. The new algorithm is termed the `Perceptron Algorithm', which utilises simple existing concepts in a novel way, has multiple immediate commercial application aspects as well as it opens up a multitude of fronts in computational science and technology. The aims of this paper are to present the concepts underlying the algorithm, observations by its application to some example cases, and the identification of a multitude of potential areas of applications such as: image compression by orders of magnitude, signal compression including sound as well, image analysis in a multilayered detailed analysis, pattern recognition and matching and rapid database searching (e.g. face recognition), motion analysis, biomedical applications e.g. in MRI and CAT scan image analysis and compression, as well as hints on the link of these ideas to the way how biological memory might work leading to new points of view in neural computation. Commercial applications of immediate interest are the compression of images at the source (e.g. photographic equipment, scanners, satellite imaging systems), DVD film compression, pay-per-view downloads acceleration and many others identified in the present paper at its conclusion and future work section.
Fast Lexically Constrained Viterbi Algorithm (FLCVA): Simultaneous Optimization of Speed and Memory
Venue: arXiv cs.CV 2006
Year: 2006

Lexical constraints on the input of speech and on-line handwriting systems improve the performance of such systems. A significant gain in speed can be achieved by integrating in a digraph structure the different Hidden Markov Models (HMM) corresponding to the words of the relevant lexicon. This integration avoids redundant computations by sharing intermediate results between HMM's corresponding to different words of the lexicon. In this paper, we introduce a token passing method to perform simultaneously the computation of the a posteriori probabilities of all the words of the lexicon. The coding scheme that we introduce for the tokens is optimal in the information theory sense. The tokens use the minimum possible number of bits. Overall, we optimize simultaneously the execution speed and the memory requirement of the recognition systems.
Complexity of the Guarded Two-Variable Fragment with Counting Quantifiers
Venue: arXiv cs.LO 2006
Year: 2006

We show that the finite satisfiability problem for the guarded two-variable fragment with counting quantifiers is in EXPTIME. The method employed also yields a simple proof of a result recently obtained by Y. Kazakov, that the satisfiability problem for the guarded two-variable fragment with counting quantifiers is in EXPTIME.
On The Minimum Mean-Square Estimation Error of the Normalized Sum of Independent Narrowband Waves in the Gaussian Channel
Venue: arXiv cs.IT 2006
Year: 2006

The minimum mean-square error of the estimation of a signal where observed from the additive white Gaussian noise (WGN) channel's output, is analyzed. It is assumed that the channel input's signal is composed of a (normalized) sum of N narrowband, mutually independent waves. It is shown that if N goes to infinity, then for any fixed signal energy to noise energy ratio (no mater how big) both the causal minimum mean-square error CMMSE and the non-causal minimum mean-square error MMSE converge to the signal energy at a rate which is proportional to 1/N.
Power Control for User Cooperation
Venue: arXiv cs.IT 2006
Year: 2006

For a fading Gaussian multiple access channel with user cooperation, we obtain the optimal power allocation policies that maximize the rates achievable by block Markov superposition coding. The optimal policies result in a coding scheme that is simpler than the one for a general multiple access channel with generalized feedback. This simpler coding scheme also leads to the possibility of formulating an otherwise non-concave optimization problem as a concave one. Using the channel state information at the transmitters to adapt the powers, we demonstrate significant gains over the achievable rates for existing cooperative systems.
Wreath Products in Stream Cipher Design
Venue: arXiv cs.CR 2006
Year: 2006

The paper develops a novel approach to stream cipher design: Both the state update function and the output function of the corresponding pseudorandom generators are compositions of arithmetic and bitwise logical operations, which are standard instructions of modern microprocessors. Moreover, both the state update function and the output function are being modified dynamically during the encryption. Also, these compositions could be keyed, so the only information available to an attacker is that these functions belong to some exponentially large class. The paper shows that under rather loose conditions the output sequence is uniformly distributed, achieves maximum period length and has high linear complexity and high $\ell$-error linear complexity. Ciphers of this kind are flexible: One could choose a suitable combination of instructions to obtain due performance without affecting the quality of the output sequence. Finally, some evidence is given that a key recovery problem for (reasonably designed) stream ciphers of this kind is intractable up to plausible conjectures.
On the Asymptotic Performance of Multiple Antenna Channels with Fast Channel Feedback
Venue: arXiv cs.IT 2006
Year: 2006

In this paper, we analyze the asymptotic performance of multiple antenna channels where the transmitter has either perfect or finite bit channel state information. Using the diversity-multiplexing tradeoff to characterize the system performance, we demonstrate that channel feedback can fundamentally change the system behavior. Even one-bit of information can increase the diversity order of the system compared to the system with no transmitter information. In addition, as the amount of channel information at the transmitter increases, the diversity order for each multiplexing gain increases and goes to infinity for perfect transmitter information. The major reason for diversity order gain is a "location-dependent" temporal power control, which adapts the power control strategy based on the average channel conditions of the channel.
Analysis of Belief Propagation for Non-Linear Problems: The Example of CDMA (or: How to Prove Tanaka's Formula)
Venue: arXiv cs.IT 2006
Year: 2006

We consider the CDMA (code-division multiple-access) multi-user detection problem for binary signals and additive white gaussian noise. We propose a spreading sequences scheme based on random sparse signatures, and a detection algorithm based on belief propagation (BP) with linear time complexity. In the new scheme, each user conveys its power onto a finite number of chips l, in the large system limit. We analyze the performances of BP detection and prove that they coincide with the ones of optimal (symbol MAP) detection in the l->\infty limit. In the same limit, we prove that the information capacity of the system converges to Tanaka's formula for random `dense' signatures, thus providing the first rigorous justification of this formula. Apart from being computationally convenient, the new scheme allows for optimization in close analogy with irregular low density parity check code ensembles.
Approximate Weighted Farthest Neighbors and Minimum Dilation Stars
Venue: arXiv cs.CG 2006
Year: 2006

We provide an efficient reduction from the problem of querying approximate multiplicatively weighted farthest neighbors in a metric space to the unweighted problem. Combining our techniques with core-sets for approximate unweighted farthest neighbors, we show how to find (1+epsilon)-approximate farthest neighbors in time O(log n) per query in D-dimensional Euclidean space for any constants D and epsilon. As an application, we find an O(n log n) expected time algorithm for choosing the center of a star topology network connecting a given set of points, so as to approximately minimize the maximum dilation between any pair of points.
Réseaux d'Automates de Caianiello Revisité
Venue: arXiv cs.NE 2006
Year: 2006

We exhibit a family of neural networks of McCulloch and Pitts of size $2nk+2$ which can be simulated by a neural networks of Caianiello of size $2n+2$ and memory length $k$. This simulation allows us to find again one of the result of the following article: [Cycles exponentiels des réseaux de Caianiello et compteurs en arithmétique redondante, Technique et Science Informatiques Vol. 19, pages 985-1008] on the existence of neural networks of Caianiello of size $2n+2$ and memory length $k$ which describes a cycle of length $k \times 2^{nk}$.
On the utility of the multimodal problem generator for assessing the performance of Evolutionary Algorithms
Venue: arXiv cs.NE 2006
Year: 2006

This paper looks in detail at how an evolutionary algorithm attempts to solve instances from the multimodal problem generator. The paper shows that in order to consistently reach the global optimum, an evolutionary algorithm requires a population size that should grow at least linearly with the number of peaks. It is also shown a close relationship between the supply and decision making issues that have been identified previously in the context of population sizing models for additively decomposable problems. The most important result of the paper, however, is that solving an instance of the multimodal problem generator is like solving a peak-in-a-haystack, and it is argued that evolutionary algorithms are not the best algorithms for such a task. Finally, and as opposed to what several researchers have been doing, it is our strong belief that the multimodal problem generator is not adequate for assessing the performance of evolutionary algorithms.
How to Beat the Adaptive Multi-Armed Bandit
Venue: arXiv cs.DS 2006
Year: 2006

The multi-armed bandit is a concise model for the problem of iterated decision-making under uncertainty. In each round, a gambler must pull one of $K$ arms of a slot machine, without any foreknowledge of their payouts, except that they are uniformly bounded. A standard objective is to minimize the gambler's regret, defined as the gambler's total payout minus the largest payout which would have been achieved by any fixed arm, in hindsight. Note that the gambler is only told the payout for the arm actually chosen, not for the unchosen arms. Almost all previous work on this problem assumed the payouts to be non-adaptive, in the sense that the distribution of the payout of arm $j$ in round $i$ is completely independent of the choices made by the gambler on rounds $1, \dots, i-1$. In the more general model of adaptive payouts, the payouts in round $i$ may depend arbitrarily on the history of past choices made by the algorithm. We present a new algorithm for this problem, and prove nearly optimal guarantees for the regret against both non-adaptive and adaptive adversaries. After $T$ rounds, our algorithm has regret $O(\sqrt{T})$ with high probability (the tail probability decays exponentially). This dependence on $T$ is best possible, and matches that of the full-information version of the problem, in which the gambler is told the payouts for all $K$ arms after each round. Previously, even for non-adaptive payouts, the best high-probability bounds known were $O(T^{2/3})$, due to Auer, Cesa-Bianchi, Freund and Schapire. The expected regret of their algorithm is $O(T^{1/2}) for non-adaptive payouts, but as we show, $Ω(T^{2/3})$ for adaptive payouts.
Natural Economics
Venue: arXiv cs.OH 2006
Year: 2006

A few considerations on the nature of Economics and its relationship to human communities through the prism of Self-Organizing-Systems.
The approximability of MAX CSP with fixed-value constraints
Venue: arXiv cs.CC 2006
Year: 2006

In the maximum constraint satisfaction problem (MAX CSP), one is given a finite collection of (possibly weighted) constraints on overlapping sets of variables, and the goal is to assign values from a given finite domain to the variables so as to maximize the number (or the total weight, for the weighted case) of satisfied constraints. This problem is NP-hard in general, and, therefore, it is natural to study how restricting the allowed types of constraints affects the approximability of the problem. In this paper, we show that any MAX CSP problem with a finite set of allowed constraint types, which includes all fixed-value constraints (i.e., constraints of the form x=a), is either solvable exactly in polynomial-time or else is APX-complete, even if the number of occurrences of variables in instances are bounded. Moreover, we present a simple description of all polynomial-time solvable cases of our problem. This description relies on the well-known algebraic combinatorial property of supermodularity.
Pants Decomposition of the Punctured Plane
Venue: arXiv cs.CG 2006
Year: 2006

A pants decomposition of an orientable surface S is a collection of simple cycles that partition S into pants, i.e., surfaces of genus zero with three boundary cycles. Given a set P of n points in the plane, we consider the problem of computing a pants decomposition of the surface S which is the plane minus P, of minimum total length. We give a polynomial-time approximation scheme using Mitchell's guillotine rectilinear subdivisions. We give a quartic-time algorithm to compute the shortest pants decomposition of S when the cycles are restricted to be axis-aligned boxes, and a quadratic-time algorithm when all the points lie on a line; both exact algorithms use dynamic programming with Yao's speedup.