OpenRaiser/Intern-Atlas huggingface dataset:
A Local Tree Structure is NOT Sufficient for the Local Optimality of Message-Passing Decoding in Low Density Parity Check Codes
Venue: arXiv cs.IT 2007
Year: 2007

We address the problem,`Is a local tree structure sufficient for the local optimality of message passing algorithm in low density parity check codes?'.It is shown that the answer is negative. Using this observation, we pinpoint a flaw in the proof of Theorem 1 in the paper `The Capacity of Low-Density Parity-Check Codes Under Message-Passing Decoding' by Thomas J. Richardson and Rüdiger L.Urbanke\cite{RUCapacity}. We further provide a new proof of that theorem based on a different argument.
Bistable Biorders: A Sequential Domain Theory
Venue: arXiv cs.PL 2007
Year: 2007

We give a simple order-theoretic construction of a Cartesian closed category of sequential functions. It is based on bistable biorders, which are sets with a partial order -- the extensional order -- and a bistable coherence, which captures equivalence of program behaviour, up to permutation of top (error) and bottom (divergence). We show that monotone and bistable functions (which are required to preserve bistably bounded meets and joins) are strongly sequential, and use this fact to prove universality results for the bistable biorder semantics of the simply-typed lambda-calculus (with atomic constants), and an extension with arithmetic and recursion. We also construct a bistable model of SPCF, a higher-order functional programming language with non-local control. We use our universality result for the lambda-calculus to show that the semantics of SPCF is fully abstract. We then establish a direct correspondence between bistable functions and sequential algorithms by showing that sequential data structures give rise to bistable biorders, and that each bistable function between such biorders is computed by a sequential algorithm.
How Overlap Determines the Macronuclear Genes in Ciliates
Venue: arXiv cs.LO 2007
Year: 2007

Formal models for gene assembly in ciliates have been developed, in particular the string pointer reduction system (SPRS) and the graph pointer reduction system (GPRS). The reduction graph is a valuable tool within the SPRS, revealing much information about how gene assembly is performed for a given gene. The GPRS is more abstract than the SPRS and not all information present in the SPRS is retained in the GPRS. As a consequence the reduction graph cannot be defined for the GPRS in general, but we show that it can be defined (in an equivalent manner as defined for the SPRS) if we restrict ourselves to so-called realistic overlap graphs. Fortunately, only these graphs correspond to genes occurring in nature. Defining the reduction graph within the GPRS allows one to carry over several results within the SPRS that rely on the reduction graph.
Numerical Model For Vibration Damping Resulting From the First Order Phase Transformations
Venue: arXiv cs.CE 2007
Year: 2007

A numerical model is constructed for modelling macroscale damping effects induced by the first order martensite phase transformations in a shape memory alloy rod. The model is constructed on the basis of the modified Landau-Ginzburg theory that couples nonlinear mechanical and thermal fields. The free energy function for the model is constructed as a double well function at low temperature, such that the external energy can be absorbed during the phase transformation and converted into thermal form. The Chebyshev spectral methods are employed together with backward differentiation for the numerical analysis of the problem. Computational experiments performed for different vibration energies demonstrate the importance of taking into account damping effects induced by phase transformations.
Strategies in object-oriented design
Venue: arXiv cs.HC 2007
Year: 2007

This paper presents a study aiming to analyse the design strategies of experts in object-oriented programming. We report an experiment conducted with four experts. Each subject solved three problems. Our results show that three strategies may be used in program design according to the solution structure. An object-centred strategy and a function-centred strategy are used when the solution has a hierarchical structure with vertical communication between objects. In this case, the plan which guides the design activity is declarative. A procedure-centred strategy is used when the solution has a flat structure with horizontal communication between objects. In this case, the plan which guides the design activity is procedural. These results are discussed in relation with results on design strategies in procedural design. Furthermore, our results provide insight into the knowledge structures of experts in object-oriented design. To conclude, we point out limitations of this study and discuss implications of our results for Human-Computer Interaction systems, in particular for systems assisting experts in their design activity.
Counting preimages of TCP reordering patterns
Venue: arXiv cs.DS 2007
Year: 2007

