OpenRaiser/Intern-Atlas huggingface dataset:
On Conditional Branches in Optimal Search Trees
Venue: arXiv cs.PF 2006
Year: 2006

Algorithms for efficiently finding optimal alphabetic decision trees -- such as the Hu-Tucker algorithm -- are well established and commonly used. However, such algorithms generally assume that the cost per decision is uniform and thus independent of the outcome of the decision. The few algorithms without this assumption instead use one cost if the decision outcome is ``less than'' and another cost otherwise. In practice, neither assumption is accurate for software optimized for today's microprocessors. Such software generally has one cost for the more likely decision outcome and a greater cost -- often far greater -- for the less likely decision outcome. This problem and generalizations thereof are thus applicable to hard coding static decision tree instances in software, e.g., for optimizing program bottlenecks or for compiling switch statements. An O(n^3)-time O(n^2)-space dynamic programming algorithm can solve this optimal binary decision tree problem, and this approach has many generalizations that optimize for the behavior of processors with predictive branch capabilities, both static and dynamic. Solutions to this formulation are often faster in practice than ``optimal'' decision trees as formulated in the literature. Different search paradigms can sometimes yield even better performance.
Cryptographic Pseudo-Random Sequences from the Chaotic Henon Map
Venue: arXiv cs.CR 2006
Year: 2006

A scheme for pseudo-random binary sequence generation based on the two-dimensional discrete-time Henon map is proposed. Properties of the proposed sequences pertaining to linear complexity, linear complexity profile, correlation and auto-correlation are investigated. All these properties of the sequences suggest a strong resemblance to random sequences. Results of statistical testing of the sequences are found encouraging. An attempt is made to estimate the keyspace size if the proposed scheme is used for cryptographic applications. The keyspace size is found to be large and is dependent on the precision of the computing platform used.
Cohomology in Grothendieck Topologies and Lower Bounds in Boolean Complexity II: A Simple Example
Venue: arXiv cs.CC 2006
Year: 2006

In a previous paper we have suggested a number of ideas to attack circuit size complexity with cohomology. As a simple example, we take circuits that can only compute the AND of two inputs, which essentially reduces to SET COVER. We show a very special case of the cohomological approach (one particular free category, using injective and superskyscraper sheaves) gives the linear programming bound coming from the relaxation of the standard integer programming reformulation of SET COVER.
APHRODITE: an Anomaly-based Architecture for False Positive Reduction
Venue: arXiv cs.CR 2006
Year: 2006

We present APHRODITE, an architecture designed to reduce false positives in network intrusion detection systems. APHRODITE works by detecting anomalies in the output traffic, and by correlating them with the alerts raised by the NIDS working on the input traffic. Benchmarks show a substantial reduction of false positives and that APHRODITE is effective also after a "quick setup", i.e. in the realistic case in which it has not been "trained" and set up optimally
Unification of multi-lingual scientific terminological resources using the ISO 16642 standard. The TermSciences initiative
Venue: arXiv cs.CL 2006
Year: 2006

This paper presents the TermSciences portal, which deals with the implementation of a conceptual model that uses the recent ISO 16642 standard (Terminological Markup Framework). This standard turns out to be suitable for concept modeling since it allowed for organizing the original resources by concepts and to associate the various terms for a given concept. Additional structuring is produced by sharing conceptual relationships, that is, cross-linking of resource results through the introduction of semantic relations which may have initially be missing.
Two Proofs of the Fisher Information Inequality via Data Processing Arguments
Venue: arXiv cs.IT 2006
Year: 2006

Two new proofs of the Fisher information inequality (FII) using data processing inequalities for mutual information and conditional variance are presented.
A Fixed-Point Type for Octave
Venue: arXiv cs.MS 2006
Year: 2006

