OpenRaiser/Intern-Atlas huggingface dataset:
Approximation Algorithms for K-Modes Clustering
Venue: arXiv cs.AI 2006
Year: 2006

In this paper, we study clustering with respect to the k-modes objective function, a natural formulation of clustering for categorical data. One of the main contributions of this paper is to establish the connection between k-modes and k-median, i.e., the optimum of k-median is at most twice the optimum of k-modes for the same categorical data clustering problem. Based on this observation, we derive a deterministic algorithm that achieves an approximation factor of 2. Furthermore, we prove that the distance measure in k-modes defines a metric. Hence, we are able to extend existing approximation algorithms for metric k-median to k-modes. Empirical results verify the superiority of our method.
Complexity of Monadic inf-datalog. Application to temporal logic
Venue: arXiv cs.DS 2006
Year: 2006

In [11] we defined Inf-Datalog and characterized the fragments of Monadic inf-Datalog that have the same expressive power as Modal Logic (resp. $CTL$, alternation-free Modal $μ$-calculus and Modal $μ$-calculus). We study here the time and space complexity of evaluation of Monadic inf-Datalog programs on finite models. We deduce a new unified proof that model checking has 1. linear data and program complexities (both in time and space) for $CTL$ and alternation-free Modal $μ$-calculus, and 2. linear-space (data and program) complexities, linear-time program complexity and polynomial-time data complexity for $Lμ\_k$ (Modal $μ$-calculus with fixed alternation-depth at most $k$).}
If a tree casts a shadow is it telling the time?
Venue: arXiv cs.MA 2006
Year: 2006

Physical processes are computations only when we use them to externalize thought. Computation is the performance of one or more fixed processes within a contingent environment. We reformulate the Church-Turing thesis so that it applies to programs rather than to computability. When suitably formulated agent-based computing in an open, multi-scalar environment represents the current consensus view of how we interact with the world. But we don't know how to formulate multi-scalar environments.
Theoretical Properties of Projection Based Multilayer Perceptrons with Functional Inputs
Venue: arXiv cs.NE 2006
Year: 2006

Many real world data are sampled functions. As shown by Functional Data Analysis (FDA) methods, spectra, time series, images, gesture recognition data, etc. can be processed more efficiently if their functional nature is taken into account during the data analysis process. This is done by extending standard data analysis methods so that they can apply to functional inputs. A general way to achieve this goal is to compute projections of the functional data onto a finite dimensional sub-space of the functional space. The coordinates of the data on a basis of this sub-space provide standard vector representations of the functions. The obtained vectors can be processed by any standard method. In our previous work, this general approach has been used to define projection based Multilayer Perceptrons (MLPs) with functional inputs. We study in this paper important theoretical properties of the proposed model. We show in particular that MLPs with functional inputs are universal approximators: they can approximate to arbitrary accuracy any continuous mapping from a compact sub-space of a functional space to R. Moreover, we provide a consistency result that shows that any mapping from a functional space to R can be learned thanks to examples by a projection based MLP: the generalization mean square error of the MLP decreases to the smallest possible mean square error on the data when the number of examples goes to infinity.
Complexity of Consistent Query Answering in Databases under Cardinality-Based and Incremental Repair Semantics
Venue: arXiv cs.DB 2006
Year: 2006

Consistent Query Answering (CQA) is the problem of computing from a database the answers to a query that are consistent with respect to certain integrity constraints that the database, as a whole, may fail to satisfy. Consistent answers have been characterized as those that are invariant under certain minimal forms of restoration of the database consistency. We investigate algorithmic and complexity theoretic issues of CQA under database repairs that minimally depart -wrt the cardinality of the symmetric difference- from the original database. We obtain first tight complexity bounds. We also address the problem of incremental complexity of CQA, that naturally occurs when an originally consistent database becomes inconsistent after the execution of a sequence of update operations. Tight bounds on incremental complexity are provided for various semantics under denial constraints. Fixed parameter tractability is also investigated in this dynamic context, where the size of the update sequence becomes the relevant parameter.
The Poincare conjecture for digital spaces. Properties of digital n-dimensional disks and spheres
Venue: arXiv cs.DM 2006
Year: 2006