Packet reordering is an important property of network traffic that should be captured by analytical models of the Transmission Control Protocol (TCP). We study a combinatorial problem motivated by RESTORED, a TCP modeling methodology that incorporates information about packet dynamics. A significant component of this model is a many-to-one mapping B that transforms sequences of packet IDs into buffer sequences, in a manner that is compatible with TCP semantics. We show that the following hold: 1. There exists a linear time algorithm that, given a buffer sequence W of length n, decides whether there exists a permutation A of 1,2,..., n such that $A\in B^{-1}(W)$ (and constructs such a permutation, when it exists). 2. The problem of counting the number of permutations in $B^{-1}(W)$ has a polynomial time algorithm. We also show how to extend these results to sequences of IDs that contain repeated packets.
Computing a Minimum-Dilation Spanning Tree is NP-hard
Venue: arXiv cs.CG 2007
Year: 2007

In a geometric network G = (S, E), the graph distance between two vertices u, v in S is the length of the shortest path in G connecting u to v. The dilation of G is the maximum factor by which the graph distance of a pair of vertices differs from their Euclidean distance. We show that given a set S of n points with integer coordinates in the plane and a rational dilation delta > 1, it is NP-hard to determine whether a spanning tree of S with dilation at most delta exists.
FPRAS for computing a lower bound for weighted matching polynomial of graphs
Venue: arXiv cs.CC 2007
Year: 2007

We give a fully polynomial randomized approximation scheme to compute a lower bound for the matching polynomial of any weighted graph at a positive argument. For the matching polynomial of complete bipartite graphs with bounded weights these lower bounds are asymptotically optimal.
Recommender System for Online Dating Service
Venue: arXiv cs.IR 2007
Year: 2007

Users of online dating sites are facing information overload that requires them to manually construct queries and browse huge amount of matching user profiles. This becomes even more problematic for multimedia profiles. Although matchmaking is frequently cited as a typical application for recommender systems, there is a surprising lack of work published in this area. In this paper we describe a recommender system we implemented and perform a quantitative comparison of two collaborative filtering (CF) and two global algorithms. Results show that collaborative filtering recommenders significantly outperform global algorithms that are currently used by dating sites. A blind experiment with real users also confirmed that users prefer CF based recommendations to global popularity recommendations. Recommender systems show a great potential for online dating where they could improve the value of the service to users and improve monetization of the service.
Algorithm of Segment-Syllabic Synthesis in Speech Recognition Problem
Venue: arXiv cs.SD 2007
Year: 2007

Speech recognition based on the syllable segment is discussed in this paper. The principal search methods in space of states for the speech recognition problem by segment-syllabic parameters trajectory synthesis are investigated. Recognition as comparison the parameters trajectories in chosen speech units on the sections of the segmented speech is realized. Some experimental results are given and discussed.
On The Capacity Deficit of Mobile Wireless Ad Hoc Networks: A Rate Distortion Formulation
Venue: arXiv cs.IT 2007
Year: 2007

Overheads incurred by routing protocols diminish the capacity available for relaying useful data in a mobile wireless ad hoc network. Discovering lower bounds on the amount of protocol overhead incurred for routing data packets is important for the development of efficient routing protocols, and for characterizing the actual (effective) capacity available for network users. This paper presents an information-theoretic framework for characterizing the minimum routing overheads of geographic routing in a network with mobile nodes. specifically, the minimum overhead problem is formulated as a rate-distortion problem. The formulation may be applied to networks with arbitrary traffic arrival and location service schemes. Lower bounds are derived for the minimum overheads incurred for maintaining the location of destination nodes and consistent neighborhood information in terms of node mobility and packet arrival process. This leads to a characterization of the deficit caused by the routing overheads on the overall transport capacity.
An ExpTime Procedure for Description Logic $\mathcal{ALCQI}$ (Draft)
Venue: arXiv cs.LO 2007
Year: 2007