This paper announces the availability of a fixed point toolbox for the Matlab compatible software package Octave. This toolbox is released under the GNU Public License, and can be used to model the losses in algorithms implemented in hardware. Furthermore, this paper presents as an example of the use of this toolbox, the effects of a fixed point implementation on the precision of an OFDM modulator.
Optimal Distortion-Power Tradeoffs in Sensor Networks: Gauss-Markov Random Processes
Venue: arXiv cs.IT 2006
Year: 2006

We investigate the optimal performance of dense sensor networks by studying the joint source-channel coding problem. The overall goal of the sensor network is to take measurements from an underlying random process, code and transmit those measurement samples to a collector node in a cooperative multiple access channel with feedback, and reconstruct the entire random process at the collector node. We provide lower and upper bounds for the minimum achievable expected distortion when the underlying random process is stationary and Gaussian. In the case where the random process is also Markovian, we evaluate the lower and upper bounds explicitly and show that they are of the same order for a wide range of sum power constraints. Thus, for a Gauss-Markov random process, under these sum power constraints, we determine the achievability scheme that is order-optimal, and express the minimum achievable expected distortion as a function of the sum power constraint.
Demand-driven Inlining in a Region-based Optimizer for ILP Architectures
Venue: arXiv cs.DC 2006
Year: 2006

Region-based compilation repartitions a program into more desirable compilation units using profiling information and procedure inlining to enable region formation analysis. Heuristics play a key role in determining when it is most beneficial to inline procedures during region formation. An ILP optimizing compiler using a region-based approach restructures a program to better reflect dynamic behavior and increase interprocedural optimization and scheduling opportunities. This paper presents an interprocedural compilation technique which performs procedure inlining on-demand, rather than as a separate phase, to improve the ability of a region-based optimizer to control code growth, compilation time and memory usage while improving performance. The interprocedural region formation algorithm utilizes a demand-driven, heuristics-guided approach to inlining, restructuring an input program into interprocedural regions. Experimental results are presented to demonstrate the impact of the algorithm and several inlining heuristics upon a number of traditional and novel compilation characteristics within a region-based ILP compiler and simulator.
Will the Butterfly Cipher keep your Network Data secure? Developments in Computer Encryption
Venue: arXiv cs.CR 2006
Year: 2006

This paper explains the recent developments in security and encryption. The Butterfly cipher and quantum cryptography are reviewed and compared. Examples of their relative uses are discussed and suggestions for future developments considered. In addition application to network security together with a substantial review of classification of encryption systems and a summary of security weaknesses are considered.
Survivable Routing in IP-over-WDM Networks in the Presence of Multiple Failures
Venue: arXiv cs.NI 2006
Year: 2006

Failure restoration at the IP layer in IP-over-WDM networks requires to map the IP topology on the WDM topology in such a way that a failure at the WDM layer leaves the IP topology connected. Such a mapping is called $survivable$. As finding a survivable mapping is known to be NP-complete, in practice it requires a heuristic approach. We have introduced in [1] a novel algorithm called ``SMART'', that is more effective and scalable than the heuristics known to date. Moreover, the formal analysis of SMART [2] has led to new applications: the formal verification of the existence of a survivable mapping, and a tool tracing and repairing the vulnerable areas of the network. In this paper we extend the theoretical analysis in [2] by considering $multiple failures$.
Universal decoding with an erasure option
Venue: arXiv cs.IT 2006
Year: 2006

Motivated by applications of rateless coding, decision feedback, and ARQ, we study the problem of universal decoding for unknown channels, in the presence of an erasure option. Specifically, we harness the competitive minimax methodology developed in earlier studies, in order to derive a universal version of Forney's classical erasure/list decoder, which in the erasure case, optimally trades off between the probability of erasure and the probability of undetected error. The proposed universal erasure decoder guarantees universal achievability of a certain fraction $ξ$ of the optimum error exponents of these probabilities (in a sense to be made precise in the sequel). A single--letter expression for $ξ$, which depends solely on the coding rate and the threshold, is provided. The example of the binary symmetric channel is studied in full detail, and some conclusions are drawn.
Evolutionary Socioeconomics: a Schumpeterian Computer Simulation
Venue: arXiv cs.GT 2006
Year: 2006

