OpenRaiser/Intern-Atlas huggingface dataset:
Bounds for Compression in Streaming Models
Venue: arXiv cs.IT 2008
Year: 2008

Compression algorithms and streaming algorithms are both powerful tools for dealing with massive data sets, but many of the best compression algorithms -- e.g., those based on the Burrows-Wheeler Transform -- at first seem incompatible with streaming. In this paper we consider several popular streaming models and ask in which, if any, we can compress as well as we can with the BWT. We first prove a nearly tight tradeoff between memory and redundancy for the Standard, Multipass and W-Streams models, demonstrating a bound that is achievable with the BWT but unachievable in those models. We then show we can compute the related Schindler Transform in the StreamSort model and the BWT in the Read-Write model and, thus, achieve that bound.
Evaluating the Impact of Information Distortion on Normalized Compression Distance
Venue: arXiv cs.IT 2008
Year: 2008

In this paper we apply different techniques of information distortion on a set of classical books written in English. We study the impact that these distortions have upon the Kolmogorov complexity and the clustering by compression technique (the latter based on Normalized Compression Distance, NCD). We show how to decrease the complexity of the considered books introducing several modifications in them. We measure how the information contained in each book is maintained using a clustering error measure. We find experimentally that the best way to keep the clustering error is by means of modifications in the most frequent words. We explain the details of these information distortions and we compare with other kinds of modifications like random word distortions and unfrequent word distortions. Finally, some phenomenological explanations from the different empirical results that have been carried out are presented.
Representation and Measure of Structural Information
Venue: arXiv cs.CC 2008
Year: 2008

We introduce a uniform representation of general objects that captures the regularities with respect to their structure. It allows a representation of a general class of objects including geometric patterns and images in a sparse, modular, hierarchical, and recursive manner. The representation can exploit any computable regularity in objects to compactly describe them, while also being capable of representing random objects as raw data. A set of rules uniformly dictates the interpretation of the representation into raw signal, which makes it possible to ask what pattern a given raw signal contains. Also, it allows simple separation of the information that we wish to ignore from that which we measure, by using a set of maps to delineate the a priori parts of the objects, leaving only the information in the structure. Using the representation, we introduce a measure of information in general objects relative to structures defined by the set of maps. We point out that the common prescription of encoding objects by strings to use Kolmogorov complexity is meaningless when, as often is the case, the encoding is not specified in any way other than that it exists. Noting this, we define the measure directly in terms of the structures of the spaces in which the objects reside. As a result, the measure is defined relative to a set of maps that characterize the structures. It turns out that the measure is equivalent to Kolmogorov complexity when it is defined relative to the maps characterizing the structure of natural numbers. Thus, the formulation gives the larger class of objects a meaningful measure of information that generalizes Kolmogorov complexity.
Distributed Arithmetic Coding for the Asymmetric Slepian-Wolf problem
Venue: arXiv cs.IT 2008
Year: 2008

Distributed source coding schemes are typically based on the use of channels codes as source codes. In this paper we propose a new paradigm, termed "distributed arithmetic coding", which exploits the fact that arithmetic codes are good source as well as channel codes. In particular, we propose a distributed binary arithmetic coder for Slepian-Wolf coding with decoder side information, along with a soft joint decoder. The proposed scheme provides several advantages over existing Slepian-Wolf coders, especially its good performance at small block lengths, and the ability to incorporate arbitrary source models in the encoding process, e.g. context-based statistical models. We have compared the performance of distributed arithmetic coding with turbo codes and low-density parity-check codes, and found that the proposed approach has very competitive performance.
Power-Aware Real-Time Scheduling upon Identical Multiprocessor Platforms
Venue: arXiv cs.OS 2008
Year: 2008

