OpenRaiser/Intern-Atlas huggingface dataset:
The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case
Venue: arXiv cs.LO 2006
Year: 2006

The constraint satisfaction probem (CSP) is a well-acknowledged framework in which many combinatorial search problems can be naturally formulated. The CSP may be viewed as the problem of deciding the truth of a logical sentence consisting of a conjunction of constraints, in front of which all variables are existentially quantified. The quantified constraint satisfaction problem (QCSP) is the generalization of the CSP where universal quantification is permitted in addition to existential quantification. The general intractability of these problems has motivated research studying the complexity of these problems under a restricted constraint language, which is a set of relations that can be used to express constraints. This paper introduces collapsibility, a technique for deriving positive complexity results on the QCSP. In particular, this technique allows one to show that, for a particular constraint language, the QCSP reduces to the CSP. We show that collapsibility applies to three known tractable cases of the QCSP that were originally studied using disparate proof techniques in different decades: Quantified 2-SAT (Aspvall, Plass, and Tarjan 1979), Quantified Horn-SAT (Karpinski, Kleine Büning, and Schmitt 1987), and Quantified Affine-SAT (Creignou, Khanna, and Sudan 2001). This reconciles and reveals common structure among these cases, which are describable by constraint languages over a two-element domain. In addition to unifying these known tractable cases, we study constraint languages over domains of larger size.
Object-Based Groupware: Theory, Design and Implementation Issues
Venue: arXiv cs.SE 2006
Year: 2006

Document management software systems are having a wide audience at present. However, groupware as a term has a wide variety of possible definitions. Groupware classification attempt is made in this paper. Possible approaches to groupware are considered including document management, document control and mailing systems. Lattice theory and concept modelling are presented as a theoretical background for the systems in question. Current technologies in state-of-the-art document managenent software are discussed. Design and implementation aspects for user-friendly integrate enterprise systems are described. Results for a real system to be implemented are given. Perspectives of the field in question are discussed.
Integrating Enterprise Software Applications with Web Portal Technology
Venue: arXiv cs.SE 2006
Year: 2006

Web-portal based approach can significantly improve the entire corporate information infrastructure. The approach proposed provides for rapid and accurate front-end integration of heterogeneous corporate applications including enterprise resource planning (ERP) systems. Human resources ERP component and multimedia data warehouse implementations are discussed as essential instances.
Leading strategies in competitive on-line prediction
Venue: arXiv cs.LG 2006
Year: 2006

We start from a simple asymptotic result for the problem of on-line regression with the quadratic loss function: the class of continuous limited-memory prediction strategies admits a "leading prediction strategy", which not only asymptotically performs at least as well as any continuous limited-memory strategy but also satisfies the property that the excess loss of any continuous limited-memory strategy is determined by how closely it imitates the leading strategy. More specifically, for any class of prediction strategies constituting a reproducing kernel Hilbert space we construct a leading strategy, in the sense that the loss of any prediction strategy whose norm is not too large is determined by how closely it imitates the leading strategy. This result is extended to the loss functions given by Bregman divergences and by strictly proper scoring rules.
A polynomial-time approximation algorithm for the number of k-matchings in bipartite graphs
Venue: arXiv cs.CC 2006
Year: 2006

We show that the number of $k$-matching in a given undirected graph $G$ is equal to the number of perfect matching of the corresponding graph $G_k$ on an even number of vertices divided by a suitable factor. If $G$ is bipartite then one can construct a bipartite $G_k$. For bipartite graphs this result implies that the number of $k$-matching has a polynomial-time approximation algorithm. The above results are extended to permanents and hafnians of corresponding matrices.
Levels of Product Differentiation in the Global Mobile Phones Market
Venue: arXiv cs.OH 2006
Year: 2006