The following note contains a computer simulation concerning the struggle between two companies: the first one is "the biggest zaibatsu of all", while the second one is "small, fast, ruthless". The model is based on a neo-Schumpeterian framework operating in a Darwinian evolutionary environment. After running the program a large number of times, two characteristics stand out: -- There is always a winner which takes it all, while the loser disappears. -- The key to success is the ability to employ efficiently the technological innovations. The topic of the present paper is strictly related with the content of the following notes: Michele Tucci, Evolution and Gravitation: a Computer Simulation of a Non-Walrasian Equilibrium Model; Michele Tucci, Oligopolistic Competition in an Evolutionary Environment: a Computer Simulation. The texts can be downloaded respectively at the following addresses: http://arxiv.org/abs/cs.CY/0209017 http://arxiv.org/abs/cs.CY/0501037 These references include some preliminary considerations regarding the comparison between the evolutionary and the gravitational paradigms and the evaluation of approaches belonging to rival schools of economic thought.
Polynomial-time algorithms for coding across multiple unicasts
Venue: arXiv cs.NI 2006
Year: 2006

We consider the problem of network coding across multiple unicasts. We give, for wired and wireless networks, efficient polynomial time algorithms for finding optimal network codes within the class of network codes restricted to XOR coding between pairs of flows.
Achievable Rates for the Multiple Access Channel with Feedback and Correlated Sources
Venue: arXiv cs.IT 2006
Year: 2006

In this paper, we investigate achievable rates on the multiple access channel with feedback and correlated sources (MACFCS). The motivation for studying the MACFCS stems from the fact that in a sensor network, sensors collect and transmit correlated data to a common sink. We derive two achievable rate regions for the three-node MACFCS.
Modeling and Mathematical Analysis of Swarms of Microscopic Robots
Venue: arXiv cs.MA 2006
Year: 2006

The biologically-inspired swarm paradigm is being used to design self-organizing systems of locally interacting artificial agents. A major difficulty in designing swarms with desired characteristics is understanding the causal relation between individual agent and collective behaviors. Mathematical analysis of swarm dynamics can address this difficulty to gain insight into system design. This paper proposes a framework for mathematical modeling of swarms of microscopic robots that may one day be useful in medical applications. While such devices do not yet exist, the modeling approach can be helpful in identifying various design trade-offs for the robots and be a useful guide for their eventual fabrication. Specifically, we examine microscopic robots that reside in a fluid, for example, a bloodstream, and are able to detect and respond to different chemicals. We present the general mathematical model of a scenario in which robots locate a chemical source. We solve the scenario in one-dimension and show how results can be used to evaluate certain design decisions.
On Multistage Successive Refinement for Wyner-Ziv Source Coding with Degraded Side Informations
Venue: arXiv cs.IT 2006
Year: 2006

We provide a complete characterization of the rate-distortion region for the multistage successive refinement of the Wyner-Ziv source coding problem with degraded side informations at the decoder. Necessary and sufficient conditions for a source to be successively refinable along a distortion vector are subsequently derived. A source-channel separation theorem is provided when the descriptions are sent over independent channels for the multistage case. Furthermore, we introduce the notion of generalized successive refinability with multiple degraded side informations. This notion captures whether progressive encoding to satisfy multiple distortion constraints for different side informations is as good as encoding without progressive requirement. Necessary and sufficient conditions for generalized successive refinability are given. It is shown that the following two sources are generalized successively refinable: (1) the Gaussian source with degraded Gaussian side informations, (2) the doubly symmetric binary source when the worse side information is a constant. Thus for both cases, the failure of being successively refinable is only due to the inherent uncertainty on which side information will occur at the decoder, but not the progressive encoding requirement.
An Information-Spectrum Approach to Multiterminal Rate-Distortion Theory
Venue: arXiv cs.IT 2006
Year: 2006