Motivated by the Poincare conjecture, we study properties of digital n-dimensional spheres and disks, which are digital models of their continuous counterparts. We introduce homeomorphic transformations of digital manifolds, which retain the connectedness, the dimension, the Euler characteristics and the homology groups of manifolds. We find conditions where an n-dimensional digital manifold is the n-dimensional digital sphere and discuss the link between continuous closed n-manifolds and their digital models.
Certain new M-matrices and their properties and applications
Venue: arXiv cs.DM 2006
Year: 2006

The Mn-matrix was defined by Mohan [20] in which he has shown a method of constructing (1,-1)-matrices and studied some of their properties. The (1,-1)-matrices were constructed and studied by Cohn [5],Wang [33], Ehrlich [8] and Ehrlich and Zeller[9]. But in this paper, while giving some resemblances of this matrix with Hadamard matrix, and by naming it as M-matrix, we show how to construct partially balanced incomplete block (PBIB) designs and some regular bipartite graphs by it. We have considered two types of these M- matrices. Also we will make a mention of certain applications of these M-matrices in signal and communication processing, and network systems and end with some open problems.
UniCalc.LIN: a linear constraint solver for the UniCalc system
Venue: arXiv cs.MS 2006
Year: 2006

In this short paper we present a linear constraint solver for the UniCalc system, an environment for reliable solution of mathematical modeling problems.
Structural Alignments of pseudo-knotted RNA-molecules in polynomial time
Venue: arXiv cs.DS 2006
Year: 2006

An RNA molecule is structured on several layers. The primary and most obvious structure is its sequence of bases, i.e. a word over the alphabet {A,C,G,U}. The higher structure is a set of one-to-one base-pairings resulting in a two-dimensional folding of the one-dimensional sequence. One speaks of a secondary structure if these pairings do not cross and of a tertiary structure otherwise. Since the folding of the molecule is important for its function, the search for related RNA molecules should not only be restricted to the primary structure. It seems sensible to incorporate the higher structures in the search. Based on this assumption and certain edit-operations a distance between two arbitrary structures can be defined. It is known that the general calculation of this measure is NP-complete \cite{zhang02similarity}. But for some special cases polynomial algorithms are known. Using a new formal description of secondary and tertiary structures, we extend the class of structures for which the distance can be calculated in polynomial time. In addition the presented algorithm may be used to approximate the edit-distance between two arbitrary structures with a constant ratio.
Extension of the functionality of the symbolic program FORM by external software
Venue: arXiv cs.SC 2006
Year: 2006

We describe the implementation of facilities for the communication with external resources in the Symbolic Manipulation System FORM. This is done according to the POSIX standards defined for the UNIX operating system. We present a number of examples that illustrate the increased power due to these new capabilities.
Polynomial Time Nondimensionalisation of Ordinary Differential Equations via their Lie Point Symmetries
Venue: arXiv cs.SC 2006
Year: 2006

Lie group theory states that knowledge of a $m$-parameters solvable group of symmetries of a system of ordinary differential equations allows to reduce by $m$ the number of equation. We apply this principle by finding dilatations and translations that are Lie point symmetries of considered ordinary differential system. By rewriting original problem in an invariant coordinates set for these symmetries, one can reduce the involved number of parameters. This process is classically call nondimensionalisation in dimensional analysis. We present an algorithm based on this standpoint and show that its arithmetic complexity is polynomial in input's size.
Quantum Fuzzy Sets: Blending Fuzzy Set Theory and Quantum Computation
Venue: arXiv cs.LO 2006
Year: 2006

