OpenRaiser/Intern-Atlas huggingface dataset:
Continued Fraction Expansion as Isometry: The Law of the Iterated Logarithm for Linear, Jump, and 2--Adic Complexity
Venue: arXiv cs.IT 2005
Year: 2005

In the cryptanalysis of stream ciphers and pseudorandom sequences, the notions of linear, jump, and 2-adic complexity arise naturally to measure the (non)randomness of a given string. We define an isometry K on F_q^\infty that is the precise equivalent to Euclid's algorithm over the reals to calculate the continued fraction expansion of a formal power series. The continued fraction expansion allows to deduce the linear and jump complexity profiles of the input sequence. Since K is an isometry, the resulting F_q^\infty-sequence is i.i.d. for i.i.d. input. Hence the linear and jump complexity profiles may be modelled via Bernoulli experiments (for F_2: coin tossing), and we can apply the very precise bounds as collected by Revesz, among others the Law of the Iterated Logarithm. The second topic is the 2-adic span and complexity, as defined by Goresky and Klapper. We derive again an isometry, this time on the dyadic integers Z_2 which induces an isometry A on F_2}^\infty. The corresponding jump complexity behaves on average exactly like coin tossing. Index terms: Formal power series, isometry, linear complexity, jump complexity, 2-adic complexity, 2-adic span, law of the iterated logarithm, Levy classes, stream ciphers, pseudorandom sequences
Artificial Agents and Speculative Bubbles
Venue: arXiv cs.GT 2005
Year: 2005

Pertaining to Agent-based Computational Economics (ACE), this work presents two models for the rise and downfall of speculative bubbles through an exchange price fixing based on double auction mechanisms. The first model is based on a finite time horizon context, where the expected dividends decrease along time. The second model follows the {\em greater fool} hypothesis; the agent behaviour depends on the comparison of the estimated risk with the greater fool's. Simulations shed some light on the influent parameters and the necessary conditions for the apparition of speculative bubbles in an asset market within the considered framework.
Evaluating Mobility Pattern Space Routing for DTNs
Venue: arXiv cs.NI 2005
Year: 2005

Because a delay tolerant network (DTN) can often be partitioned, the problem of routing is very challenging. However, routing benefits considerably if one can take advantage of knowledge concerning node mobility. This paper addresses this problem with a generic algorithm based on the use of a high-dimensional Euclidean space, that we call MobySpace, constructed upon nodes' mobility patterns. We provide here an analysis and the large scale evaluation of this routing scheme in the context of ambient networking by replaying real mobility traces. The specific MobySpace evaluated is based on the frequency of visit of nodes for each possible location. We show that the MobySpace can achieve good performance compared to that of the other algorithms we implemented, especially when we perform routing on the nodes that have a high connection time. We determine that the degree of homogeneity of mobility patterns of nodes has a high impact on routing. And finally, we study the ability of nodes to learn their own mobility patterns.
An Infeasibility Result for the Multiterminal Source-Coding Problem
Venue: arXiv cs.IT 2005
Year: 2005

We prove a new outer bound on the rate-distortion region for the multiterminal source-coding problem. This bound subsumes the best outer bound in the literature and improves upon it strictly in some cases. The improved bound enables us to obtain a new, conclusive result for the binary erasure version of the "CEO problem." The bound recovers many of the converse results that have been established for special cases of the problem, including the recent one for the Gaussian version of the CEO problem.
Channel Model and Upper Bound on the Information Capacity of the Fiber Optical Communication Channel Based on the Effects of XPM Induced Nonlinearity
Venue: arXiv cs.IT 2005
Year: 2005

An upper bound to the information capacity of a wavelength-division multi- plexed optical fiber communication system is derived in a model incorporating the nonlinear propagation effects of cross-phase modulation (XPM). This work is based on the paper by Mitra et al., finding lower bounds to the channel capacity, in which physical models for propagation are used to calculate statistical properties of the conditional probability distribution relating input and output in a single WDM channel. In this paper we present a tractable channel model incorporating the effects of cross phase modulation. Using this model we find an upper bound to the information capacity of the fiber optical communication channel at high SNR. The results provide physical insight into the manner in which nonlinearities degrade the information capacity.
A Game-Theoretic Approach to Energy-Efficient Power Control in Multi-Carrier CDMA Systems
Venue: arXiv cs.IT 2005
Year: 2005