An information-spectrum approach is applied to solve the multiterminal source coding problem for correlated general sources, where sources may be nonstationary and/or nonergodic, and the distortion measure is arbitrary and may be nonadditive. A general formula for the rate-distortion region of the multiterminal source coding problem with the maximum distortion criterion under fixed-length coding is shown in this correspondence.
Complementary Set Matrices Satisfying a Column Correlation Constraint
Venue: arXiv cs.IT 2006
Year: 2006

Motivated by the problem of reducing the peak to average power ratio (PAPR) of transmitted signals, we consider a design of complementary set matrices whose column sequences satisfy a correlation constraint. The design algorithm recursively builds a collection of $2^{t+1}$ mutually orthogonal (MO) complementary set matrices starting from a companion pair of sequences. We relate correlation properties of column sequences to that of the companion pair and illustrate how to select an appropriate companion pair to ensure that a given column correlation constraint is satisfied. For $t=0$, companion pair properties directly determine matrix column correlation properties. For $t\geq 1$, reducing correlation merits of the companion pair may lead to improved column correlation properties. However, further decrease of the maximum out-off-phase aperiodic autocorrelation of column sequences is not possible once the companion pair correlation merit is less than a threshold determined by $t$. We also reveal a design of the companion pair which leads to complementary set matrices with Golay column sequences. Exhaustive search for companion pairs satisfying a column correlation constraint is infeasible for medium and long sequences. We instead search for two shorter length sequences by minimizing a cost function in terms of their autocorrelation and crosscorrelation merits. Furthermore, an improved cost function which helps in reducing the maximum out-off-phase column correlation is derived based on the properties of the companion pair. By exploiting the well-known Welch bound, sufficient conditions for the existence of companion pairs which satisfy a set of column correlation constraints are also given.
Reasoning and Planning with Sensing Actions, Incomplete Information, and Static Causal Laws using Answer Set Programming
Venue: arXiv cs.AI 2006
Year: 2006

We extend the 0-approximation of sensing actions and incomplete information in [Son and Baral 2000] to action theories with static causal laws and prove its soundness with respect to the possible world semantics. We also show that the conditional planning problem with respect to this approximation is NP-complete. We then present an answer set programming based conditional planner, called ASCP, that is capable of generating both conformant plans and conditional plans in the presence of sensing actions, incomplete information about the initial state, and static causal laws. We prove the correctness of our implementation and argue that our planner is sound and complete with respect to the proposed approximation. Finally, we present experimental results comparing ASCP to other planners.
SAT Techniques for Lexicographic Path Orders
Venue: arXiv cs.SC 2006
Year: 2006

This seminar report is concerned with expressing LPO-termination of term rewrite systems as a satisfiability problem in propositional logic. After relevant algorithms are explained, experimental results are reported.
Spanners for Geometric Intersection Graphs
Venue: arXiv cs.CG 2006
Year: 2006

Efficient algorithms are presented for constructing spanners in geometric intersection graphs. For a unit ball graph in R^k, a (1+ε)-spanner is obtained using efficient partitioning of the space into hypercubes and solving bichromatic closest pair problems. The spanner construction has almost equivalent complexity to the construction of Euclidean minimum spanning trees. The results are extended to arbitrary ball graphs with a sub-quadratic running time. For unit ball graphs, the spanners have a small separator decomposition which can be used to obtain efficient algorithms for approximating proximity problems like diameter and distance queries. The results on compressed quadtrees, geometric graph separators, and diameter approximation might be of independent interest.
Peer to Peer Networks for Defense Against Internet Worms
Venue: arXiv cs.CR 2006
Year: 2006