In this article we investigate a way in which quantum computing can be used to extend the class of fuzzy sets. The core idea is to see states of a quantum register as characteristic functions of quantum fuzzy subsets of a given set. As the real unit interval is embedded in the Bloch sphere, every fuzzy set is automatically a quantum fuzzy set. However, a generic quantum fuzzy set can be seen as a (possibly entangled) superposition of many fuzzy sets at once, offering new opportunities for modeling uncertainty. After introducing the main framework of quantum fuzzy set theory, we analyze the standard operations of fuzzification and defuzzification from our viewpoint. We conclude this preliminary paper with a list of possible applications of quantum fuzzy sets to pattern recognition, as well as future directions of pure research in quantum fuzzy set theory.
Octave-GTK: A GTK binding for GNU Octave
Venue: arXiv cs.SE 2006
Year: 2006

This paper discusses the problems faced with interoperability between two programming languages, with respect to GNU Octave, and GTK API written in C, to provide the GTK API on Octave.Octave-GTK is the fusion of two different API's: one exported by GNU Octave [scientific computing tool] and the other GTK [GUI toolkit]; this enables one to use GTK primitives within GNU Octave, to build graphical front ends,at the same time using octave engine for number crunching power. This paper illustrates our implementation of binding logic, and shows results extended to various other libraries using the same base code generator. Also shown, are methods of code generation, binding automation, and the niche we plan to fill in the absence of GUI in Octave. Canonical discussion of advantages, feasibility and problems faced in the process are elucidated.
Energy-Efficient Power and Rate Control with QoS Constraints: A Game-Theoretic Approach
Venue: arXiv cs.IT 2006
Year: 2006

A game-theoretic model is proposed to study the cross-layer problem of joint power and rate control with quality of service (QoS) constraints in multiple-access networks. In the proposed game, each user seeks to choose its transmit power and rate in a distributed manner in order to maximize its own utility and at the same time satisfy its QoS requirements. The user's QoS constraints are specified in terms of the average source rate and average delay. The utility function considered here measures energy efficiency and the delay includes both transmission and queueing delays. The Nash equilibrium solution for the proposed non-cooperative game is derived and a closed-form expression for the utility achieved at equilibrium is obtained. It is shown that the QoS requirements of a user translate into a "size" for the user which is an indication of the amount of network resources consumed by the user. Using this framework, the tradeoffs among throughput, delay, network capacity and energy efficiency are also studied.
A Knowledge-Based Approach for Selecting Information Sources
Venue: arXiv cs.AI 2006
Year: 2006

Through the Internet and the World-Wide Web, a vast number of information sources has become available, which offer information on various subjects by different providers, often in heterogeneous formats. This calls for tools and methods for building an advanced information-processing infrastructure. One issue in this area is the selection of suitable information sources in query answering. In this paper, we present a knowledge-based approach to this problem, in the setting where one among a set of information sources (prototypically, data repositories) should be selected for evaluating a user query. We use extended logic programs (ELPs) to represent rich descriptions of the information sources, an underlying domain theory, and user queries in a formal query language (here, XML-QL, but other languages can be handled as well). Moreover, we use ELPs for declarative query analysis and generation of a query description. Central to our approach are declarative source-selection programs, for which we define syntax and semantics. Due to the structured nature of the considered data items, the semantics of such programs must carefully respect implicit context information in source-selection rules, and furthermore combine it with possible user preferences. A prototype implementation of our approach has been realized exploiting the DLV KR system and its plp front-end for prioritized ELPs. We describe a representative example involving specific movie databases, and report about experimental results.
Cognitive Radio: An Information-Theoretic Perspective
Venue: arXiv cs.IT 2006
Year: 2006

Cognitive radios have been proposed as a means to implement efficient reuse of the licensed spectrum. The key feature of a cognitive radio is its ability to recognize the primary (licensed) user and adapt its communication strategy to minimize the interference that it generates. We consider a communication scenario in which the primary and the cognitive user wish to communicate to different receivers, subject to mutual interference. Modeling the cognitive radio as a transmitter with side-information about the primary transmission, we characterize the largest rate at which the cognitive radio can reliably communicate under the constraint that (i) no interference is created for the primary user, and (ii) the primary encoder-decoder pair is oblivious to the presence of the cognitive radio.
On the Foundations of Universal Sequence Prediction
Venue: arXiv cs.LG 2006
Year: 2006