A worst-case ExpTime tableau-based decision procedure is outlined for the satisfiability problem in $\mathcal{ALCQI}$ w.r.t. general axioms.
On the densest MIMO lattices from cyclic division algebras
Venue: arXiv cs.IT 2007
Year: 2007

It is shown why the discriminant of a maximal order within a cyclic division algebra must be minimized in order to get the densest possible matrix lattices with a prescribed nonvanishing minimum determinant. Using results from class field theory a lower bound to the minimum discriminant of a maximal order with a given center and index (= the number of Tx/Rx antennas) is derived. Also numerous examples of division algebras achieving our bound are given. E.g. we construct a matrix lattice with QAM coefficients that has 2.5 times as many codewords as the celebrated Golden code of the same minimum determinant. We describe a general algorithm due to Ivanyos and Ronyai for finding maximal orders within a cyclic division algebra and discuss our enhancements to this algorithm. We also consider general methods for finding cyclic division algebras of a prescribed index achieving our lower bound.
Extraction of cartographic objects in high resolution satellite images for object model generation
Venue: arXiv cs.CV 2007
Year: 2007

The aim of this study is to detect man-made cartographic objects in high-resolution satellite images. New generation satellites offer a sub-metric spatial resolution, in which it is possible (and necessary) to develop methods at object level rather than at pixel level, and to exploit structural features of objects. With this aim, a method to generate structural object models from manually segmented images has been developed. To generate the model from non-segmented images, extraction of the objects from the sample images is required. A hybrid method of extraction (both in terms of input sources and segmentation algorithms) is proposed: A region based segmentation is applied on a 10 meter resolution multi-spectral image. The result is used as marker in a "marker-controlled watershed method using edges" on a 2.5 meter resolution panchromatic image. Very promising results have been obtained even on images where the limits of the target objects are not apparent.
Convergence and Optimal Buffer Sizing for Window Based AIMD Congestion Control
Venue: arXiv cs.NI 2007
Year: 2007

We study the interaction between the AIMD (Additive Increase Multiplicative Decrease) congestion control and a bottleneck router with Drop Tail buffer. We consider the problem in the framework of deterministic hybrid models. First, we show that the hybrid model of the interaction between the AIMD congestion control and bottleneck router always converges to a cyclic behavior. We characterize the cycles. Necessary and sufficient conditions for the absence of multiple jumps of congestion window in the same cycle are obtained. Then, we propose an analytical framework for the optimal choice of the router buffer size. We formulate the problem of the optimal router buffer size as a multi-criteria optimization problem, in which the Lagrange function corresponds to a linear combination of the average goodput and the average delay in the queue. The solution to the optimization problem provides further evidence that the buffer size should be reduced in the presence of traffic aggregation. Our analytical results are confirmed by simulations performed with Simulink and the NS simulator.
Target assignment for robotic networks: asymptotic performance under limited communication
Venue: arXiv cs.RO 2007
Year: 2007

We are given an equal number of mobile robotic agents, and distinct target locations. Each agent has simple integrator dynamics, a limited communication range, and knowledge of the position of every target. We address the problem of designing a distributed algorithm that allows the group of agents to divide the targets among themselves and, simultaneously, leads each agent to reach its unique target. We do not require connectivity of the communication graph at any time. We introduce a novel assignment-based algorithm with the following features: initial assignments and robot motions follow a greedy rule, and distributed refinements of the assignment exploit an implicit circular ordering of the targets. We prove correctness of the algorithm, and give worst-case asymptotic bounds on the time to complete the assignment as the environment grows with the number of agents. We show that among a certain class of distributed algorithms, our algorithm is asymptotically optimal. The analysis utilizes results on the Euclidean traveling salesperson problem.
Option Valuation using Fourier Space Time Stepping
Venue: arXiv cs.CE 2007
Year: 2007

