OpenRaiser/Intern-Atlas huggingface dataset:
The Linear Arrangement Problem Parameterized Above Guaranteed Value
Venue: arXiv cs.DS 2006
Year: 2006

A linear arrangement (LA) is an assignment of distinct integers to the vertices of a graph. The cost of an LA is the sum of lengths of the edges of the graph, where the length of an edge is defined as the absolute value of the difference of the integers assigned to its ends. For many application one hopes to find an LA with small cost. However, it is a classical NP-complete problem to decide whether a given graph $G$ admits an LA of cost bounded by a given integer. Since every edge of $G$ contributes at least one to the cost of any LA, the problem becomes trivially fixed-parameter tractable (FPT) if parameterized by the upper bound of the cost. Fernau asked whether the problem remains FPT if parameterized by the upper bound of the cost minus the number of edges of the given graph; thus whether the problem is FPT ``parameterized above guaranteed value.'' We answer this question positively by deriving an algorithm which decides in time $O(m+n+5.88^k)$ whether a given graph with $m$ edges and $n$ vertices admits an LA of cost at most $m+k$ (the algorithm computes such an LA if it exists). Our algorithm is based on a procedure which generates a problem kernel of linear size in linear time for a connected graph $G$. We also prove that more general parameterized LA problems stated by Serna and Thilikos are not FPT, unless P=NP.
On-line regression competitive with reproducing kernel Hilbert spaces
Venue: arXiv cs.LG 2006
Year: 2006

We consider the problem of on-line prediction of real-valued labels, assumed bounded in absolute value by a known constant, of new objects from known labeled objects. The prediction algorithm's performance is measured by the squared deviation of the predictions from the actual labels. No stochastic assumptions are made about the way the labels and objects are generated. Instead, we are given a benchmark class of prediction rules some of which are hoped to produce good predictions. We show that for a wide range of infinite-dimensional benchmark classes one can construct a prediction algorithm whose cumulative loss over the first N examples does not exceed the cumulative loss of any prediction rule in the class plus O(sqrt(N)); the main differences from the known results are that we do not impose any upper bound on the norm of the considered prediction rules and that we achieve an optimal leading term in the excess loss of our algorithm. If the benchmark class is "universal" (dense in the class of continuous functions on each compact set), this provides an on-line non-stochastic analogue of universally consistent prediction in non-parametric statistics. We use two proof techniques: one is based on the Aggregating Algorithm and the other on the recently developed method of defensive forecasting.
Every Sequence is Decompressible from a Random One
Venue: arXiv cs.IT 2006
Year: 2006

Kucera and Gacs independently showed that every infinite sequence is Turing reducible to a Martin-Lof random sequence. This result is extended by showing that every infinite sequence S is Turing reducible to a Martin-Lof random sequence R such that the asymptotic number of bits of R needed to compute n bits of S, divided by n, is precisely the constructive dimension of S. It is shown that this is the optimal ratio of query bits to computed bits achievable with Turing reductions. As an application of this result, a new characterization of constructive dimension is given in terms of Turing reduction compression ratios.
Incremental and Transitive Discrete Rotations
Venue: arXiv cs.DM 2006
Year: 2006

A discrete rotation algorithm can be apprehended as a parametric application $f\_α$ from $\ZZ[i]$ to $\ZZ[i]$, whose resulting permutation ``looks like'' the map induced by an Euclidean rotation. For this kind of algorithm, to be incremental means to compute successively all the intermediate rotate d copies of an image for angles in-between 0 and a destination angle. The di scretized rotation consists in the composition of an Euclidean rotation with a discretization; the aim of this article is to describe an algorithm whic h computes incrementally a discretized rotation. The suggested method uses o nly integer arithmetic and does not compute any sine nor any cosine. More pr ecisely, its design relies on the analysis of the discretized rotation as a step function: the precise description of the discontinuities turns to be th e key ingredient that will make the resulting procedure optimally fast and e xact. A complete description of the incremental rotation process is provided, also this result may be useful in the specification of a consistent set of defin itions for discrete geometry.
On the Complexity of finding Stopping Distance in Tanner Graphs
Venue: arXiv cs.IT 2006
Year: 2006

Two decision problems related to the computation of stopping sets in Tanner graphs are shown to be NP-complete. NP-hardness of the problem of computing the stopping distance of a Tanner graph follows as a consequence
Forward slicing of functional logic programs by partial evaluation
Venue: arXiv cs.PL 2006
Year: 2006