Solomonoff completed the Bayesian framework by providing a rigorous, unique, formal, and universal choice for the model class and the prior. We discuss in breadth how and in which sense universal (non-i.i.d.) sequence prediction solves various (philosophical) problems of traditional Bayesian sequence prediction. We show that Solomonoff's model possesses many desirable properties: Fast convergence and strong bounds, and in contrast to most classical continuous prior densities has no zero p(oste)rior problem, i.e. can confirm universal hypotheses, is reparametrization and regrouping invariant, and avoids the old-evidence and updating problem. It even performs well (actually better) in non-computable environments.
Computational Modeling in Applied Problems: collected papers on econometrics, operations research, game theory and simulation
Venue: arXiv cs.OH 2006
Year: 2006

Computational models pervade all branches of the exact sciences and have in recent times also started to prove to be of immense utility in some of the traditionally 'soft' sciences like ecology, sociology and politics. This volume is a collection of a few cutting-edge research papers on the application of variety of computational models and tools in the analysis, interpretation and solution of vexing real-world problems and issues in economics, management, ecology and global politics by some prolific researchers in the field.
The Distribution of Patterns in Random Trees
Venue: arXiv cs.DM 2006
Year: 2006

Let $T\_n$ denote the set of unrooted labeled trees of size $n$ and let $T\_n$ be a particular (finite, unlabeled) tree. Assuming that every tree of $T\_n$ is equally likely, it is shown that the limiting distribution as $n$ goes to infinity of the number of occurrences of $M$ as an induced subtree is asymptotically normal with mean value and variance asymptotically equivalent to $μn$ and $σ^2n$, respectively, where the constants $μ>0$ and $σ\ge 0$ are computable.
On Orthogonalities in Matrices
Venue: arXiv cs.DM 2006
Year: 2006

In this paper we have discussed different possible orthogonalities in matrices, namely orthogonal, quasi-orthogonal, semi-orthogonal and non-orthogonal matrices including completely positive matrices, while giving some of their constructions besides studying some of their properties.
A Polynomial Time Nilpotence Test for Galois Groups and Related Results
Venue: arXiv cs.CC 2006
Year: 2006

We give a deterministic polynomial-time algorithm to check whether the Galois group $\Gal{f}$ of an input polynomial $f(X) \in \Q[X]$ is nilpotent: the running time is polynomial in $\size{f}$. Also, we generalize the Landau-Miller solvability test to an algorithm that tests if $\Gal{f}$ is in $Γ_d$: this algorithm runs in time polynomial in $\size{f}$ and $n^d$ and, moreover, if $\Gal{f}\inΓ_d$ it computes all the prime factors of $# \Gal{f}$.
From Proof Nets to the Free *-Autonomous Category
Venue: arXiv cs.LO 2006
Year: 2006

In the first part of this paper we present a theory of proof nets for full multiplicative linear logic, including the two units. It naturally extends the well-known theory of unit-free multiplicative proof nets. A linking is no longer a set of axiom links but a tree in which the axiom links are subtrees. These trees will be identified according to an equivalence relation based on a simple form of graph rewriting. We show the standard results of sequentialization and strong normalization of cut elimination. In the second part of the paper we show that the identifications enforced on proofs are such that the class of two-conclusion proof nets defines the free *-autonomous category.
SLA-Based Coordinated Superscheduling Scheme and Performance for Computational Grids
Venue: arXiv cs.DC 2006
Year: 2006