A game-theoretic model for studying power control in multi-carrier CDMA systems is proposed. Power control is modeled as a non-cooperative game in which each user decides how much power to transmit over each carrier to maximize its own utility. The utility function considered here measures the number of reliable bits transmitted over all the carriers per Joule of energy consumed and is particularly suitable for networks where energy efficiency is important. The multi-dimensional nature of users' strategies and the non-quasiconcavity of the utility function make the multi-carrier problem much more challenging than the single-carrier or throughput-based-utility case. It is shown that, for all linear receivers including the matched filter, the decorrelator, and the minimum-mean-square-error (MMSE) detector, a user's utility is maximized when the user transmits only on its "best" carrier. This is the carrier that requires the least amount of power to achieve a particular target signal-to-interference-plus-noise ratio (SINR) at the output of the receiver. The existence and uniqueness of Nash equilibrium for the proposed power control game are studied. In particular, conditions are given that must be satisfied by the channel gains for a Nash equilibrium to exist, and the distribution of the users among the carriers at equilibrium is also characterized. In addition, an iterative and distributed algorithm for reaching the equilibrium (when it exists) is presented. It is shown that the proposed approach results in significant improvements in the total utility achieved at equilibrium compared to a single-carrier system and also to a multi-carrier system in which each user maximizes its utility over each carrier independently.
Approximately Universal Codes over Slow Fading Channels
Venue: arXiv cs.IT 2005
Year: 2005

Performance of reliable communication over a coherent slow fading channel at high SNR is succinctly captured as a fundamental tradeoff between diversity and multiplexing gains. We study the problem of designing codes that optimally tradeoff the diversity and multiplexing gains. Our main contribution is a precise characterization of codes that are universally tradeoff-optimal, i.e., they optimally tradeoff the diversity and multiplexing gains for every statistical characterization of the fading channel. We denote this characterization as one of approximate universality where the approximation is in the connection between error probability and outage capacity with diversity and multiplexing gains, respectively. The characterization of approximate universality is then used to construct new coding schemes as well as to show optimality of several schemes proposed in the space-time coding literature.
A bound on Grassmannian codes
Venue: arXiv cs.IT 2005
Year: 2005

We give a new asymptotic upper bound on the size of a code in the Grassmannian space. The bound is better than the upper bounds known previously in the entire range of distances except very large values.
Ensuring Trust in One Time Exchanges: Solving the QoS Problem
Venue: arXiv cs.GT 2005
Year: 2005

We describe a pricing structure for the provision of IT services that ensures trust without requiring repeated interactions between service providers and users. It does so by offering a pricing structure that elicits truthful reporting of quality of service (QoS) by providers while making them profitable. This mechanism also induces truth-telling on the part of users reserving the service.
Capacity of Differential versus Non-Differential Unitary Space-Time Modulation for MIMO channels
Venue: arXiv cs.IT 2005
Year: 2005

Differential Unitary Space-Time Modulation (DUSTM) and its earlier nondifferential counterpart, USTM, permit high-throughput MIMO communication entirely without the possession of channel state information (CSI) by either the transmitter or the receiver. For an isotropically random unitary input we obtain the exact closed-form expression for the probability density of the DUSTM received signal, which permits the straightforward Monte Carlo evaluation of its mutual information. We compare the performance of DUSTM and USTM through both numerical computations of mutual information and through the analysis of low- and high-SNR asymptotic expressions. In our comparisons the symbol durations of the equivalent unitary space-time signals are both equal to T, as are the number of receive antennas N. For DUSTM the number of transmit antennas is constrained by the scheme to be M = T/2, while USTM has no such constraint. If DUSTM and USTM utilize the same number of transmit antennas at high SNR's the normalized mutual information of the differential and the nondifferential schemes expressed in bits/sec/Hz are asymptotically equal, with the differential scheme performing somewhat better, while at low SNR's the normalized mutual information of DUSTM is asymptotically twice the normalized mutual information of USTM. If, instead, USTM utilizes the optimum number of transmit antennas then USTM can outperform DUSTM at sufficiently low SNR's.
Points on Computable Curves
Venue: arXiv cs.CC 2005
Year: 2005

