OpenRaiser/Intern-Atlas huggingface dataset:
Statistical mechanics of neocortical interactions: Portfolio of Physiological Indicators
Venue: arXiv cs.CE 2006
Year: 2006

There are several kinds of non-invasive imaging methods that are used to collect data from the brain, e.g., EEG, MEG, PET, SPECT, fMRI, etc. It is difficult to get resolution of information processing using any one of these methods. Approaches to integrate data sources may help to get better resolution of data and better correlations to behavioral phenomena ranging from attention to diagnoses of disease. The approach taken here is to use algorithms developed for the author's Trading in Risk Dimensions (TRD) code using modern methods of copula portfolio risk management, with joint probability distributions derived from the author's model of statistical mechanics of neocortical interactions (SMNI). The author's Adaptive Simulated Annealing (ASA) code is for optimizations of training sets, as well as for importance-sampling. Marginal distributions will be evolved to determine their expected duration and stability using algorithms developed by the author, i.e., PATHTREE and PATHINT codes.
On the time complexity of 2-tag systems and small universal Turing machines
Venue: arXiv cs.CC 2006
Year: 2006

We show that 2-tag systems efficiently simulate Turing machines. As a corollary we find that the small universal Turing machines of Rogozhin, Minsky and others simulate Turing machines in polynomial time. This is an exponential improvement on the previously known simulation time overhead and improves a forty year old result in the area of small universal Turing machines.
Network Information Flow in Small World Networks
Venue: arXiv cs.IT 2006
Year: 2006

Recent results from statistical physics show that large classes of complex networks, both man-made and of natural origin, are characterized by high clustering properties yet strikingly short path lengths between pairs of nodes. This class of networks are said to have a small-world topology. In the context of communication networks, navigable small-world topologies, i.e. those which admit efficient distributed routing algorithms, are deemed particularly effective, for example in resource discovery tasks and peer-to-peer applications. Breaking with the traditional approach to small-world topologies that privileges graph parameters pertaining to connectivity, and intrigued by the fundamental limits of communication in networks that exploit this type of topology, we investigate the capacity of these networks from the perspective of network information flow. Our contribution includes upper and lower bounds for the capacity of standard and navigable small-world models, and the somewhat surprising result that, with high probability, random rewiring does not alter the capacity of a small-world network.
Isolation Support for Service-based Applications: A Position Paper
Venue: arXiv cs.DB 2006
Year: 2006

In this paper, we propose an approach to providing the benefits of isolation in service-oriented applications where it is not feasible to hold traditional locks for ACID transactions. Our technique, called "Promises", provides an uniform view for clients which covers a wide range of implementation techniques on the service side, all allowing the client to check a condition and then later rely on that condition still holding.
Statistical Mechanics of On-line Learning when a Moving Teacher Goes around an Unlearnable True Teacher
Venue: arXiv cs.LG 2006
Year: 2006

In the framework of on-line learning, a learning machine might move around a teacher due to the differences in structures or output functions between the teacher and the learning machine. In this paper we analyze the generalization performance of a new student supervised by a moving machine. A model composed of a fixed true teacher, a moving teacher, and a student is treated theoretically using statistical mechanics, where the true teacher is a nonmonotonic perceptron and the others are simple perceptrons. Calculating the generalization errors numerically, we show that the generalization errors of a student can temporarily become smaller than that of a moving teacher, even if the student only uses examples from the moving teacher. However, the generalization error of the student eventually becomes the same value with that of the moving teacher. This behavior is qualitatively different from that of a linear model.
Power Assignment Problems in Wireless Communication
Venue: arXiv cs.CG 2006
Year: 2006