The sixth product level called compliant product is a connecting element between the physical product characteristics and the strategy of the producer company. The article discusses the differentiation among the product offers of companies working in the global markets, as well as the strategies which they use and could use in that respect.
Relation Variables in Qualitative Spatial Reasoning
Venue: arXiv cs.AI 2006
Year: 2006

We study an alternative to the prevailing approach to modelling qualitative spatial reasoning (QSR) problems as constraint satisfaction problems. In the standard approach, a relation between objects is a constraint whereas in the alternative approach it is a variable. The relation-variable approach greatly simplifies integration and implementation of QSR. To substantiate this point, we discuss several QSR algorithms from the literature which in the relation-variable approach reduce to the customary constraint propagation algorithm enforcing generalised arc-consistency.
Quasi-friendly sup-interpretations
Venue: arXiv cs.CC 2006
Year: 2006

In a previous paper, the sup-interpretation method was proposed as a new tool to control memory resources of first order functional programs with pattern matching by static analysis. Basically, a sup-interpretation provides an upper bound on the size of function outputs. In this former work, a criterion, which can be applied to terminating as well as non-terminating programs, was developed in order to bound polynomially the stack frame size. In this paper, we suggest a new criterion which captures more algorithms computing values polynomially bounded in the size of the inputs. Since this work is related to quasi-interpretations, we compare the two notions obtaining two main features. The first one is that, given a program, we have heuristics for finding a sup-interpretation when we consider polynomials of bounded degree. The other one consists in the characterizations of the set of function computable in polynomial time and in polynomial space.
Cryptanalysis of an Encryption Scheme Based on Blind Source Separation
Venue: arXiv cs.CR 2006
Year: 2006

Recently Lin et al. proposed a method of using the underdetermined BSS (blind source separation) problem to realize image and speech encryption. In this paper, we give a cryptanalysis of this BSS-based encryption and point out that it is not secure against known/chosen-plaintext attack and chosen-ciphertext attack. In addition, there exist some other security defects: low sensitivity to part of the key and the plaintext, a ciphertext-only differential attack, divide-and-conquer (DAC) attack on part of the key. We also discuss the role of BSS in Lin et al.'s efforts towards cryptographically secure ciphers.
Reversal Complexity Revisited
Venue: arXiv cs.CC 2006
Year: 2006

We study a generalized version of reversal bounded Turing machines where, apart from several tapes on which the number of head reversals is bounded by r(n), there are several further tapes on which head reversals remain unrestricted, but size is bounded by s(n). Recently, such machines were introduced as a formalization of a computation model that restricts random access to external memory and internal memory space. Here, each of the tapes with a restriction on the head reversals corresponds to an external memory device, and the tapes of restricted size model internal memory. We use ST(r(n),s(n),O(1)) to denote the class of all problems that can be solved by deterministic Turing machines that comply to the above resource bounds. Similarly, NST and RST, respectively, are used for the corresponding nondeterministic and randomized classes. While previous papers focused on lower bounds for particular problems, including sorting, the set equality problem, and several query evaluation problems, the present paper addresses the relations between the (R,N)ST-classes and classical complexity classes and investigates the structural complexity of the (R,N)ST-classes. Our main results are (1) a trade-off between internal memory space and external memory head reversals, (2) correspondences between the (R,N)ST-classes and ``classical'' time-bounded, space-bounded, reversal-bounded, and circuit complexity classes, and (3) hierarchies of (R)ST-classes in terms of increasing numbers of head reversals on external memory tapes.
The weak pigeonhole principle for function classes in S^1_2
Venue: arXiv cs.LO 2006
Year: 2006

It is well known that S^1_2 cannot prove the injective weak pigeonhole principle for polynomial time functions unless RSA is insecure. In this note we investigate the provability of the surjective (dual) weak pigeonhole principle in S^1_2 for provably weaker function classes.
MDS Ideal Secret Sharing Scheme from AG-codes on Elliptic Curves
Venue: arXiv cs.CR 2006
Year: 2006