The ``analyst's traveling salesman theorem'' of geometric measure theory characterizes those subsets of Euclidean space that are contained in curves of finite length. This result, proven for the plane by Jones (1990) and extended to higher-dimensional Euclidean spaces by Okikiolu (1991), says that a bounded set $K$ is contained in some curve of finite length if and only if a certain ``square beta sum'', involving the ``width of $K$'' in each element of an infinite system of overlapping ``tiles'' of descending size, is finite. In this paper we characterize those {\it points} of Euclidean space that lie on {\it computable} curves of finite length by formulating and proving a computable extension of the analyst's traveling salesman theorem. Our extension says that a point in Euclidean space lies on some computable curve of finite length if and only if it is ``permitted'' by some computable ``Jones constriction''. A Jones constriction here is an explicit assignment of a rational cylinder to each of the above-mentioned tiles in such a way that, when the radius of the cylinder corresponding to a tile is used in place of the ``width of $K$'' in each tile, the square beta sum is finite. A point is permitted by a Jones constriction if it is contained in the cylinder assigned to each tile containing the point. The main part of our proof is the construction of a computable curve of finite length traversing all the points permitted by a given Jones constriction. Our construction uses the main ideas of Jones's ``farthest insertion'' construction, but our algorithm for computing the curve must work exclusively with the Jones constriction itself, because it has no direct access to the (typically uncomputable) points permitted by the Jones constriction.
Mastermind is NP-Complete
Venue: arXiv cs.CC 2005
Year: 2005

In this paper we show that the Mastermind Satisfiability Problem (MSP) is NP-complete. The Mastermind is a popular game which can be turned into a logical puzzle called Mastermind Satisfiability Problem in a similar spirit to the Minesweeper puzzle. By proving that MSP is NP-complete, we reveal its intrinsic computational property that makes it challenging and interesting. This serves as an addition to our knowledge about a host of other puzzles, such as Minesweeper, Mah-Jongg, and the 15-puzzle.
Tradeoffs in Metaprogramming
Venue: arXiv cs.PL 2005
Year: 2005

The design of metaprogramming languages requires appreciation of the tradeoffs that exist between important language characteristics such as safety properties, expressive power, and succinctness. Unfortunately, such tradeoffs are little understood, a situation we try to correct by embarking on a study of metaprogramming language tradeoffs using tools from computability theory. Safety properties of metaprograms are in general undecidable; for example, the property that a metaprogram always halts and produces a type-correct instance is $Π^0_2$-complete. Although such safety properties are undecidable, they may sometimes be captured by a restricted language, a notion we adapt from complexity theory. We give some sufficient conditions and negative results on when languages capturing properties can exist: there can be no languages capturing total correctness for metaprograms, and no `functional' safety properties above $Σ^0_3$ can be captured. We prove that translating a metaprogram from a general-purpose to a restricted metaprogramming language capturing a property is tantamount to proving that property for the metaprogram. Surprisingly, when one shifts perspective from programming to metaprogramming, the corresponding safety questions do not become substantially harder -- there is no `jump' of Turing degree for typical safety properties.
Performance versus Complexity Per Iteration for Low-Density Parity-Check Codes: An Information-Theoretic Approach
Venue: arXiv cs.IT 2005
Year: 2005

