OpenRaiser/Intern-Atlas huggingface dataset:
Local search heuristics: Fitness Cloud versus Fitness Landscape
Venue: arXiv cs.AI 2007
Year: 2007

This paper introduces the concept of fitness cloud as an alternative way to visualize and analyze search spaces than given by the geographic notion of fitness landscape. It is argued that the fitness cloud concept overcomes several deficiencies of the landscape representation. Our analysis is based on the correlation between fitness of solutions and fitnesses of nearest solutions according to some neighboring. We focus on the behavior of local search heuristics, such as hill climber, on the well-known NK fitness landscape. In both cases the fitness vs. fitness correlation is shown to be related to the epistatic parameter K.
Measuring the Evolvability Landscape to study Neutrality
Venue: arXiv cs.AI 2007
Year: 2007

This theoretical work defines the measure of autocorrelation of evolvability in the context of neutral fitness landscape. This measure has been studied on the classical MAX-SAT problem. This work highlight a new characteristic of neutral fitness landscapes which allows to design new adapted metaheuristic.
Serially Concatenated IRA Codes
Venue: arXiv cs.IT 2007
Year: 2007

We address the error floor problem of low-density parity check (LDPC) codes on the binary-input additive white Gaussian noise (AWGN) channel, by constructing a serially concatenated code consisting of two systematic irregular repeat accumulate (IRA) component codes connected by an interleaver. The interleaver is designed to prevent stopping-set error events in one of the IRA codes from propagating into stopping set events of the other code. Simulations with two 128-bit rate 0.707 IRA component codes show that the proposed architecture achieves a much lower error floor at higher SNRs, compared to a 16384-bit rate 1/2 IRA code, but incurs an SNR penalty of about 2 dB at low to medium SNRs. Experiments indicate that the SNR penalty can be reduced at larger blocklengths.
The complexity of nonrepetitive edge coloring of graphs
Venue: arXiv cs.CC 2007
Year: 2007

A squarefree word is a sequence $w$ of symbols such that there are no strings $x, y$, and $z$ for which $w=xyyz$. A nonrepetitive coloring of a graph is an edge coloring in which the sequence of colors along any open path is squarefree. We show that determining whether a graph $G$ has a nonrepetitive $k$-coloring is $Σ_2^p$-complete. When we restrict to paths of lengths at most $n$, the problem becomes NP-complete for fixed $n$.
Practical Multiwriter Lock-Free Queues for "Hard Real-Time" Systems without CAS
Venue: arXiv cs.OS 2007
Year: 2007

FIFO queues with a single reader and writer can be insufficient for "hard real-time" systems where interrupt handlers require wait-free guarantees when writing to message queues. We present an algorithm which elegantly and practically solves this problem on small processors that are often found in embedded systems. The algorithm does not require special CPU instructions (such as atomic CAS), and therefore is more robust than many existing methods that suffer the ABA problem associated with swing pointers. The algorithm gives "first-in, almost first-out" guarantees under pathological interrupt conditions, which manifests as arbitrary "shoving" among nearly-simultaneous arrivals at the end of the queue.
Sorting and Selection with Random Costs
Venue: arXiv cs.DS 2007
Year: 2007

There is a growing body of work on sorting and selection in models other than the unit-cost comparison model. This work is the first treatment of a natural stochastic variant of the problem where the cost of comparing two elements is a random variable. Each cost is chosen independently and is known to the algorithm. In particular we consider the following three models: each cost is chosen uniformly in the range $[0,1]$, each cost is 0 with some probability $p$ and 1 otherwise, or each cost is 1 with probability $p$ and infinite otherwise. We present lower and upper bounds (optimal in most cases) for these problems. We obtain our upper bounds by carefully designing algorithms to ensure that the costs incurred at various stages are independent and using properties of random partial orders when appropriate.
Zipf's Law and Avoidance of Excessive Synonymy
Venue: arXiv cs.CL 2007
Year: 2007