A fundamental class of problems in wireless communication is concerned with the assignment of suitable transmission powers to wireless devices/stations such that the resulting communication graph satisfies certain desired properties and the overall energy consumed is minimized. Many concrete communication tasks in a wireless network like broadcast, multicast, point-to-point routing, creation of a communication backbone, etc. can be regarded as such a power assignment problem. This paper considers several problems of that kind; for example one problem studied before in \cite{Carrots, Bilo} aims to select and assign powers to $k$ of the stations such that all other stations are within reach of at least one of the selected stations. We improve the running time for obtaining a $(1+ε)$-approximate solution for this problem from $n^{((α/ε)^{O(d)})}$ as reported by Bilo et al. (\cite{Bilo}) to $O(n+ {(\frac{k^{2d+1}}{ε^d})}^{\min{\{2k, (α/ε)^{O(d)} \}}})$ that is, we obtain a running time that is \emph{linear} in the network size. Further results include a constant approximation algorithm for the TSP problem under squared (non-metric!) edge costs, which can be employed to implement a novel data aggregation protocol, as well as efficient schemes to perform $k$-hop multicasts.
Electronic Laboratory Notebook Assisting Reflectance Spectrometry in Legal Medicine
Venue: arXiv cs.DB 2006
Year: 2006

Reflectance spectrometry is a fast and reliable method for the characterisation of human skin if the spectra are analysed with respect to a physical model describing the optical properties of human skin. For a field study performed at the Institute of Legal Medicine and the Freiburg Materials Research Center of the University of Freiburg an electronic laboratory notebook has been developed, which assists in the recording, management, and analysis of reflectance spectra. The core of the electronic laboratory notebook is a MySQL database. It is filled with primary data via a web interface programmed in Java, which also enables the user to browse the database and access the results of data analysis. These are carried out by Matlab, Tcl and Python scripts, which retrieve the primary data from the electronic laboratory notebook, perform the analysis, and store the results in the database for further usage.
Exact solutions for the two- and all-terminal reliabilities of a simple ladder network
Venue: arXiv cs.PF 2006
Year: 2006

The exact calculation of network reliability in a probabilistic context has been a long-standing issue of practical importance, but a difficult one, even for planar graphs, with perfect nodes and with edges of identical reliability p. Many approaches (determination of bounds, sums of disjoint products algorithms, Monte Carlo evaluations, studies of the reliability polynomials, etc.) can only provide approximations when the network's size increases. We consider here a ladder graph of arbitrary size corresponding to real-life network configurations, and give the exact, analytical solutions for the all- and two-terminal reliabilities. These solutions use transfer matrices, in which individual reliabilities of edges and nodes are taken into account. The special case of identical edge and node reliabilities -- p and rho, respectively -- is solved. We show that the zeros of the two-terminal reliability polynomial exhibit structures which differ substantially for seemingly similar networks, and we compare the sensitivity of various edges. We discuss how the present work may be further extended to lead to a catalog of exactly solvable networks in terms of reliability, which could be useful as elementary bricks for a new and improved set of bounds or benchmarks in the general case.
Magnification Laws of Winner-Relaxing and Winner-Enhancing Kohonen Feature Maps
Venue: arXiv cs.NE 2006
Year: 2006

Self-Organizing Maps are models for unsupervised representation formation of cortical receptor fields by stimuli-driven self-organization in laterally coupled winner-take-all feedforward structures. This paper discusses modifications of the original Kohonen model that were motivated by a potential function, in their ability to set up a neural mapping of maximal mutual information. Enhancing the winner update, instead of relaxing it, results in an algorithm that generates an infomax map corresponding to magnification exponent of one. Despite there may be more than one algorithm showing the same magnification exponent, the magnification law is an experimentally accessible quantity and therefore suitable for quantitative description of neural optimization principles.
On Almost Periodicity Criteria for Morphic Sequences in Some Particular Cases
Venue: arXiv cs.DM 2007
Year: 2007

In some particular cases we give criteria for morphic sequences to be almost periodic (=uniformly recurrent). Namely, we deal with fixed points of non-erasing morphisms and with automatic sequences. In both cases a polynomial-time algorithm solving the problem is found. A result more or less supporting the conjecture of decidability of the general problem is given.
The Complexity of HCP in Digraps with Degree Bound Two
Venue: arXiv cs.CC 2007
Year: 2007