The paper is focused on the tradeoff between performance and decoding complexity per iteration for LDPC codes in terms of their gap (in rate) to capacity. The study of this tradeoff is done via information-theoretic bounds which also enable to get an indication on the sub-optimality of message-passing iterative decoding algorithms (as compared to optimal ML decoding). The bounds are generalized for parallel channels, and are applied to ensembles of punctured LDPC codes where both intentional and random puncturing are addressed. This work suggests an improvement in the tightness of some information-theoretic bounds which were previously derived by Burshtein et al. and by Sason and Urbanke.
On The Effectiveness of Kolmogorov Complexity Estimation to Discriminate Semantic Types
Venue: arXiv cs.NI 2005
Year: 2005

We present progress on the experimental validation of a fundamental and universally applicable vulnerability analysis framework that is capable of identifying new types of vulnerabilities before attackers innovate attacks. This new framework proactively identifies system components that are vulnerable based upon their Kolmogorov Complexity estimates and it facilitates prediction of previously unknown vulnerabilities that are likely to be exploited by future attack methods. A tool that utilizes a growing library of complexity estimators is presented. This work is an incremental step towards validation of the concept of complexity-based vulnerability analysis. In particular, results indicate that data types (semantic types) can be identified by estimates of their complexity. Thus, a map of complexity can identify suspicious types, such as executable data embedded within passive data types, without resorting to predefined headers, signatures, or other limiting a priori information.
Construction of Turbo Code Interleavers from 3-Regular Hamiltonian Graphs
Venue: arXiv cs.IT 2005
Year: 2005

In this letter we present a new construction of interleavers for turbo codes from 3-regular Hamiltonian graphs. The interleavers can be generated using a few parameters, which can be selected in such a way that the girth of the interleaver graph (IG) becomes large, inducing a high summary distance. The size of the search space for these parameters is derived. The proposed interleavers themselves work as their de-interleavers.
Gaussian Channels with Feedback: Optimality, Fundamental Limitations, and Connections of Communication, Estimation, and Control
Venue: arXiv cs.IT 2005
Year: 2005

Gaussian channels with memory and with noiseless feedback have been widely studied in the information theory literature. However, a coding scheme to achieve the feedback capacity is not available. In this paper, a coding scheme is proposed to achieve the feedback capacity for Gaussian channels. The coding scheme essentially implements the celebrated Kalman filter algorithm, and is equivalent to an estimation system over the same channel without feedback. It reveals that the achievable information rate of the feedback communication system can be alternatively given by the decay rate of the Cramer-Rao bound of the associated estimation system. Thus, combined with the control theoretic characterizations of feedback communication (proposed by Elia), this implies that the fundamental limitations in feedback communication, estimation, and control coincide. This leads to a unifying perspective that integrates information, estimation, and control. We also establish the optimality of the Kalman filtering in the sense of information transmission, a supplement to the optimality of Kalman filtering in the sense of information processing proposed by Mitter and Newton. In addition, the proposed coding scheme generalizes the Schalkwijk-Kailath codes and reduces the coding complexity and coding delay. The construction of the coding scheme amounts to solving a finite-dimensional optimization problem. A simplification to the optimal stationary input distribution developed by Yang, Kavcic, and Tatikonda is also obtained. The results are verified in a numerical example.
A Note on the Complexity of Computing the Smallest Four-Coloring of Planar Graphs
Venue: arXiv cs.CC 2006
Year: 2006

We show that computing the lexicographically first four-coloring for planar graphs is P^{NP}-hard. This result optimally improves upon a result of Khuller and Vazirani who prove this problem to be NP-hard, and conclude that it is not self-reducible in the sense of Schnorr, assuming P \neq NP. We discuss this application to non-self-reducibility and provide a general related result.
Deductive Algorithmic Knowledge
Venue: arXiv cs.AI 2006
Year: 2006