Zipf's law states that if words of language are ranked in the order of decreasing frequency in texts, the frequency of a word is inversely proportional to its rank. It is very robust as an experimental observation, but to date it escaped satisfactory theoretical explanation. We suggest that Zipf's law may arise from the evolution of word semantics dominated by expansion of meanings and competition of synonyms.
The Theory of Unified Relativity for a Biovielectroluminescence Phenomenon via Fly's Visual and Imaging System
Venue: arXiv cs.CE 2007
Year: 2007

The elucidation upon fly's neuronal patterns as a link to computer graphics and memory cards I/O's, is investigated for the phenomenon by propounding a unified theory of Einstein's two known relativities. It is conclusive that flies could contribute a certain amount of neuromatrices indicating an imagery function of a visual-computational system into computer graphics and storage systems. The visual system involves the time aspect, whereas flies possess faster pulses compared to humans' visual ability due to the E-field state on an active fly's eye surface. This behaviour can be tested on a dissected fly specimen at its ommatidia. Electro-optical contacts and electrodes are wired through the flesh forming organic emitter layer to stimulate light emission, thereby to a computer circuit. The next step is applying a threshold voltage with secondary voltages to the circuit denoting an array of essential electrodes for bit switch. As a result, circuit's dormant pulses versus active pulses at the specimen's area are recorded. The outcome matrix possesses a construction of RGB and time radicals expressing the time problem in consumption, allocating time into computational algorithms, enhancing the technology far beyond. The obtained formulation generates consumed distance cons(x), denoting circuital travel between data source/sink for pixel data and bendable wavelengths. Once 'image logic' is in place, incorporating this point of graphical acceleration permits one to enhance graphics and optimize immensely central processing, data transmissions between memory and computer visual system. The phenomenon can be mainly used in 360-deg. display/viewing, 3D scanning techniques, military and medicine, a robust and cheap substitution for e.g. pre-motion pattern analysis, real-time rendering and LCDs.
Optimization of supply diversity for the self-assembly of simple objects in two and three dimensions
Venue: arXiv cs.NE 2007
Year: 2007

The field of algorithmic self-assembly is concerned with the design and analysis of self-assembly systems from a computational perspective, that is, from the perspective of mathematical problems whose study may give insight into the natural processes through which elementary objects self-assemble into more complex ones. One of the main problems of algorithmic self-assembly is the minimum tile set problem (MTSP), which asks for a collection of types of elementary objects (called tiles) to be found for the self-assembly of an object having a pre-established shape. Such a collection is to be as concise as possible, thus minimizing supply diversity, while satisfying a set of stringent constraints having to do with the termination and other properties of the self-assembly process from its tile types. We present a study of what we think is the first practical approach to MTSP. Our study starts with the introduction of an evolutionary heuristic to tackle MTSP and includes results from extensive experimentation with the heuristic on the self-assembly of simple objects in two and three dimensions. The heuristic we introduce combines classic elements from the field of evolutionary computation with a problem-specific variant of Pareto dominance into a multi-objective approach to MTSP.
Wireless Local Area Networks with Multiple-Packet Reception Capability
Venue: arXiv cs.PF 2007
Year: 2007

Thanks to its simplicity and cost efficiency, wireless local area network (WLAN) enjoys unique advantages in providing high-speed and low-cost wireless services in hot spots and indoor environments. Traditional WLAN medium-access-control (MAC) protocols assume that only one station can transmit at a time: simultaneous transmissions of more than one station causes the destruction of all packets involved. By exploiting recent advances in PHY-layer multiuser detection (MUD) techniques, it is possible for a receiver to receive multiple packets simultaneously. This paper argues that such multipacket reception (MPR) capability can greatly enhance the capacity of future WLANs. In addition, it provides the MAC-layer and PHY-layer designs needed to achieve the improved capacity. First, to demonstrate MUD/MPR as a powerful capacity-enhancement technique, we prove a "super-linearity" result, which states that the system throughput per unit cost increases as the MPR capability increases. Second, we show that the commonly deployed binary exponential backoff (BEB) algorithm in today's WLAN MAC may not be optimal in an MPR system, and that the optimal backoff factor increases with the MPR capability: the number of packets that can be received simultaneously. Third, based on the above insights, we design a joint MAC-PHY layer protocol for an IEEE 802.11-like WLAN that incorporates advanced PHY-layer blind detection and MUD techniques to implement MPR
Secrecy Capacity of the Wiretap Channel with Noisy Feedback
Venue: arXiv cs.IT 2007
Year: 2007