It is well known that the Black-Scholes-Merton model suffers from several deficiencies. Jump-diffusion and Levy models have been widely used to partially alleviate some of the biases inherent in this classical model. Unfortunately, the resulting pricing problem requires solving a more difficult partial-integro differential equation (PIDE) and although several approaches for solving the PIDE have been suggested in the literature, none are entirely satisfactory. All treat the integral and diffusive terms asymmetrically and are difficult to extend to higher dimensions. We present a new, efficient algorithm, based on transform methods, which symmetrically treats the diffusive and integrals terms, is applicable to a wide class of path-dependent options (such as Bermudan, barrier, and shout options) and options on multiple assets, and naturally extends to regime-switching Levy models. We present a concise study of the precision and convergence properties of our algorithm for several classes of options and Levy models and demonstrate that the algorithm is second-order in space and first-order in time for path-dependent options.
Portlet Wrappers using JavaScript
Venue: arXiv cs.SE 2007
Year: 2007

In this paper we extend the classical portal (with static portlets) design with HTML DOM Web clipping on the client browser using dynamic JavaScript portlets: the portal server supplies the user/passwords for all services through https and the client browser retrieves web pages and cuts/selects/changes the desired parts using paths (XPath) in the Web page structure. This operation brings along a set of advantages: dynamic wrapping of existing legacy websites in the client browser, the reloading of only changed portlets instead of whole portal, low bandwidth on the server, the elimination of re-writing the URL links in the portal, and last but not least, a support for Java applets in portlets by putting the login cookies on the client browser. Our solution is compliant with JSR168 Portlet Specification allowing portability across all vendor platforms.
Automatic Annotation of XHTML Pages with Audio Components
Venue: arXiv cs.OH 2007
Year: 2007

In this paper we present Deiush, a multimodal system for browsing hypertext Web documents. The Deiush system is based on our novel approach to automatically annotate hypertext Web documents (i.e. XHTML pages) with browsable audio components. It combines two key technologies: (1) middleware automatic separation of Web documents through structural and semantic analysis which is annotated with audio components, transforming them into XHTML+VoiceXML format to represent multimodal dialog; and (2) Opera Browser, an already standardized browser which we adopt as an interface of the XHTML+VoiceXML output of annotating. This paper describes the annotation technology of Deiush and presents an initial system evaluation.
Automata with Nested Pebbles Capture First-Order Logic with Transitive Closure
Venue: arXiv cs.LO 2007
Year: 2007

String languages recognizable in (deterministic) log-space are characterized either by two-way (deterministic) multi-head automata, or following Immerman, by first-order logic with (deterministic) transitive closure. Here we elaborate this result, and match the number of heads to the arity of the transitive closure. More precisely, first-order logic with k-ary deterministic transitive closure has the same power as deterministic automata walking on their input with k heads, additionally using a finite set of nested pebbles. This result is valid for strings, ordered trees, and in general for families of graphs having a fixed automaton that can be used to traverse the nodes of each of the graphs in the family. Other examples of such families are grids, toruses, and rectangular mazes. For nondeterministic automata, the logic is restricted to positive occurrences of transitive closure. The special case of k=1 for trees, shows that single-head deterministic tree-walking automata with nested pebbles are characterized by first-order logic with unary deterministic transitive closure. This refines our earlier result that placed these automata between first-order and monadic second-order logic on trees.
A Technical Report On Grid Benchmarking using SEE V.O
Venue: arXiv cs.PF 2007
Year: 2007

Grids include heterogeneous resources, which are based on different hardware and software architectures or components. In correspondence with this diversity of the infrastructure, the execution time of any single job, as well as the total grid performance can both be affected substantially, which can be demonstrated by measurements. Running a simple benchmarking suite can show this heterogeneity and give us results about the differences over the grid sites.
Plot 94 in ambiance X-Window
Venue: arXiv cs.CV 2007
Year: 2007