The framework of algorithmic knowledge assumes that agents use algorithms to compute the facts they explicitly know. In many cases of interest, a deductive system, rather than a particular algorithm, captures the formal reasoning used by the agents to compute what they explicitly know. We introduce a logic for reasoning about both implicit and explicit knowledge with the latter defined with respect to a deductive system formalizing a logical theory for agents. The highly structured nature of deductive systems leads to very natural axiomatizations of the resulting logic when interpreted over any fixed deductive system. The decision problem for the logic, in the presence of a single agent, is NP-complete in general, no harder than propositional logic. It remains NP-complete when we fix a deductive system that is decidable in nondeterministic polynomial time. These results extend in a straightforward way to multiple agents.
Abstract Canonical Inference
Venue: arXiv cs.LO 2006
Year: 2006

An abstract framework of canonical inference is used to explore how different proof orderings induce different variants of saturation and completeness. Notions like completion, paramodulation, saturation, redundancy elimination, and rewrite-system reduction are connected to proof orderings. Fairness of deductive mechanisms is defined in terms of proof orderings, distinguishing between (ordinary) "fairness," which yields completeness, and "uniform fairness," which yields saturation.
A Decidable Probability Logic for Timed Probabilistic Systems
Venue: arXiv cs.LO 2006
Year: 2006

In this paper we extend the predicate logic introduced in [Beauquier et al. 2002] in order to deal with Semi-Markov Processes. We prove that with respect to qualitative probabilistic properties, model checking is decidable for this logic applied to Semi-Markov Processes. Furthermore we apply our logic to Probabilistic Timed Automata considering classical and urgent semantics, and considering also predicates on clock. We prove that results on Semi Markov Processes hold also for Probabilistic Timed Automata for both the two semantics considered. Moreover, we prove that results for Markov Processes shown in [Beauquier et al. 2002] are extensible to Probabilistic Timed Automata where urgent semantics is considered.
Is entanglement necessary to have unconditional security in quantum bit commitment ?
Venue: arXiv cs.CR 2006
Year: 2006

A simple un-entanglement based quantum bit commitment scheme is presented. Although commitment is unconditionally secure but concealment is not.
Les représentations génétiques d'objets : simples analogies ou modèles pertinents ? Le point de vue de l' "évolutique".<br>–––<br>Genetic representations of objects : simple analogies or efficient models ? The "evolutic" point of view
Venue: arXiv cs.AI 2006
Year: 2006

Depuis une trentaine d'années, les ingénieurs utilisent couramment des analogies avec l'évolution naturelle pour optimiser des dispositifs techniques. Le plus souvent, ces méthodes "génétiques" ou "évolutionnaires" sont considérées uniquement du point de vue pratique, comme des méthodes d'optimisation performantes, qu'on peut utiliser à la place d'autres méthodes (gradients, simplexes, ...). Dans cet article, nous essayons de montrer que les sciences et les techniques, mais aussi les organisations humaines, et généralement tous les systèmes complexes, obéissent à des lois d'évolution dont la génétique est un bon modèle représentatif, même si gênes et chromosomes sont "virtuels" : ainsi loin d'être seulement un outil ponctuel d'aide à la synthèse de solutions technologiques, la représentation génétique est-elle un modèle dynamique global de l'évolution du monde façonné par l'agitation humaine.––––For thirty years, engineers commonly use analogies with natural evolution to optimize technical devices. More often that not, these "genetic" or "evolutionary" methods are only view as efficient tools, which could replace other optimization techniques (gradient methods, simplex, ...). In this paper, we try to show that sciences, techniques, human organizations, and more generally all complex systems, obey to evolution rules, whose the genetic is a good representative model, even if genes and chromosomes are "virtual". Thus, the genetic representation is not only a specific tool helping for the design of technological solutions, but also a global and dynamic model for the action of the human agitation on our world.
Non-asymptotic calibration and resolution
Venue: arXiv cs.LG 2006
Year: 2006

We analyze a new algorithm for probability forecasting of binary observations on the basis of the available data, without making any assumptions about the way the observations are generated. The algorithm is shown to be well calibrated and to have good resolution for long enough sequences of observations and for a suitable choice of its parameter, a kernel on the Cartesian product of the forecast space $[0,1]$ and the data space. Our main results are non-asymptotic: we establish explicit inequalities, shown to be tight, for the performance of the algorithm.