In this work, the role of noisy feedback in enhancing the secrecy capacity of the wiretap channel is investigated. A model is considered in which the feed-forward and feedback signals share the same noisy channel. More specifically, a discrete memoryless modulo-additive channel with a full-duplex destination node is considered first, and it is shown that a judicious use of feedback increases the perfect secrecy capacity to the capacity of the source-destination channel in the absence of the wiretapper. In the achievability scheme, the feedback signal corresponds to a private key, known only to the destination. Then a half-duplex system is considered, for which a novel feedback technique that always achieves a positive perfect secrecy rate (even when the source-wiretapper channel is less noisy than the source-destination channel) is proposed. These results hinge on the modulo-additive property of the channel, which is exploited by the destination to perform encryption over the channel without revealing its key to the source.
On the Relationship between Mutual Information and Minimum Mean-Square Errors in Stochastic Dynamical Systems
Venue: arXiv cs.IT 2007
Year: 2007

We consider a general stochastic input-output dynamical system with output evolving in time as the solution to a functional coefficients, Itô's stochastic differential equation, excited by an input process. This general class of stochastic systems encompasses not only the classical communication channel models, but also a wide variety of engineering systems appearing through a whole range of applications. For this general setting we find analogous of known relationships linking input-output mutual information and minimum mean causal and non-causal square errors, previously established in the context of additive Gaussian noise communication channels. Relationships are not only established in terms of time-averaged quantities, but also their time-instantaneous, dynamical counterparts are presented. The problem of appropriately introducing in this general framework a signal-to-noise ratio notion expressed through a signal-to-noise ratio parameter is also taken into account, identifying conditions for a proper and meaningful interpretation.
Multi-User Diversity vs. Accurate Channel Feedback for MIMO Broadcast Channels
Venue: arXiv cs.IT 2007
Year: 2007

A multiple transmit antenna, single receive antenna (per receiver) downlink channel with limited channel feedback is considered. Given a constraint on the total system-wide channel feedback, the following question is considered: is it preferable to get low-rate feedback from a large number of receivers or to receive high-rate/high-quality feedback from a smaller number of (randomly selected) receivers? Acquiring feedback from many users allows multi-user diversity to be exploited, while high-rate feedback allows for very precise selection of beamforming directions. It is shown that systems in which a limited number of users feedback high-rate channel information significantly outperform low-rate/many user systems. While capacity increases only double logarithmically with the number of users, the marginal benefit of channel feedback is very significant up to the point where the CSI is essentially perfect.
Polish grid infrastructure for science and research
Venue: arXiv cs.DC 2007
Year: 2007

Structure, functionality, parameters and organization of the computing Grid in Poland is described, mainly from the perspective of high-energy particle physics community, currently its largest consumer and developer. It represents distributed Tier-2 in the worldwide Grid infrastructure. It also provides services and resources for data-intensive applications in other sciences.
Weight Distributions of Hamming Codes
Venue: arXiv cs.IT 2007
Year: 2007

We derive a recursive formula determing the weight distribution of the [n=(q^m-1)/(q-1), n-m, 3] Hamming code H(m,q), when (m, q-1)=1. Here q is a prime power. The proof is based on Moisio's idea of using Pless power moment identity together with exponential sum techniques.
Heap Reference Analysis for Functional Programs
Venue: arXiv cs.PL 2007
Year: 2007