For a secret sharing scheme, two parameters $d_{min}$ and $d_{cheat}$ are defined in [12] and [13]. These two parameters measure the error-correcting capability and the secret-recovering capability of the secret sharing scheme against cheaters. Some general properties of the parameters have been studied in [12,[9] and [13]. The MDS secret-sharing scheme was defined in [12] and it is proved that MDS perfect secret sharing scheme can be constructed for any monotone access structure. The famous Shamir $(k,n)$ threshold secret sharing scheme is the MDS with $d_{min}=d_{cheat}=n-k+1$. In [3] we proposed the linear secret sharing scheme from algebraic-geometric codes. In this paper the linear secret sharing scheme from AG-codes on elliptic curves is studied and it is shown that many of them are MDS linear secret sharing scheme.
Combinatorial and Arithmetical Properties of Infinite Words Associated with Non-simple Quadratic Parry Numbers
Venue: arXiv cs.DM 2006
Year: 2006

We study arithmetical and combinatorial properties of $β$-integers for $β$ being the root of the equation $x^2=mx-n, m,n \in \mathbb N, m \geq n+2\geq 3$. We determine with the accuracy of $\pm 1$ the maximal number of $β$-fractional positions, which may arise as a result of addition of two $β$-integers. For the infinite word $u_β$ coding distances between consecutive $β$-integers, we determine precisely also the balance. The word $u_β$ is the fixed point of the morphism $A \to A^{m-1}B$ and $B\to A^{m-n-1}B$. In the case $n=1$ the corresponding infinite word $u_β$ is sturmian and therefore 1-balanced. On the simplest non-sturmian example with $n\geq 2$, we illustrate how closely the balance and arithmetical properties of $β$-integers are related.
The Aligned-Coordinated Geographical Routing for Multihop Wireless Networks
Venue: arXiv cs.NI 2006
Year: 2006

The stateless, low overhead and distributed nature of the Geographic routing protocols attract a lot of research attentions recently. Since the geographic routing would face void problems, leading to complementary routing such as perimeter routing which degrades the performance of geographic routing, most research works are focus on optimizing this complementary part of geographic routing to improve it. The greedy forwarding part of geographic routing provides an optimal routing performance in terms of path stretch. If the geographic routing could adapt the greedy forwarding more, its performance would be enhanced much more than to optimize the complementary routing such as perimeter routings. Our work is the first time to do so. The aligned physical coordinate is used to do the greedy forwarding routing decision which would lead more greedy forwarding. We evaluate our design to most geographic routing protocols, showing it helps much and maintain the stateless nature of geographic routing.
Radial Structure of the Internet
Venue: arXiv cs.NI 2006
Year: 2006

The structure of the Internet at the Autonomous System (AS) level has been studied by both the Physics and Computer Science communities. We extend this work to include features of the core and the periphery, taking a radial perspective on AS network structure. New methods for plotting AS data are described, and they are used to analyze data sets that have been extended to contain edges missing from earlier collections. In particular, the average distance from one vertex to the rest of the network is used as the baseline metric for investigating radial structure. Common vertex-specific quantities are plotted against this metric to reveal distinctive characteristics of central and peripheral vertices. Two data sets are analyzed using these measures as well as two common generative models (Barabasi-Albert and Inet). We find a clear distinction between the highly connected core and a sparse periphery. We also find that the periphery has a more complex structure than that predicted by degree distribution or the two generative models.
On-line topological simplification of weighted graphs
Venue: arXiv cs.DS 2006
Year: 2006

We describe two efficient on-line algorithms to simplify weighted graphs by eliminating degree-two vertices. Our algorithms are on-line in that they react to updates on the data, keeping the simplification up-to-date. The supported updates are insertions of vertices and edges; hence, our algorithms are partially dynamic. We provide both analytical and empirical evaluations of the efficiency of our approaches. Specifically, we prove an O(log n) upper bound on the amortized time complexity of our maintenance algorithms, with n the number of insertions.
Cross Entropy Approximation of Structured Covariance Matrices
Venue: arXiv cs.IT 2006
Year: 2006

We apply two variations of the principle of Minimum Cross Entropy (the Kullback information measure) to fit parameterized probability density models to observed data densities. For an array beamforming problem with P incident narrowband point sources, N > P sensors, and colored noise, both approaches yield eigenvector fitting methods similar to that of the MUSIC algorithm[1]. Furthermore, the corresponding cross-entropies are related to the MDL model order selection criterion[2].
Combining typing and size constraints for checking the termination of higher-order conditional rewrite systems
Venue: arXiv cs.LO 2006
Year: 2006

In a previous work, the first author extended to higher-order rewriting and dependent types the use of size annotations in types, a termination proof technique called type or size based termination and initially developed for ML-like programs. Here, we go one step further by considering conditional rewriting and explicit quantifications and constraints on size annotations. This allows to describe more precisely how the size of the output of a function depends on the size of its inputs. Hence, we can check the termination of more functions. We first give a general type-checking algorithm based on constraint solving. Then, we give a termination criterion with constraints in Presburger arithmetic. To our knowledge, this is the first termination criterion for higher-order conditional rewriting taking into account the conditions in termination.
ANAP: Anonymous Authentication Protocol in Mobile Ad hoc Networks
Venue: arXiv cs.CR 2006
Year: 2006

The pervasiveness of wireless communication recently gave mobile ad hoc networks (MANET) a significant researchers' attention, due to its innate capabilities of instant communication in many time and mission critical applications. However, its natural advantages of networking in civilian and military environments make them vulnerable to security threats. Support for an anonymity in MANET is an orthogonal to security critical challenge we faced in this paper. We propose a new anonymous authentication protocol for mobile ad hoc networks enhanced with a distributed reputation system. The main its objective is to provide mechanisms concealing a real identity of communicating nodes with an ability of resist to known attacks. The distributed reputation system is incorporated for a trust management and malicious behavior detection in the network. The end-to-end anonymous authentication is conducted in three-pass handshake based on an asymmetric and symmetric key cryptography. After successfully finished authentication phase secure and multiple anonymous data channels are established. The anonymity is guarantied by randomly chosen pseudonyms owned by a user. Nodes of the network are publicly identified and are independent of users' pseudonyms. In this paper we presented an example of the protocol implementation.
Bilayer Low-Density Parity-Check Codes for Decode-and-Forward in Relay Channels
Venue: arXiv cs.IT 2006
Year: 2006

This paper describes an efficient implementation of binning for the relay channel using low-density parity-check (LDPC) codes. We devise bilayer LDPC codes to approach the theoretically promised rate of the decode-and-forward relaying strategy by incorporating relay-generated information bits in specially designed bilayer graphical code structures. While conventional LDPC codes are sensitively tuned to operate efficiently at a certain channel parameter, the proposed bilayer LDPC codes are capable of working at two different channel parameters and two different rates: that at the relay and at the destination. To analyze the performance of bilayer LDPC codes, bilayer density evolution is devised as an extension of the standard density evolution algorithm. Based on bilayer density evolution, a design methodology is developed for the bilayer codes in which the degree distribution is iteratively improved using linear programming. Further, in order to approach the theoretical decode-and-forward rate for a wide range of channel parameters, this paper proposes two different forms bilayer codes, the bilayer-expurgated and bilayer-lengthened codes. It is demonstrated that a properly designed bilayer LDPC code can achieve an asymptotic infinite-length threshold within 0.24 dB gap to the Shannon limits of two different channels simultaneously for a wide range of channel parameters. By practical code construction, finite-length bilayer codes are shown to be able to approach within a 0.6 dB gap to the theoretical decode-and-forward rate of the relay channel at a block length of $10^5$ and a bit-error probability (BER) of $10^{-4}$. Finally, it is demonstrated that a generalized version of the proposed bilayer code construction is applicable to relay networks with multiple relays.
Fast algorithms for computing isogenies between elliptic curves
Venue: arXiv cs.CC 2006
Year: 2006

We survey algorithms for computing isogenies between elliptic curves defined over a field of characteristic either 0 or a large prime. We introduce a new algorithm that computes an isogeny of degree $\ell$ ($\ell$ different from the characteristic) in time quasi-linear with respect to $\ell$. This is based in particular on fast algorithms for power series expansion of the Weierstrass $\wp$-function and related functions.
Dichotomies and Duality in First-order Model Checking Problems
Venue: arXiv cs.LO 2006
Year: 2006

We study the complexity of the model checking problem, for fixed model A, over certain fragments L of first-order logic. These are sometimes known as the expression complexities of L. We obtain various complexity classification theorems for these logics L as each ranges over models A, in the spirit of the dichotomy conjecture for the Constraint Satisfaction Problem -- which itself may be seen as the model checking problem for existential conjunctive positive first-order logic.
A Case for Peering of Content Delivery Networks
Venue: arXiv cs.DC 2006
Year: 2006

The proliferation of Content Delivery Networks (CDN) reveals that existing content networks are owned and operated by individual companies. As a consequence, closed delivery networks are evolved which do not cooperate with other CDNs and in practice, islands of CDNs are formed. Moreover, the logical separation between contents and services in this context results in two content networking domains. But present trends in content networks and content networking capabilities give rise to the interest in interconnecting content networks. Finding ways for distinct content networks to coordinate and cooperate with other content networks is necessary for better overall service. In addition to that, meeting the QoS requirements of users according to the negotiated Service Level Agreements between the user and the content network is a burning issue in this perspective. In this article, we present an open, scalable and Service-Oriented Architecture based system to assist the creation of open Content and Service Delivery Networks (CSDN) that scale and support sharing of resources with other CSDNs.
Challenging the principle of compositionality in interpreting natural language texts
Venue: arXiv cs.CL 2006
Year: 2006

The paper aims at emphasizing that, even relaxed, the hypothesis of compositionality has to face many problems when used for interpreting natural language texts. Rather than fixing these problems within the compositional framework, we believe that a more radical change is necessary, and propose another approach.
Navigating multilingual news collections using automatically extracted information
Venue: arXiv cs.CL 2006
Year: 2006

We are presenting a text analysis tool set that allows analysts in various fields to sieve through large collections of multilingual news items quickly and to find information that is of relevance to them. For a given document collection, the tool set automatically clusters the texts into groups of similar articles, extracts names of places, people and organisations, lists the user-defined specialist terms found, links clusters and entities, and generates hyperlinks. Through its daily news analysis operating on thousands of articles per day, the tool also learns relationships between people and other entities. The fully functional prototype system allows users to explore and navigate multilingual document collections across languages and time.
The JRC-Acquis: A multilingual aligned parallel corpus with 20+ languages
Venue: arXiv cs.CL 2006
Year: 2006

We present a new, unique and freely available parallel corpus containing European Union (EU) documents of mostly legal nature. It is available in all 20 official EUanguages, with additional documents being available in the languages of the EU candidate countries. The corpus consists of almost 8,000 documents per language, with an average size of nearly 9 million words per language. Pair-wise paragraph alignment information produced by two different aligners (Vanilla and HunAlign) is available for all 190+ language pair combinations. Most texts have been manually classified according to the EUROVOC subject domains so that the collection can also be used to train and test multi-label classification algorithms and keyword-assignment software. The corpus is encoded in XML, according to the Text Encoding Initiative Guidelines. Due to the large number of parallel texts in many languages, the JRC-Acquis is particularly suitable to carry out all types of cross-language research, as well as to test and benchmark text analysis software across different languages (for instance for alignment, sentence splitting and term extraction).