The Hamiltonian cycle problem (HCP) in digraphs D with degree bound two is solved by two mappings in this paper. The first bijection is between an incidence matrix C_{nm} of simple digraph and an incidence matrix F of balanced bipartite undirected graph G; The second mapping is from a perfect matching of G to a cycle of D. It proves that the complexity of HCP in D is polynomial, and finding a second non-isomorphism Hamiltonian cycle from a given Hamiltonian digraph with degree bound two is also polynomial. Lastly it deduces P=NP base on the results.
A Low Complexity Algorithm and Architecture for Systematic Encoding of Hermitian Codes
Venue: arXiv cs.IT 2007
Year: 2007

We present an algorithm for systematic encoding of Hermitian codes. For a Hermitian code defined over GF(q^2), the proposed algorithm achieves a run time complexity of O(q^2) and is suitable for VLSI implementation. The encoder architecture uses as main blocks q varying-rate Reed-Solomon encoders and achieves a space complexity of O(q^2) in terms of finite field multipliers and memory elements.
Empirical analysis and statistical modeling of attack processes based on honeypots
Venue: arXiv cs.PF 2007
Year: 2007

Honeypots are more and more used to collect data on malicious activities on the Internet and to better understand the strategies and techniques used by attackers to compromise target systems. Analysis and modeling methodologies are needed to support the characterization of attack processes based on the data collected from the honeypots. This paper presents some empirical analyses based on the data collected from the Leurr{é}.com honeypot platforms deployed on the Internet and presents some preliminary modeling studies aimed at fulfilling such objectives.
Cross-Layer Optimization of MIMO-Based Mesh Networks with Gaussian Vector Broadcast Channels
Venue: arXiv cs.IT 2007
Year: 2007

MIMO technology is one of the most significant advances in the past decade to increase channel capacity and has a great potential to improve network capacity for mesh networks. In a MIMO-based mesh network, the links outgoing from each node sharing the common communication spectrum can be modeled as a Gaussian vector broadcast channel. Recently, researchers showed that ``dirty paper coding'' (DPC) is the optimal transmission strategy for Gaussian vector broadcast channels. So far, there has been little study on how this fundamental result will impact the cross-layer design for MIMO-based mesh networks. To fill this gap, we consider the problem of jointly optimizing DPC power allocation in the link layer at each node and multihop/multipath routing in a MIMO-based mesh networks. It turns out that this optimization problem is a very challenging non-convex problem. To address this difficulty, we transform the original problem to an equivalent problem by exploiting the channel duality. For the transformed problem, we develop an efficient solution procedure that integrates Lagrangian dual decomposition method, conjugate gradient projection method based on matrix differential calculus, cutting-plane method, and subgradient method. In our numerical example, it is shown that we can achieve a network performance gain of 34.4% by using DPC.
Differential Diversity Reception of MDPSK over Independent Rayleigh Channels with Nonidentical Branch Statistics and Asymmetric Fading Spectrum
Venue: arXiv cs.IT 2007
Year: 2007

This paper is concerned with optimum diversity receiver structure and its performance analysis of differential phase shift keying (DPSK) with differential detection over nonselective, independent, nonidentically distributed, Rayleigh fading channels. The fading process in each branch is assumed to have an arbitrary Doppler spectrum with arbitrary Doppler bandwidth, but to have distinct, asymmetric fading power spectral density characteristic. Using 8-DPSK as an example, the average bit error probability (BEP) of the optimum diversity receiver is obtained by calculating the BEP for each of the three individual bits. The BEP results derived are given in exact, explicit, closed-form expressions which show clearly the behavior of the performance as a function of various system parameters.
A Doubly Distributed Genetic Algorithm for Network Coding
Venue: arXiv cs.NE 2007
Year: 2007