Current garbage collectors leave a lot of garbage uncollected because they conservatively approximate liveness by reachability from program variables. In this paper, we describe a sequence of static analyses that takes as input a program written in a first-order, eager functional programming language, and finds at each program point the references to objects that are guaranteed not to be used in the future. Such references are made null by a transformation pass. If this makes the object unreachable, it can be collected by the garbage collector. This causes more garbage to be collected, resulting in fewer collections. Additionally, for those garbage collectors which scavenge live objects, it makes each collection faster. The interesting aspects of our method are both in the identification of the analyses required to solve the problem and the way they are carried out. We identify three different analyses -- liveness, sharing and accessibility. In liveness and sharing analyses, the function definitions are analyzed independently of the calling context. This is achieved by using a variable to represent the unknown context of the function being analyzed and setting up constraints expressing the effect of the function with respect to the variable. The solution of the constraints is a summary of the function that is parameterized with respect to a calling context and is used to analyze function calls. As a result we achieve context sensitivity at call sites without analyzing the function multiple number of times.
Analysis of Fixed Outage Transmission Schemes: A Finer Look at the Full Multiplexing Point
Venue: arXiv cs.IT 2007
Year: 2007

This paper studies the performance of transmission schemes that have rate that increases with average SNR while maintaining a fixed outage probability. This is in contrast to the classical Zheng-Tse diversity-multiplexing tradeoff (DMT) that focuses on increasing rate and decreasing outage probability. Three different systems are explored: antenna diversity systems, time/frequency diversity systems, and automatic repeat request (ARQ) systems. In order to accurately study performance in the fixed outage setting, it is necesary to go beyond the coarse, asymptotic multiplexing gain metric. In the case of antenna diversity and time/frequency diversity, an affine approximation to high SNR outage capacity (i.e., multiplexing gain plus a power/rate offset) accurately describes performance and shows the very significant benefits of diversity. ARQ is also seen to provide a significant performance advantage, but even an affine approximation to outage capacity is unable to capture this advantage and outage capacity must be directly studied in the non-asymptotic regime.
Stanford Matrix Considered Harmful
Venue: arXiv cs.IR 2007
Year: 2007

This note argues about the validity of web-graph data used in the literature.
Success and failure of programming environments - report on the design and use of a graphic abstract syntax tree editor
Venue: arXiv cs.PL 2007
Year: 2007

The STAPLE project investigated (at the end of the eighties), a persistent architecture for functional programming. Work has been done in two directions: the development of a programming environment for a functional language within a persistent system and an experiment on transferring the expertise of functional prototyping into industry. This paper is a report on the first activity. The first section gives a general description of Absynte - the abstract syntax tree editor developed within the Project. Following sections make an attempt at measuring the effectiveness of such an editor and discuss the problems raised by structured syntax editing - specially environments based on abstract syntax trees.
The structure of verbal sequences analyzed with unsupervised learning techniques
Venue: arXiv cs.CL 2007
Year: 2007

Data mining allows the exploration of sequences of phenomena, whereas one usually tends to focus on isolated phenomena or on the relation between two phenomena. It offers invaluable tools for theoretical analyses and exploration of the structure of sentences, texts, dialogues, and speech. We report here the results of an attempt at using it for inspecting sequences of verbs from French accounts of road accidents. This analysis comes from an original approach of unsupervised training allowing the discovery of the structure of sequential data. The entries of the analyzer were only made of the verbs appearing in the sentences. It provided a classification of the links between two successive verbs into four distinct clusters, allowing thus text segmentation. We give here an interpretation of these clusters by applying a statistical analysis to independent semantic annotations.
Probabilistic communication complexity over the reals
Venue: arXiv cs.CC 2007
Year: 2007