<PLOT > is a collection of routines to draw surfaces, contours and so on. In this work we are presenting a version, that functions over work stations with the operative system UNIX, that count with the graphic ambiance X-WINDOW with the tools XLIB and OSF/MOTIF. This implant was realized for the work stations DEC 5000-200, DEC IPX, and DEC ALFA of the CINVESTAV (Center of Investigation and Advanced Studies). Also implanted in SILICON GRAPHICS of the CENAC (National Center of Calculation of the Polytechnic National Institute
Space Program Language (SPL/SQL) for the Relational Approach of the Spatial Databases
Venue: arXiv cs.DB 2007
Year: 2007

In this project we are presenting a grammar which unify the design and development of spatial databases. In order to make it, we combine nominal and spatial information, the former is represented by the relational model and latter by a modification of the same model. The modification lets to represent spatial data structures (as Quadtrees, Octrees, etc.) in a integrated way. This grammar is important because with it we can create tools to build systems that combine spatial-nominal characteristics such as Geographical Information Systems (GIS), Hypermedia Systems, Computed Aided Design Systems (CAD), and so on
On Approximating Optimal Weighted Lobbying, and Frequency of Correctness versus Average-Case Polynomial Time
Venue: arXiv cs.GT 2007
Year: 2007

We investigate issues related to two hard problems related to voting, the optimal weighted lobbying problem and the winner problem for Dodgson elections. Regarding the former, Christian et al. [CFRS06] showed that optimal lobbying is intractable in the sense of parameterized complexity. We provide an efficient greedy algorithm that achieves a logarithmic approximation ratio for this problem and even for a more general variant--optimal weighted lobbying. We prove that essentially no better approximation ratio than ours can be proven for this greedy algorithm. The problem of determining Dodgson winners is known to be complete for parallel access to NP [HHR97]. Homan and Hemaspaandra [HH06] proposed an efficient greedy heuristic for finding Dodgson winners with a guaranteed frequency of success, and their heuristic is a ``frequently self-knowingly correct algorithm.'' We prove that every distributional problem solvable in polynomial time on the average with respect to the uniform distribution has a frequently self-knowingly correct polynomial-time algorithm. Furthermore, we study some features of probability weight of correctness with respect to Procaccia and Rosenschein's junta distributions [PR07].
Polynomial time algorithm for 3-SAT. Examples of use
Venue: arXiv cs.CC 2007
Year: 2007

The algorithm checks the propositional formulas for patterns of unsatisfiability.
Approximation Algorithms for Multiprocessor Scheduling under Uncertainty
Venue: arXiv cs.DC 2007
Year: 2007

Motivated by applications in grid computing and project management, we study multiprocessor scheduling in scenarios where there is uncertainty in the successful execution of jobs when assigned to processors. We consider the problem of multiprocessor scheduling under uncertainty, in which we are given n unit-time jobs and m machines, a directed acyclic graph C giving the dependencies among the jobs, and for every job j and machine i, the probability p_{ij} of the successful completion of job j when scheduled on machine i in any given particular step. The goal of the problem is to find a schedule that minimizes the expected makespan, that is, the expected completion time of all the jobs. The problem of multiprocessor scheduling under uncertainty was introduced by Malewicz and was shown to be NP-hard even when all the jobs are independent. In this paper, we present polynomial-time approximation algorithms for the problem, for special cases of the dag C. We obtain an O(log(n))-approximation for the case of independent jobs, an O(log(m)log(n)log(n+m)/loglog(n+m))-approximation when C is a collection of disjoint chains, an O(log(m)log^2(n))-approximation when C is a collection of directed out- or in-trees, and an O(log(m)log^2(n)log(n+m)/loglog(n+m))-approximation when C is a directed forest.