We present a genetic algorithm which is distributed in two novel ways: along genotype and temporal axes. Our algorithm first distributes, for every member of the population, a subset of the genotype to each network node, rather than a subset of the population to each. This genotype distribution is shown to offer a significant gain in running time. Then, for efficient use of the computational resources in the network, our algorithm divides the candidate solutions into pipelined sets and thus the distribution is in the temporal domain, rather that in the spatial domain. This temporal distribution may lead to temporal inconsistency in selection and replacement, however our experiments yield better efficiency in terms of the time to convergence without incurring significant penalties.
Distance preserving mappings from ternary vectors to permutations
Venue: arXiv cs.DM 2007
Year: 2007

Distance-preserving mappings (DPMs) are mappings from the set of all q-ary vectors of a fixed length to the set of permutations of the same or longer length such that every two distinct vectors are mapped to permutations with the same or even larger Hamming distance than that of the vectors. In this paper, we propose a construction of DPMs from ternary vectors. The constructed DPMs improve the lower bounds on the maximal size of permutation arrays.
Locally Decodable Codes From Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers
Venue: arXiv cs.CC 2007
Year: 2007

A k-query Locally Decodable Code (LDC) encodes an n-bit message x as an N-bit codeword C(x), such that one can probabilistically recover any bit x_i of the message by querying only k bits of the codeword C(x), even after some constant fraction of codeword bits has been corrupted. The major goal of LDC related research is to establish the optimal trade-off between length and query complexity of such codes. Recently [Y] introduced a novel technique for constructing locally decodable codes and vastly improved the upper bounds for code length. The technique is based on Mersenne primes. In this paper we extend the work of [Y] and argue that further progress via these methods is tied to progress on an old number theory question regarding the size of the largest prime factors of Mersenne numbers. Specifically, we show that every Mersenne number m=2^t-1 that has a prime factor p>m^γyields a family of k(γ)-query locally decodable codes of length Exp(n^{1/t}). Conversely, if for some fixed k and all ε> 0 one can use the technique of [Y] to obtain a family of k-query LDCs of length Exp(n^ε); then infinitely many Mersenne numbers have prime factors arger than known currently.
Assessment and Propagation of Input Uncertainty in Tree-based Option Pricing Models
Venue: arXiv cs.CE 2007
Year: 2007

This paper aims to provide a practical example on the assessment and propagation of input uncertainty for option pricing when using tree-based methods. Input uncertainty is propagated into output uncertainty, reflecting that option prices are as unknown as the inputs they are based on. Option pricing formulas are tools whose validity is conditional not only on how close the model represents reality, but also on the quality of the inputs they use, and those inputs are usually not observable. We provide three alternative frameworks to calibrate option pricing tree models, propagating parameter uncertainty into the resulting option prices. We finally compare our methods with classical calibration-based results assuming that there is no options market established. These methods can be applied to pricing of instruments for which there is not an options market, as well as a methodological tool to account for parameter and model uncertainty in theoretical option pricing.
An Achievable Rate Region for Interference Channels with Conferencing
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, we propose an achievable rate region for discrete memoryless interference channels with conferencing at the transmitter side. We employ superposition block Markov encoding, combined with simultaneous superposition coding, dirty paper coding, and random binning to obtain the achievable rate region. We show that, under respective conditions, the proposed achievable region reduces to Han and Kobayashi achievable region for interference channels, the capacity region for degraded relay channels, and the capacity region for the Gaussian vector broadcast channel. Numerical examples for the Gaussian case are given.
Kekulé Cells for Molecular Computation
Venue: arXiv cs.OH 2007
Year: 2007