Deterministic and probabilistic communication protocols are introduced in which parties can exchange the values of polynomials (rather than bits in the usual setting). It is established a sharp lower bound $2n$ on the communication complexity of recognizing the $2n$-dimensional orthant, on the other hand the probabilistic communication complexity of its recognizing does not exceed 4. A polyhedron and a union of hyperplanes are constructed in $\RR^{2n}$ for which a lower bound $n/2$ on the probabilistic communication complexity of recognizing each is proved. As a consequence this bound holds also for the EMPTINESS and the KNAPSACK problems.
An efficient reduction of ranking to classification
Venue: arXiv cs.LG 2007
Year: 2007

This paper describes an efficient reduction of the learning problem of ranking to binary classification. The reduction guarantees an average pairwise misranking regret of at most that of the binary classifier regret, improving a recent result of Balcan et al which only guarantees a factor of 2. Moreover, our reduction applies to a broader class of ranking loss functions, admits a simpler proof, and the expected running time complexity of our algorithm in terms of number of calls to a classifier or preference function is improved from $Ω(n^2)$ to $O(n \log n)$. In addition, when the top $k$ ranked elements only are required ($k \ll n$), as in many applications in information extraction or search engines, the time complexity of our algorithm can be further reduced to $O(k \log k + n)$. Our reduction and algorithm are thus practical for realistic applications where the number of points to rank exceeds several thousands. Much of our results also extend beyond the bipartite case previously studied. Our rediction is a randomized one. To complement our result, we also derive lower bounds on any deterministic reduction from binary (preference) classification to ranking, implying that our use of a randomized reduction is essentially necessary for the guarantees we provide.
A generic attack to ciphers
Venue: arXiv cs.CR 2007
Year: 2007

In this paper, we present a generic attack for ciphers, which is in essence a collision attack on the secret keys of ciphers .
Modeling Context, Collaboration, and Civilization in End-User Informatics
Venue: arXiv cs.OH 2007
Year: 2007

End-user informatics applications are Internet data web management automation solutions. These are mass modeling and mass management collaborative communal consensus solutions. They are made and maintained by managerial, professional, technical and specialist end-users. In end-user informatics the end-users are always right. So it becomes necessary for information technology professionals to understand information and informatics from the end-user perspective. End-user informatics starts with the observation that practical prose is a mass consensus communal modeling technology. This high technology is the mechanistic modeling medium we all use every day in all of our practical pursuits. Practical information flows are the lifeblood of modern capitalist communities. But what exactly is practical information? It's ultimately physical information, but the physics is highly emergent rather than elementary. So practical reality is just physical reality in deep disguise. Practical prose is the medium that we all use to model the everyday and elite mechanics of practical reality. So this is the medium that end-user informatics must automate and animate.
Fuzzy Modeling of Electrical Impedance Tomography Image of the Lungs
Venue: arXiv cs.AI 2007
Year: 2007

Electrical Impedance Tomography (EIT) is a functional imaging method that is being developed for bedside use in critical care medicine. Aiming at improving the chest anatomical resolution of EIT images we developed a fuzzy model based on EIT high temporal resolution and the functional information contained in the pulmonary perfusion and ventilation signals. EIT data from an experimental animal model were collected during normal ventilation and apnea while an injection of hypertonic saline was used as a reference . The fuzzy model was elaborated in three parts: a modeling of the heart, a pulmonary map from ventilation images and, a pulmonary map from perfusion images. Image segmentation was performed using a threshold method and a ventilation/perfusion map was generated. EIT images treated by the fuzzy model were compared with the hypertonic saline injection method and CT-scan images, presenting good results in both qualitative (the image obtained by the model was very similar to that of the CT-scan) and quantitative (the ROC curve provided an area equal to 0.93) point of view. Undoubtedly, these results represent an important step in the EIT images area, since they open the possibility of developing EIT-based bedside clinical methods, which are not available nowadays. These achievements could serve as the base to develop EIT diagnosis system for some life-threatening diseases commonly found in critical care medicine.