Program slicing has been mainly studied in the context of imperative languages, where it has been applied to a wide variety of software engineering tasks, like program understanding, maintenance, debugging, testing, code reuse, etc. This work introduces the first forward slicing technique for declarative multi-paradigm programs which integrate features from functional and logic programming. Basically, given a program and a slicing criterion (a function call in our setting), the computed forward slice contains those parts of the original program which are reachable from the slicing criterion. Our approach to program slicing is based on an extension of (online) partial evaluation. Therefore, it provides a simple way to develop program slicing tools from existing partial evaluators and helps to clarify the relation between both methodologies. A slicing tool for the multi-paradigm language Curry, which demonstrates the usefulness of our approach, has been implemented in Curry itself.
Weighted Norms of Ambiguity Functions and Wigner Distributions
Venue: arXiv cs.IT 2006
Year: 2006

In this article new bounds on weighted p-norms of ambiguity functions and Wigner functions are derived. Such norms occur frequently in several areas of physics and engineering. In pulse optimization for Weyl--Heisenberg signaling in wide-sense stationary uncorrelated scattering channels for example it is a key step to find the optimal waveforms for a given scattering statistics which is a problem also well known in radar and sonar waveform optimizations. The same situation arises in quantum information processing and optical communication when optimizing pure quantum states for communicating in bosonic quantum channels, i.e. find optimal channel input states maximizing the pure state channel fidelity. Due to the non-convex nature of this problem the optimum and the maximizers itself are in general difficult find, numerically and analytically. Therefore upper bounds on the achievable performance are important which will be provided by this contribution. Based on a result due to E. Lieb, the main theorem states a new upper bound which is independent of the waveforms and becomes tight only for Gaussian weights and waveforms. A discussion of this particular important case, which tighten recent results on Gaussian quantum fidelity and coherent states, will be given. Another bound is presented for the case where scattering is determined only by some arbitrary region in phase space.
On the Fading Number of Multiple-Input Single-Output Fading Channels with Memory
Venue: arXiv cs.IT 2006
Year: 2006

We derive new upper and lower bounds on the fading number of multiple-input single-output (MISO) fading channels of general (not necessarily Gaussian) regular law with spatial and temporal memory. The fading number is the second term, after the double-logarithmic term, of the high signal-to-noise ratio (SNR) expansion of channel capacity. In case of an isotropically distributed fading vector it is proven that the upper and lower bound coincide, i.e., the general MISO fading number with memory is known precisely. The upper and lower bounds show that a type of beam-forming is asymptotically optimal.
Efficient Convergent Maximum Likelihood Decoding on Tail-Biting Trellises
Venue: arXiv cs.IT 2006
Year: 2006

An algorithm for exact maximum likelihood(ML) decoding on tail-biting trellises is presented, which exhibits very good average case behavior. An approximate variant is proposed, whose simulated performance is observed to be virtually indistinguishable from the exact one at all values of signal to noise ratio, and which effectively performs computations equivalent to at most two rounds on the tail-biting trellis. The approximate algorithm is analyzed, and the conditions under which its output is different from the ML output are deduced. The results of simulations on an AWGN channel for the exact and approximate algorithms on the 16 state tail-biting trellis for the (24,12) Extended Golay Code, and tail-biting trellises for two rate 1/2 convolutional codes with memories of 4 and 6 respectively, are reported. An advantage of our algorithms is that they do not suffer from the effects of limit cycles or the presence of pseudocodewords.
PageRank without hyperlinks: Structural re-ranking using links induced by language models
Venue: arXiv cs.IR 2006
Year: 2006

Inspired by the PageRank and HITS (hubs and authorities) algorithms for Web search, we propose a structural re-ranking approach to ad hoc information retrieval: we reorder the documents in an initially retrieved set by exploiting asymmetric relationships between them. Specifically, we consider generation links, which indicate that the language model induced from one document assigns high probability to the text of another; in doing so, we take care to prevent bias against long documents. We study a number of re-ranking criteria based on measures of centrality in the graphs formed by generation links, and show that integrating centrality into standard language-model-based retrieval is quite effective at improving precision at top ranks.
Automatic Detection of Trends in Dynamical Text: An Evolutionary Approach
Venue: arXiv cs.IR 2006
Year: 2006

This paper presents an evolutionary algorithm for modeling the arrival dates of document streams, which is any time-stamped collection of documents, such as newscasts, e-mails, IRC conversations, scientific journals archives and weblog postings. This algorithm assigns frequencies (number of document arrivals per time unit) to time intervals so that it produces an optimal fit to the data. The optimization is a trade off between accurately fitting the data and avoiding too many frequency changes; this way the analysis is able to find fits which ignore the noise. Classical dynamic programming algorithms are limited by memory and efficiency requirements, which can be a problem when dealing with long streams. This suggests to explore alternative search methods which allow for some degree of uncertainty to achieve tractability. Experiments have shown that the designed evolutionary algorithm is able to reach the same solution quality as those classical dynamic programming algorithms in a shorter time. We have also explored different probabilistic models to optimize the fitting of the date streams, and applied these algorithms to infer whether a new arrival increases or decreases {\em interest} in the topic the document stream is about.
Learning by Test-infecting Symmetric Ciphers
Venue: arXiv cs.CR 2006
Year: 2006