The configurations of single and double bonds in polycyclic hydrocarbons are abstracted as Kekulé states of graphs. Sending a so-called soliton over an open channel between ports (external nodes) of the graph changes the Kekulé state and therewith the set of open channels in the graph. This switching behaviour is proposed as a basis for molecular computation. The proposal is highly speculative but may have tremendous impact. Kekulé states with the same boundary behaviour (port assignment) can be regarded as equivalent. This gives rise to the abstraction of Kekulé cells. The basic theory of Kekulé states and Kekulé cells is developed here, up to the classification of Kekulé cells with $\leq 4$ ports. To put the theory in context, we generalize Kekulé states to semi-Kekulé states, which form the solutions of a linear system of equations over the field of the bits 0 and 1. We briefly study so-called omniconjugated graphs, in which every port assignment of the right signature has a Kekulé state. Omniconjugated graphs may be useful as connectors between computational elements. We finally investigate some examples with potentially useful switching behaviour.
Power control algorithms for CDMA networks based on large system analysis
Venue: arXiv cs.IT 2007
Year: 2007

Power control is a fundamental task accomplished in any wireless cellular network; its aim is to set the transmit power of any mobile terminal, so that each user is able to achieve its own target SINR. While conventional power control algorithms require knowledge of a number of parameters of the signal of interest and of the multiaccess interference, in this paper it is shown that in a large CDMA system much of this information can be dispensed with, and effective distributed power control algorithms may be implemented with very little information on the user of interest. An uplink CDMA system subject to flat fading is considered with a focus on the cases in which a linear MMSE receiver and a non-linear MMSE serial interference cancellation receiver are adopted; for the latter case new formulas are also given for the system SINR in the large system asymptote. Experimental results show an excellent agreement between the performance and the power profile of the proposed distributed algorithms and that of conventional ones that require much greater prior knowledge.
Computing Extensions of Linear Codes
Venue: arXiv cs.IT 2007
Year: 2007

This paper deals with the problem of increasing the minimum distance of a linear code by adding one or more columns to the generator matrix. Several methods to compute extensions of linear codes are presented. Many codes improving the previously known lower bounds on the minimum distance have been found.
Opportunistic Communications in an Orthogonal Multiaccess Relay Channel
Venue: arXiv cs.IT 2007
Year: 2007

The problem of resource allocation is studied for a two-user fading orthogonal multiaccess relay channel (MARC) where both users (sources) communicate with a destination in the presence of a relay. A half-duplex relay is considered that transmits on a channel orthogonal to that used by the sources. The instantaneous fading state between every transmit-receive pair in this network is assumed to be known at both the transmitter and receiver. Under an average power constraint at each source and the relay, the sum-rate for the achievable strategy of decode-and-forward (DF) is maximized over all power allocations (policies) at the sources and relay. It is shown that the sum-rate maximizing policy exploits the multiuser fading diversity to reveal the optimality of opportunistic channel use by each user. A geometric interpretation of the optimal power policy is also presented.
The Complexity of Simple Stochastic Games
Venue: arXiv cs.CC 2007
Year: 2007

In this paper we survey the computational time complexity of assorted simple stochastic game problems, and we give an overview of the best known algorithms associated with each problem.
Writing on Dirty Paper with Resizing and its Application to Quasi-Static Fading Broadcast Channels
Venue: arXiv cs.IT 2007
Year: 2007

This paper studies a variant of the classical problem of ``writing on dirty paper'' in which the sum of the input and the interference, or dirt, is multiplied by a random variable that models resizing, known to the decoder but not to the encoder. The achievable rate of Costa's dirty paper coding (DPC) scheme is calculated and compared to the case of the decoder's also knowing the dirt. In the ergodic case, the corresponding rate loss vanishes asymptotically in the limits of both high and low signal-to-noise ratio (SNR), and is small at all finite SNR for typical distributions like Rayleigh, Rician, and Nakagami. In the quasi-static case, the DPC scheme is lossless at all SNR in terms of outage probability. Quasi-static fading broadcast channels (BC) without transmit channel state information (CSI) are investigated as an application of the robustness properties. It is shown that the DPC scheme leads to an outage achievable rate region that strictly dominates that of time division.