In this paper, we address the power-aware scheduling of sporadic constrained-deadline hard real-time tasks using dynamic voltage scaling upon multiprocessor platforms. We propose two distinct algorithms. Our first algorithm is an off-line speed determination mechanism which provides an identical speed for each processor. That speed guarantees that all deadlines are met if the jobs are scheduled using EDF. The second algorithm is an on-line and adaptive speed adjustment mechanism which reduces the energy consumption while the system is running.
A Unified Framework for Pricing Credit and Equity Derivatives
Venue: arXiv cs.CE 2008
Year: 2008

We propose a model which can be jointly calibrated to the corporate bond term structure and equity option volatility surface of the same company. Our purpose is to obtain explicit bond and equity option pricing formulas that can be calibrated to find a risk neutral model that matches a set of observed market prices. This risk neutral model can then be used to price more exotic, illiquid or over-the-counter derivatives. We observe that the model implied credit default swap (CDS) spread matches the market CDS spread and that our model produces a very desirable CDS spread term structure. This is observation is worth noticing since without calibrating any parameter to the CDS spread data, it is matched by the CDS spread that our model generates using the available information from the equity options and corporate bond markets. We also observe that our model matches the equity option implied volatility surface well since we properly account for the default risk premium in the implied volatility surface. We demonstrate the importance of accounting for the default risk and stochastic interest rate in equity option pricing by comparing our results to Fouque, Papanicolaou, Sircar and Solna (2003), which only accounts for stochastic volatility.
Nash bargaining with a nondeterministic threat
Venue: arXiv cs.GT 2008
Year: 2008

We consider bargaining problems which involve two participants, with a nonempty closed, bounded convex bargaining set of points in the real plane representing all realizable bargains. We also assume that there is no definite threat or disagreement point which will provide the default bargain if the players cannot agree on some point in the bargaining set. However, there is a nondeterministic threat: if the players fail to agree on a bargain, one of them will be chosen at random with equal probability, and that chosen player will select any realizable bargain as the solution, subject to a reasonable restriction.
The Physical World as a Virtual Reality
Venue: arXiv cs.OH 2008
Year: 2008

This paper explores the idea that the universe is a virtual reality created by information processing, and relates this strange idea to the findings of modern physics about the physical world. The virtual reality concept is familiar to us from online worlds, but our world as a virtual reality is usually a subject for science fiction rather than science. Yet logically the world could be an information simulation running on a multi-dimensional space-time screen. Indeed, if the essence of the universe is information, matter, charge, energy and movement could be aspects of information, and the many conservation laws could be a single law of information conservation. If the universe were a virtual reality, its creation at the big bang would no longer be paradoxical, as every virtual system must be booted up. It is suggested that whether the world is an objective reality or a virtual reality is a matter for science to resolve. Modern information science can suggest how core physical properties like space, time, light, matter and movement could derive from information processing. Such an approach could reconcile relativity and quantum theories, with the former being how information processing creates space-time, and the latter how it creates energy and matter.
Sum Rate Maximization using Linear Precoding and Decoding in the Multiuser MIMO Downlink
Venue: arXiv cs.IT 2008
Year: 2008

We propose an algorithm to maximize the instantaneous sum data rate transmitted by a base station in the downlink of a multiuser multiple-input, multiple-output system. The transmitter and the receivers may each be equipped with multiple antennas and each user may receive more than one data stream. We show that maximizing the sum rate is closely linked to minimizing the product of mean squared errors (PMSE). The algorithm employs an uplink/downlink duality to iteratively design transmit-receive linear precoders, decoders, and power allocations that minimize the PMSE for all data streams under a sum power constraint. Numerical simulations illustrate the effectiveness of the algorithm and support the use of the PMSE criterion in maximizing the overall instantaneous data rate.
On the graph isomorphism problem
Venue: arXiv cs.CC 2008
Year: 2008

We relate the graph isomorphism problem to the solvability of certain systems of linear equations with nonnegative variables. This version replaces the two previous versions of this paper.
An omega-Power of a Finitary Language Which is a Borel Set of Infinite Rank
Venue: arXiv cs.LO 2008
Year: 2008