We describe a novel way in which students can learn the cipher systems without much supervision. In this work we focus on learning symmetric ciphers by altering them using the agile development approach. Two agile approaches the eXtreme Programming (XP) and the closely related Test-Driven Development (TDD) are mentioned or discussed. To facilitate this development we experiment with an approach that is based on refactoring, with JUnit serves as the automatic testing framework. In this work we exemplify our learning approach by test-infecting the Vernam cipher, an aged but still widely used stream cipher. One can replace the cipher with another symmetric cipher with the same behavior. Software testing is briefly described. Just-in-time introduction to Object-oriented programming (OOP), exemplified by using JavaTM, is advocated. Refactoring exercises, as argued, are kept strategically simple so that they do not become intensive class redesign exercises. The use of free or open-source tools and frameworks is mentioned.
SCRUB-PA: A Multi-Level Multi-Dimensional Anonymization Tool for Process Accounting
Venue: arXiv cs.CR 2006
Year: 2006

In the UNIX/Linux environment the kernel can log every command process created by every user using process accounting. This data has many potential uses, including the investigation of security incidents. However, process accounting data is also sensitive since it contains private user information. Consequently, security system administrators have been hindered from sharing these logs. Given that many interesting security applications could use process accounting data, it would be useful to have a tool that could protect private user information in the logs. For this reason we introduce SCRUB-PA, a tool that uses multi-level multi-dimensional anonymization on process accounting log files in order to provide different levels of privacy protection. It is our goal that SCRUB-PA will promote the sharing of process accounting logs while preserving privacy.
Randomized Fast Design of Short DNA Words
Venue: arXiv cs.DS 2006
Year: 2006

We consider the problem of efficiently designing sets (codes) of equal-length DNA strings (words) that satisfy certain combinatorial constraints. This problem has numerous motivations including DNA computing and DNA self-assembly. Previous work has extended results from coding theory to obtain bounds on code size for new biologically motivated constraints and has applied heuristic local search and genetic algorithm techniques for code design. This paper proposes a natural optimization formulation of the DNA code design problem in which the goal is to design n strings that satisfy a given set of constraints while minimizing the length of the strings. For multiple sets of constraints, we provide high-probability algorithms that run in time polynomial in n and any given constraint parameters, and output strings of length within a constant factor of the optimal. To the best of our knowledge, this work is the first to consider this type of optimization problem in the context of DNA code design.
Processing of Test Matrices with Guessing Correction
Venue: arXiv cs.LG 2006
Year: 2006

It is suggested to insert into test matrix 1s for correct responses, 0s for response refusals, and negative corrective elements for incorrect responses. With the classical test theory approach test scores of examinees and items are calculated traditionally as sums of matrix elements, organized in rows and columns. Correlation coefficients are estimated using correction coefficients. In item response theory approach examinee and item logits are estimated using maximum likelihood method and probabilities of all matrix elements.
Improved Nearly-MDS Expander Codes
Venue: arXiv cs.IT 2006
Year: 2006

A construction of expander codes is presented with the following three properties: (i) the codes lie close to the Singleton bound, (ii) they can be encoded in time complexity that is linear in their code length, and (iii) they have a linear-time bounded-distance decoder. By using a version of the decoder that corrects also erasures, the codes can replace MDS outer codes in concatenated constructions, thus resulting in linear-time encodable and decodable codes that approach the Zyablov bound or the capacity of memoryless channels. The presented construction improves on an earlier result by Guruswami and Indyk in that any rate and relative minimum distance that lies below the Singleton bound is attainable for a significantly smaller alphabet size.
On timed automata with input-determined guards
Venue: arXiv cs.LO 2006
Year: 2006