Internet worms, which spread in computer networks without human mediation, pose a severe threat to computer systems today. The rate of propagation of worms has been measured to be extremely high and they can infect a large fraction of their potential hosts in a short time. We study two different methods of patch dissemination to combat the spread of worms. We first show that using a fixed number of patch servers performs woefully inadequately against Internet worms. We then show that by exploiting the exponential data dissemination capability of P2P systems, the spread of worms can be halted very effectively. We compare the two methods by using fluid models to compute two quantities of interest: the time taken to effectively combat the progress of the worm and the maximum number of infected hosts. We validate our models using Internet measurements and simulations.
Evaluating the Robustness of Learning from Implicit Feedback
Venue: arXiv cs.LG 2006
Year: 2006

This paper evaluates the robustness of learning from implicit feedback in web search. In particular, we create a model of user behavior by drawing upon user studies in laboratory and real-world settings. The model is used to understand the effect of user behavior on the performance of a learning algorithm for ranked retrieval. We explore a wide range of possible user behaviors and find that learning from implicit feedback can be surprisingly robust. This complements previous results that demonstrated our algorithm's effectiveness in a real-world search engine application.
An Unfolding-Based Semantics for Logic Programming with Aggregates
Venue: arXiv cs.SE 2006
Year: 2006

The paper presents two equivalent definitions of answer sets for logic programs with aggregates. These definitions build on the notion of unfolding of aggregates, and they are aimed at creating methodologies to translate logic programs with aggregates to normal logic programs or positive programs, whose answer set semantics can be used to defined the semantics of the original programs. The first definition provides an alternative view of the semantics for logic programming with aggregates described by Pelov et al. The second definition is similar to the traditional answer set definition for normal logic programs, in that, given a logic program with aggregates and an interpretation, the unfolding process produces a positive program. The paper shows how this definition can be extended to consider aggregates in the head of the rules. The proposed views of logic programming with aggregates are simple and coincide with the ultimate stable model semantics, and with other semantic characterizations for large classes of program (e.g., programs with monotone aggregates and programs that are aggregate-stratified). Moreover, it can be directly employed to support an implementation using available answer set solvers. The paper describes a system, called ASP^A, that is capable of computing answer sets of programs with arbitrary (e.g., recursively defined) aggregates.
Utility Computing and Global Grids
Venue: arXiv cs.DC 2006
Year: 2006

This chapter focuses on the use of Grid technologies to achieve utility computing. An overview of how Grids can support utility computing is first presented through the architecture of Utility Grids. Then, utility-based resource allocation is described in detail at each level of the architecture. Finally, some industrial solutions for utility computing are discussed.
QoSIP: A QoS Aware IP Routing Ptotocol for Multimedia Data
Venue: arXiv cs.NI 2006
Year: 2006

Conventional IP routing protocols are not suitable for multimedia applications which have very stringent Quality-of-Service (QoS) demands and they require a connection oriented service. For multimedia applications it is expected that the router should be able to forward the packet according to the demand of the packet and it is necessary to find a path that satisfies the specific demands of a particular application. In order to address these issues, in this paper, we have presented a QoS aware IP routing protocol where a router stores information about the QoS parameters and routes the packet accordingly. Keywords: IP Routing Protocol, Quality of Service (QoS) parameter, QoSIP, Selective Flooding.
Parallel vs. Sequential Belief Propagation Decoding of LDPC Codes over GF(q) and Markov Sources
Venue: arXiv cs.IT 2006
Year: 2006

A sequential updating scheme (SUS) for belief propagation (BP) decoding of LDPC codes over Galois fields, $GF(q)$, and correlated Markov sources is proposed, and compared with the standard parallel updating scheme (PUS). A thorough experimental study of various transmission settings indicates that the convergence rate, in iterations, of the BP algorithm (and subsequently its complexity) for the SUS is about one half of that for the PUS, independent of the finite field size $q$. Moreover, this 1/2 factor appears regardless of the correlations of the source and the channel's noise model, while the error correction performance remains unchanged. These results may imply on the 'universality' of the one half convergence speed-up of SUS decoding.