Omega-powers of finitary languages are omega languages in the form V^omega, where V is a finitary language over a finite alphabet X. Since the set of infinite words over X can be equipped with the usual Cantor topology, the question of the topological complexity of omega-powers naturally arises and has been raised by Niwinski, by Simonnet, and by Staiger. It has been recently proved that for each integer n > 0, there exist some omega-powers of context free languages which are Pi^0_n-complete Borel sets, and that there exists a context free language L such that L^omega is analytic but not Borel. But the question was still open whether there exists a finitary language V such that V^omega is a Borel set of infinite rank. We answer this question in this paper, giving an example of a finitary language whose omega-power is Borel of infinite rank.
Capacity Bounds for Peak-Constrained Multiantenna Wideband Channels
Venue: arXiv cs.IT 2008
Year: 2008

We derive bounds on the noncoherent capacity of a very general class of multiple-input multiple-output channels that allow for selectivity in time and frequency as well as for spatial correlation. The bounds apply to peak-constrained inputs; they are explicit in the channel's scattering function, are useful for a large range of bandwidth, and allow to coarsely identify the capacity-optimal combination of bandwidth and number of transmit antennas. Furthermore, we obtain a closed-form expression for the first-order Taylor series expansion of capacity in the limit of infinite bandwidth. From this expression, we conclude that in the wideband regime: (i) it is optimal to use only one transmit antenna when the channel is spatially uncorrelated; (ii) rank-one statistical beamforming is optimal if the channel is spatially correlated; and (iii) spatial correlation, be it at the transmitter, the receiver, or both, is beneficial.
The Quadratic Gaussian Rate-Distortion Function for Source Uncorrelated Distortions
Venue: arXiv cs.IT 2008
Year: 2008

We characterize the rate-distortion function for zero-mean stationary Gaussian sources under the MSE fidelity criterion and subject to the additional constraint that the distortion is uncorrelated to the input. The solution is given by two equations coupled through a single scalar parameter. This has a structure similar to the well known water-filling solution obtained without the uncorrelated distortion restriction. Our results fully characterize the unique statistics of the optimal distortion. We also show that, for all positive distortions, the minimum achievable rate subject to the uncorrelation constraint is strictly larger than that given by the un-constrained rate-distortion function. This gap increases with the distortion and tends to infinity and zero, respectively, as the distortion tends to zero and infinity.
Minimum Leaf Out-branching and Related Problems
Venue: arXiv cs.DS 2008
Year: 2008