We consider a general notion of timed automata with input-determined guards and show that they admit a robust logical framework along the lines of [D 'Souza03], in terms of a monadic second order logic characterisation and an expressively complete timed temporal logic. We then generalize these automata using the notion of recursive operators introduced by Henzinger, Raskin, and Schobbens, and show that they admit a similar logical framework. These results hold in the ``pointwise'' semantics. We finally use this framework to show that the real-time logic MITL of Alur et al is expressively complete with respect to an MSO corresponding to an appropriate input-determined operator.
Adaptive Linear Programming Decoding
Venue: arXiv cs.IT 2006
Year: 2006

Detectability of failures of linear programming (LP) decoding and its potential for improvement by adding new constraints motivate the use of an adaptive approach in selecting the constraints for the LP problem. In this paper, we make a first step in studying this method, and show that it can significantly reduce the complexity of the problem, which was originally exponential in the maximum check-node degree. We further show that adaptively adding new constraints, e.g. by combining parity checks, can provide large gains in the performance.
The `Face on Mars': a photographic approach for the search of signs of past civilizations from a macroscopic point of view, factoring long-term erosion in image reconstruction
Venue: arXiv cs.CV 2006
Year: 2006

This short article presents an alternative view of high resolution imaging from various sources with the aim of the discovery of potential sites of archaeological importance, or sites that exhibit `anomalies' such that they may merit closer inspection and analysis. It is conjectured, and to a certain extent demonstrated here, that it is possible for advanced civilizations to factor in erosion by natural processes into a large scale design so that main features be preserved even with the passage of millions of years. Alternatively viewed, even without such intent embedded in a design left for posterity, it is possible that a gigantic construction may naturally decay in such a way that even cataclysmic (massive) events may leave sufficient information intact with the passage of time, provided one changes the point of view from high resolution images to enhanced blurred renderings of the sites in question.
Structure of Optimal Input Covariance Matrices for MIMO Systems with Covariance Feedback under General Correlated Fading
Venue: arXiv cs.IT 2006
Year: 2006

We describe the structure of optimal Input covariance matrices for single user multiple-input/multiple-output (MIMO) communication system with covariance feedback and for general correlated fading. Our approach is based on the novel concept of right commutant and recovers previously derived results for the Kronecker product models. Conditions are derived which allow a significant simplification of the optimization problem.
Certainty Closure: Reliable Constraint Reasoning with Incomplete or Erroneous Data
Venue: arXiv cs.AI 2006
Year: 2006

Constraint Programming (CP) has proved an effective paradigm to model and solve difficult combinatorial satisfaction and optimisation problems from disparate domains. Many such problems arising from the commercial world are permeated by data uncertainty. Existing CP approaches that accommodate uncertainty are less suited to uncertainty arising due to incomplete and erroneous data, because they do not build reliable models and solutions guaranteed to address the user's genuine problem as she perceives it. Other fields such as reliable computation offer combinations of models and associated methods to handle these types of uncertain data, but lack an expressive framework characterising the resolution methodology independently of the model. We present a unifying framework that extends the CP formalism in both model and solutions, to tackle ill-defined combinatorial problems with incomplete or erroneous data. The certainty closure framework brings together modelling and solving methodologies from different fields into the CP paradigm to provide reliable and efficient approches for uncertain constraint problems. We demonstrate the applicability of the framework on a case study in network diagnosis. We define resolution forms that give generic templates, and their associated operational semantics, to derive practical solution methods for reliable solutions.
Localization in Wireless Sensor Grids
Venue: arXiv cs.DC 2006
Year: 2006

This work reports experiences on using radio ranging to position sensors in a grid topology. The implementation is simple, efficient, and could be practically distributed. The paper describes an implementation and experimental result based on RSSI distance estimation. Novel techniques such as fuzzy membership functions and table lookup are used to obtain more accurate result and simplify the computation. An 86% accuracy is achieved in the experiment in spite of inaccurate RSSI distance estimates with errors up to 60%.
Reducibility of Gene Patterns in Ciliates using the Breakpoint Graph
Venue: arXiv cs.LO 2006
Year: 2006

Gene assembly in ciliates is one of the most involved DNA processings going on in any organism. This process transforms one nucleus (the micronucleus) into another functionally different nucleus (the macronucleus). We continue the development of the theoretical models of gene assembly, and in particular we demonstrate the use of the concept of the breakpoint graph, known from another branch of DNA transformation research. More specifically: (1) we characterize the intermediate gene patterns that can occur during the transformation of a given micronuclear gene pattern to its macronuclear form; (2) we determine the number of applications of the loop recombination operation (the most basic of the three molecular operations that accomplish gene assembly) needed in this transformation; (3) we generalize previous results (and give elegant alternatives for some proofs) concerning characterizations of the micronuclear gene patterns that can be assembled using a specific subset of the three molecular operations.
Approximate Linear Time ML Decoding on Tail-Biting Trellises in Two Rounds
Venue: arXiv cs.IT 2006
Year: 2006

A linear time approximate maximum likelihood decoding algorithm on tail-biting trellises is prsented, that requires exactly two rounds on the trellis. This is an adaptation of an algorithm proposed earlier with the advantage that it reduces the time complexity from O(mlogm) to O(m) where m is the number of nodes in the tail-biting trellis. A necessary condition for the output of the algorithm to differ from the output of the ideal ML decoder is reduced and simulation results on an AWGN channel using tail-biting rrellises for two rate 1/2 convoluational codes with memory 4 and 6 respectively are reported
Instantaneously Trained Neural Networks
Venue: arXiv cs.NE 2006
Year: 2006

This paper presents a review of instantaneously trained neural networks (ITNNs). These networks trade learning time for size and, in the basic model, a new hidden node is created for each training sample. Various versions of the corner-classification family of ITNNs, which have found applications in artificial intelligence (AI), are described. Implementation issues are also considered.