The Service Level Agreement~(SLA) based grid superscheduling approach promotes coordinated resource sharing. Superscheduling is facilitated between administratively and topologically distributed grid sites by grid schedulers such as Resource brokers. In this work, we present a market-based SLA coordination mechanism. We based our SLA model on a well known \emph{contract net protocol}. The key advantages of our approach are that it allows:~(i) resource owners to have finer degree of control over the resource allocation that was previously not possible through traditional mechanism; and (ii) superschedulers to bid for SLA contracts in the contract net with focus on completing the job within the user specified deadline. In this work, we use simulation to show the effectiveness of our proposed approach.
An Electronic Payment System to Ensure Cost Effectiveness with Easy Security Incorporation for the Developing Countries
Venue: arXiv cs.OH 2006
Year: 2006

With the rapid growth of Information and Communication Technology, Electronic commerce is now acting as a new means of carrying out business transactions through electronic means such as Internet environment. To avoid the complexities associated with the digital cash and electronic cash, consumers and vendors are looking for credit card payments on the Internet as one possible time-tested alternative. This gave rise of the on-line payment processing using a third-party verification; which is not suitable for the developing countries in most of the cases because of the excessive costs associated with it for maintenance and establishment of an online third-party processor. As a remedy of this problem, in this paper, we have proposed a framework for easy security incorporation in credit card based electronic payment system without the use of an on-line third- party processor; which tends to be low cost and effective for the developing countries.
Universal Filtering via Hidden Markov Modeling
Venue: arXiv cs.IT 2006
Year: 2006

The problem of discrete universal filtering, in which the components of a discrete signal emitted by an unknown source and corrupted by a known DMC are to be causally estimated, is considered. A family of filters are derived, and are shown to be universally asymptotically optimal in the sense of achieving the optimum filtering performance when the clean signal is stationary, ergodic, and satisfies an additional mild positivity condition. Our schemes are comprised of approximating the noisy signal using a hidden Markov process (HMP) via maximum-likelihood (ML) estimation, followed by the use of the forward recursions for HMP state estimation. It is shown that as the data length increases, and as the number of states in the HMP approximation increases, our family of filters attain the performance of the optimal distribution-dependent filter.
Aligned Virtual Coordinates for Greedy Routing in WSNs
Venue: arXiv cs.NI 2006
Year: 2006

Geographic routing provides relatively good performance at a much lower overhead than conventional routing protocols such as AODV. However, the performance of these protocols is impacted by physical voids, and localization errors. Accordingly, virtual coordinate systems (VCS) were proposed as an alternative approach that is resilient to localization errors and that naturally routes around physical voids. However, we show that VCS is vulnerable to different forms of the void problem and the performance of greedy routing on VCS is worse than that of geographic forwarding. We show that these anomalies are due to the integral nature of VCS, which causes quantization noise in the estimate of connectivity and node location. We propose an aligned virtual coordinate system (AVCS) on which the greedy routing success can be significantly improved. With our approach, and for the first time, we show that greedy routing on VCS out-performs that on physical coordinate systems even in the absence of localization errors. We compare AVCS against some of the most popular geographical routing protocols both on physical coordinate system and the virtual coordinate systems and show that AVCS significantly improves performance over the best known solutions.
Oblivious Transfer using Elliptic Curves
Venue: arXiv cs.CR 2006
Year: 2006

This paper proposes an algorithm for oblivious transfer using elliptic curves. Also, we present its application to chosen one-out-of-two oblivious transfer.
Power-aware scheduling for makespan and flow
Venue: arXiv cs.DS 2006
Year: 2006

We consider offline scheduling algorithms that incorporate speed scaling to address the bicriteria problem of minimizing energy consumption and a scheduling metric. For makespan, we give linear-time algorithms to compute all non-dominated solutions for the general uniprocessor problem and for the multiprocessor problem when every job requires the same amount of work. We also show that the multiprocessor problem becomes NP-hard when jobs can require different amounts of work. For total flow, we show that the optimal flow corresponding to a particular energy budget cannot be exactly computed on a machine supporting arithmetic and the extraction of roots. This hardness result holds even when scheduling equal-work jobs on a uniprocessor. We do, however, extend previous work by Pruhs et al. to give an arbitrarily-good approximation for scheduling equal-work jobs on a multiprocessor.