Given a digraph $D$, the Minimum Leaf Out-Branching problem (MinLOB) is the problem of finding in $D$ an out-branching with the minimum possible number of leaves, i.e., vertices of out-degree 0. We prove that MinLOB is polynomial-time solvable for acyclic digraphs. In general, MinLOB is NP-hard and we consider three parameterizations of MinLOB. We prove that two of them are NP-complete for every value of the parameter, but the third one is fixed-parameter tractable (FPT). The FPT parametrization is as follows: given a digraph $D$ of order $n$ and a positive integral parameter $k$, check whether $D$ contains an out-branching with at most $n-k$ leaves (and find such an out-branching if it exists). We find a problem kernel of order $O(k^2)$ and construct an algorithm of running time $O(2^{O(k\log k)}+n^6),$ which is an `additive' FPT algorithm. We also consider transformations from two related problems, the minimum path covering and the maximum internal out-tree problems into MinLOB, which imply that some parameterizations of the two problems are FPT as well.
Programming an interpreter using molecular dynamics
Venue: arXiv cs.PL 2008
Year: 2008

PGA (ProGram Algebra) is an algebra of programs which concerns programs in their simplest form: sequences of instructions. Molecular dynamics is a simple model of computation developed in the setting of PGA, which bears on the use of dynamic data structures in programming. We consider the programming of an interpreter for a program notation that is close to existing assembly languages using PGA with the primitives of molecular dynamics as basic instructions. It happens that, although primarily meant for explaining programming language features relating to the use of dynamic data structures, the collection of primitives of molecular dynamics in itself is suited to our programming wants.
An Application of the Feferman-Vaught Theorem to Automata and Logics for<br> Words over an Infinite Alphabet
Venue: arXiv cs.LO 2008
Year: 2008

We show that a special case of the Feferman-Vaught composition theorem gives rise to a natural notion of automata for finite words over an infinite alphabet, with good closure and decidability properties, as well as several logical characterizations. We also consider a slight extension of the Feferman-Vaught formalism which allows to express more relations between component values (such as equality), and prove related decidability results. From this result we get new classes of decidable logics for words over an infinite alphabet.
3D/4D ultrasound registration of bone
Venue: arXiv cs.OH 2008
Year: 2008

This paper presents a method to reduce the invasiveness of Computer Assisted Orthopaedic Surgery (CAOS) using ultrasound. In this goal, we need to develop a method for 3D/4D ultrasound registration. The premilinary results of this study suggest that the development of a robust and ``realtime'' 3D/4D ultrasound registration is feasible.
Cut Elimination for a Logic with Generic Judgments and Induction
Venue: arXiv cs.LO 2008
Year: 2008

This paper presents a cut-elimination proof for the logic $LG^ω$, which is an extension of a proof system for encoding generic judgments, the logic $\FOLDNb$ of Miller and Tiu, with an induction principle. The logic $LG^ω$, just as $\FOLDNb$, features extensions of first-order intuitionistic logic with fixed points and a ``generic quantifier'', $\nabla$, which is used to reason about the dynamics of bindings in object systems encoded in the logic. A previous attempt to extend $\FOLDNb$ with an induction principle has been unsuccessful in modeling some behaviours of bindings in inductive specifications. It turns out that this problem can be solved by relaxing some restrictions on $\nabla$, in particular by adding the axiom $B \equiv \nabla x. B$, where $x$ is not free in $B$. We show that by adopting the equivariance principle, the presentation of the extended logic can be much simplified. This paper contains the technical proofs for the results stated in \cite{tiu07entcs}; readers are encouraged to consult \cite{tiu07entcs} for motivations and examples for $LG^ω.$
Spreadsheet Hell
Venue: arXiv cs.CY 2008
Year: 2008

This management paper looks at the real world issues faced by practitioners managing spreadsheets through the production phase of their life cycle. It draws on the commercial experience of several developers working with large corporations, either as employees or consultants or contractors. It provides commercial examples of some of the practicalities involved with spreadsheet use around the enterprise.
From k-SAT to k-CSP: Two Generalized Algorithms
Venue: arXiv cs.DS 2008
Year: 2008

Constraint satisfaction problems (CSPs) models many important intractable NP-hard problems such as propositional satisfiability problem (SAT). Algorithms with non-trivial upper bounds on running time for restricted SAT with bounded clause length k (k-SAT) can be classified into three styles: DPLL-like, PPSZ-like and Local Search, with local search algorithms having already been generalized to CSP with bounded constraint arity k (k-CSP). We generalize a DPLL-like algorithm in its simplest form and a PPSZ-like algorithm from k-SAT to k-CSP. As far as we know, this is the first attempt to use PPSZ-like strategy to solve k-CSP, and before little work has been focused on the DPLL-like or PPSZ-like strategies for k-CSP.
On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth
Venue: arXiv cs.DM 2008
Year: 2008

Some 25 years ago Valiant introduced an algebraic model of computation in order to study the complexity of evaluating families of polynomials. The theory was introduced along with the complexity classes VP and VNP which are analogues of the classical classes P and NP. Families of polynomials that are difficult to evaluate (that is, VNP-complete) includes the permanent and hamiltonian polynomials. In a previous paper the authors together with P. Koiran studied the expressive power of permanent and hamiltonian polynomials of matrices of bounded treewidth, as well as the expressive power of perfect matchings of planar graphs. It was established that the permanent and hamiltonian polynomials of matrices of bounded treewidth are equivalent to arithmetic formulas. Also, the sum of weights of perfect matchings of planar graphs was shown to be equivalent to (weakly) skew circuits. In this paper we continue the research in the direction described above, and study the expressive power of permanents, hamiltonians and perfect matchings of matrices that have bounded pathwidth or bounded cliquewidth. In particular, we prove that permanents, hamiltonians and perfect matchings of matrices that have bounded pathwidth express exactly arithmetic formulas. This is an improvement of our previous result for matrices of bounded treewidth. Also, for matrices of bounded weighted cliquewidth we show membership in VP for these polynomials.
Deterministic Design of Low-Density Parity-Check Codes for Binary Erasure Channels
Venue: arXiv cs.IT 2008
Year: 2008

We propose a deterministic method to design irregular Low-Density Parity-Check (LDPC) codes for binary erasure channels (BEC). Compared to the existing methods, which are based on the application of asymptomatic analysis tools such as density evolution or Extrinsic Information Transfer (EXIT) charts in an optimization process, the proposed method is much simpler and faster. Through a number of examples, we demonstrate that the codes designed by the proposed method perform very closely to the best codes designed by optimization. An important property of the proposed designs is the flexibility to select the number of constituent variable node degrees P. The proposed designs include existing deterministic designs as a special case with P = N-1, where N is the maximum variable node degree. Compared to the existing deterministic designs, for a given rate and a given d > 0, the designed ensembles can have a threshold in d-neighborhood of the capacity upper bound with smaller values of P and N. They can also achieve the capacity of the BEC as N, and correspondingly P and the maximum check node degree tend to infinity.
Multiparty Communication Complexity of Disjointness
Venue: arXiv cs.CC 2008
Year: 2008

We obtain a lower bound of n^Omega(1) on the k-party randomized communication complexity of the Disjointness function in the `Number on the Forehead' model of multiparty communication when k is a constant. For k=o(loglog n), the bounds remain super-polylogarithmic i.e. (log n)^omega(1). The previous best lower bound for three players until recently was Omega(log n). Our bound separates the communication complexity classes NP^{CC}_k and BPP^{CC}_k for k=o(loglog n). Furthermore, by the results of Beame, Pitassi and Segerlind \cite{BPS07}, our bound implies proof size lower bounds for tree-like, degree k-1 threshold systems and superpolynomial size lower bounds for Lovasz-Schrijver proofs. Sherstov \cite{She07b} recently developed a novel technique to obtain lower bounds on two-party communication using the approximate polynomial degree of boolean functions. We obtain our results by extending his technique to the multi-party setting using ideas from Chattopadhyay \cite{Cha07}. A similar bound for Disjointness has been recently and independently obtained by Lee and Shraibman.
Comparison of Spreadsheets with other Development Tools (limitations, solutions, workarounds and alternatives)
Venue: arXiv cs.SE 2008
Year: 2008

The spreadsheet paradigm has some unique risks and challenges that are not present in more traditional development technologies. Many of the recent advances in other branches of software development have bypassed spreadsheets and spreadsheet developers. This paper compares spreadsheets and spreadsheet development to more traditional platforms such as databases and procedural languages. It also considers the fundamental danger introduced in the transition from paper spreadsheets to electronic. Suggestions are made to manage the risks and work around the limitations.
Encoding changing country codes for the Semantic Web with ISO 3166 and SKOS
Venue: arXiv cs.IR 2008
Year: 2008

This paper shows how authority files can be encoded for the Semantic Web with the Simple Knowledge Organisation System (SKOS). In particular the application of SKOS for encoding the structure, management, and utilization of country codes as defined in ISO 3166 is demonstrated. The proposed encoding gives a use case for SKOS that includes features that have only been discussed little so far, such as multiple notations, nested concept schemes, changes by versioning.
Increased security through open source
Venue: arXiv cs.CR 2008
Year: 2008

In this paper we discuss the impact of open source on both the security and transparency of a software system. We focus on the more technical aspects of this issue, combining and extending arguments developed over the years. We stress that our discussion of the problem only applies to software for general purpose computing systems. For embedded systems, where the software usually cannot easily be patched or upgraded, different considerations may apply.