OpenRaiser/Intern-Atlas huggingface dataset:
Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
Venue: arXiv cs.DS 2009
Year: 2009

We give the first polynomial-time approximation scheme (PTAS) for the Steiner forest problem on planar graphs and, more generally, on graphs of bounded genus. As a first step, we show how to build a Steiner forest spanner for such graphs. The crux of the process is a clustering procedure called prize-collecting clustering that breaks down the input instance into separate subinstances which are easier to handle; moreover, the terminals in different subinstances are far from each other. Each subinstance has a relatively inexpensive Steiner tree connecting all its terminals, and the subinstances can be solved (almost) separately. Another building block is a PTAS for Steiner forest on graphs of bounded treewidth. Surprisingly, Steiner forest is NP-hard even on graphs of treewidth 3. Therefore, our PTAS for bounded treewidth graph needs a nontrivial combination of approximation arguments and dynamic programming on the tree decomposition. We further show that Steiner forest can be solved in polynomial time for series-parallel graphs (graphs of treewidth at most two) by a novel combination of dynamic programming and minimum cut computations, completing our thorough complexity study of Steiner forest in the range of bounded treewidth graphs, planar graphs, and bounded genus graphs.
Quantifying Resource Use in Computations
Venue: arXiv cs.CC 2009
Year: 2009

It is currently not possible to quantify the resources needed to perform a computation. As a consequence, it is not possible to reliably evaluate the hardware resources needed for the application of algorithms or the running of programs. This is apparent in both computer science, for instance, in cryptanalysis, and in neuroscience, for instance, comparative neuro-anatomy. A System versus Environment game formalism is proposed based on Computability Logic that allows to define a computational work function that describes the theoretical and physical resources needed to perform any purely algorithmic computation. Within this formalism, the cost of a computation is defined as the sum of information storage over the steps of the computation. The size of the computational device, eg, the action table of a Universal Turing Machine, the number of transistors in silicon, or the number and complexity of synapses in a neural net, is explicitly included in the computational cost. The proposed cost function leads in a natural way to known computational trade-offs and can be used to estimate the computational capacity of real silicon hardware and neural nets. The theory is applied to a historical case of 56 bit DES key recovery, as an example of application to cryptanalysis. Furthermore, the relative computational capacities of human brain neurons and the C. elegans nervous system are estimated as an example of application to neural nets.
Asynchronous CDMA Systems with Random Spreading-Part I: Fundamental Limits
Venue: arXiv cs.IT 2009
Year: 2009

Spectral efficiency for asynchronous code division multiple access (CDMA) with random spreading is calculated in the large system limit allowing for arbitrary chip waveforms and frequency-flat fading. Signal to interference and noise ratios (SINRs) for suboptimal receivers, such as the linear minimum mean square error (MMSE) detectors, are derived. The approach is general and optionally allows even for statistics obtained by under-sampling the received signal. All performance measures are given as a function of the chip waveform and the delay distribution of the users in the large system limit. It turns out that synchronizing users on a chip level impairs performance for all chip waveforms with bandwidth greater than the Nyquist bandwidth, e.g., positive roll-off factors. For example, with the pulse shaping demanded in the UMTS standard, user synchronization reduces spectral efficiency up to 12% at 10 dB normalized signal-to-noise ratio. The benefits of asynchronism stem from the finding that the excess bandwidth of chip waveforms actually spans additional dimensions in signal space, if the users are de-synchronized on the chip-level. The analysis of linear MMSE detectors shows that the limiting interference effects can be decoupled both in the user domain and in the frequency domain such that the concept of the effective interference spectral density arises. This generalizes and refines Tse and Hanly's concept of effective interference. In Part II, the analysis is extended to any linear detector that admits a representation as multistage detector and guidelines for the design of low complexity multistage detectors with universal weights are provided.
Session Types at the Mirror
Venue: arXiv cs.PL 2009
Year: 2009

We (re)define session types as projections of process behaviors with respect to the communication channels they use. In this setting, we give session types a semantics based on fair testing. The outcome is a unified theory of behavioral types that shares common aspects with conversation types and that encompass features of both dyadic and multi-party session types. The point of view we provide sheds light on the nature of session types and gives us a chance to reason about them in a framework where every notion, from well-typedness to the subtyping relation between session types, is semantically -rather than syntactically- grounded.
Modeling Human Interaction to Design a Human-Computer Dialog System
Venue: arXiv cs.HC 2009
Year: 2009

This article presents the Cogni-CISMeF project, which aims at improving the health information search engine CISMeF, by including a conversational agent that interacts with the user in natural language. To study the cognitive processes involved during information search, a bottom-up methodology was adopted. An experiment has been set up to obtain human dialogs related to such searches. The analysis of these dialogs underlines the establishment of a common ground and accommodation effects to the user. A model of artificial agent is proposed, that guides the user by proposing examples, assistance and choices.
Approximate Sparse Recovery: Optimizing Time and Measurements
Venue: arXiv cs.DS 2009
Year: 2009

An approximate sparse recovery system consists of parameters $k,N$, an $m$-by-$N$ measurement matrix, $Φ$, and a decoding algorithm, $\mathcal{D}$. Given a vector, $x$, the system approximates $x$ by $\widehat x =\mathcal{D}(Φx)$, which must satisfy $\| \widehat x - x\|_2\le C \|x - x_k\|_2$, where $x_k$ denotes the optimal $k$-term approximation to $x$. For each vector $x$, the system must succeed with probability at least 3/4. Among the goals in designing such systems are minimizing the number $m$ of measurements and the runtime of the decoding algorithm, $\mathcal{D}$. In this paper, we give a system with $m=O(k \log(N/k))$ measurements--matching a lower bound, up to a constant factor--and decoding time $O(k\log^c N)$, matching a lower bound up to $\log(N)$ factors. We also consider the encode time (i.e., the time to multiply $Φ$ by $x$), the time to update measurements (i.e., the time to multiply $Φ$ by a 1-sparse $x$), and the robustness and stability of the algorithm (adding noise before and after the measurements). Our encode and update times are optimal up to $\log(N)$ factors.
Single-Agent On-line Path Planning in Continuous, Unpredictable and Highly Dynamic Environments
Venue: arXiv cs.AI 2009
Year: 2009

This document is a thesis on the subject of single-agent on-line path planning in continuous,unpredictable and highly dynamic environments. The problem is finding and traversing a collision-free path for a holonomic robot, without kinodynamic restrictions, moving in an environment with several unpredictably moving obstacles or adversaries. The availability of perfect information of the environment at all times is assumed. Several static and dynamic variants of the Rapidly Exploring Random Trees (RRT) algorithm are explored, as well as an evolutionary algorithm for planning in dynamic environments called the Evolutionary Planner/Navigator. A combination of both kinds of algorithms is proposed to overcome shortcomings in both, and then a combination of a RRT variant for initial planning and informed local search for navigation, plus a simple greedy heuristic for optimization. We show that this combination of simple techniques provides better responses to highly dynamic environments than the RRT extensions.
Hardness Results for the Gapped Consecutive-Ones Property
Venue: arXiv cs.CC 2009
Year: 2009

Motivated by problems of comparative genomics and paleogenomics, in [Chauve et al., 2009], the authors introduced the Gapped Consecutive-Ones Property Problem (k,delta)-C1P: given a binary matrix M and two integers k and delta, can the columns of M be permuted such that each row contains at most k blocks of ones and no two consecutive blocks of ones are separated by a gap of more than delta zeros. The classical C1P problem, which is known to be polynomial is equivalent to the (1,0)-C1P problem. They showed that the (2,delta)-C1P Problem is NP-complete for all delta >= 2 and that the (3,1)-C1P problem is NP-complete. They also conjectured that the (k,delta)-C1P Problem is NP-complete for k >= 2, delta >= 1 and (k,delta) =/= (2,1). Here, we prove that this conjecture is true. The only remaining case is the (2,1)-C1P Problem, which could be polynomial-time solvable.
Hardness Amplification in Proof Complexity
Venue: arXiv cs.CC 2009
Year: 2009

We present a general method for converting any family of unsatisfiable CNF formulas that is hard for one of the simplest proof systems, tree resolution, into formulas that require large rank in any proof system that manipulates polynomials or polynomial threshold functions of degree at most k (known as Th(k) proofs). Such systems include Lovasz-Schrijver and Cutting Planes proof systems as well as their high degree analogues. These are based on analyzing two new proof systems, denoted by T^cc(k) and R^cc(k). The proof lines of T^cc(k) are arbitrary Boolean functions, each of which can be evaluated by an efficient k-party randomized communication protocol. They include Th{k-1} proofs as a special case. R^cc(k) proofs are stronger and only require that each inference be locally checkable by an efficient k-party randomized communication protocol. Our main results are the following: (1) When k is O(loglogn), for any unsatisfiable CNF formula F requiring resolution rank r, there is a related CNF formula G=Lift_k(F) requiring refutation rank r^Omega(1/k) log^O(1) n in all R^cc(k) systems. (2) There are strict hierarchies for T^cc(k) and R^cc(k) systems with respect to k when k is O(loglogn in that there are unsatisfiable CNF formulas requiring large rank R^cc(k) refutations but having log^O(1) n rank Th(k) refutations. (3) When k is O(loglogn) there are 2^(n^Omega(1/k)) lower bounds on the size of tree-like T^cc(k) refutations for large classes of lifted CNF formulas. (4) A general method for producing integrality gaps for low rank R^cc(2) inference (and hence Cutting Planes and Th(1) inference) based on related gaps for low rank resolution. These gaps are optimal for MAX-2t-SAT.
Isometric Multi-Manifolds Learning
Venue: arXiv cs.LG 2009
Year: 2009

Isometric feature mapping (Isomap) is a promising manifold learning method. However, Isomap fails to work on data which distribute on clusters in a single manifold or manifolds. Many works have been done on extending Isomap to multi-manifolds learning. In this paper, we first proposed a new multi-manifolds learning algorithm (M-Isomap) with help of a general procedure. The new algorithm preserves intra-manifold geodesics and multiple inter-manifolds edges precisely. Compared with previous methods, this algorithm can isometrically learn data distributed on several manifolds. Secondly, the original multi-cluster manifold learning algorithm first proposed in \cite{DCIsomap} and called D-C Isomap has been revised so that the revised D-C Isomap can learn multi-manifolds data. Finally, the features and effectiveness of the proposed multi-manifolds learning algorithms are demonstrated and compared through experiments.
Reversible Image Authentication with Tamper Localization Based on Integer Wavelet Transform
Venue: arXiv cs.CR 2009
Year: 2009

In this paper, a new reversible image authentication technique with tamper localization based on watermarking in integer wavelet transform is proposed. If the image authenticity is verified, then the distortion due to embedding the watermark can be completely removed from the watermarked image. If the image is tampered, then the tampering positions can also be localized. Two layers of watermarking are used. The first layer embedded in spatial domain verifies authenticity and the second layer embedded in transform domain provides reversibility. This technique utilizes selective LSB embedding and histogram characteristics of the difference images of the wavelet coefficients and modifies pixel values slightly to embed the watermark. Experimental results demonstrate that the proposed scheme can detect any modifications of the watermarked image.
Beamforming in MISO Systems: Empirical Results and EVM-based Analysis
Venue: arXiv cs.IT 2009
Year: 2009

We present an analytical, simulation, and experimental-based study of beamforming Multiple Input Single Output (MISO) systems. We analyze the performance of beamforming MISO systems taking into account implementation complexity and effects of imperfect channel estimate, delayed feedback, real Radio Frequency (RF) hardware, and imperfect timing synchronization. Our results show that efficient implementation of codebook-based beamforming MISO systems with good performance is feasible in the presence of channel and implementation-induced imperfections. As part of our study we develop a framework for Average Error Vector Magnitude Squared (AEVMS)-based analysis of beamforming MISO systems which facilitates comparison of analytical, simulation, and experimental results on the same scale. In addition, AEVMS allows fair comparison of experimental results obtained from different wireless testbeds. We derive novel expressions for the AEVMS of beamforming MISO systems and show how the AEVMS relates to important system characteristics like the diversity gain, coding gain, and error floor.
Lexical evolution rates by automated stability measure
Venue: arXiv cs.CL 2009
Year: 2009

Phylogenetic trees can be reconstructed from the matrix which contains the distances between all pairs of languages in a family. Recently, we proposed a new method which uses normalized Levenshtein distances among words with same meaning and averages on all the items of a given list. Decisions about the number of items in the input lists for language comparison have been debated since the beginning of glottochronology. The point is that words associated to some of the meanings have a rapid lexical evolution. Therefore, a large vocabulary comparison is only apparently more accurate then a smaller one since many of the words do not carry any useful information. In principle, one should find the optimal length of the input lists studying the stability of the different items. In this paper we tackle the problem with an automated methodology only based on our normalized Levenshtein distance. With this approach, the program of an automated reconstruction of languages relationships is completed.
Applying an XML Warehouse to Social Network Analysis, Lessons from the WebStand Project
Venue: arXiv cs.DB 2009
Year: 2009

In this paper we present the state of advancement of the French ANR WebStand project. The objective of this project is to construct a customizable XML based warehouse platform to acquire, transform, analyze, store, query and export data from the web, in particular mailing lists, with the final intension of using this data to perform sociological studies focused on social groups of World Wide Web, with a specific emphasis on the temporal aspects of this data. We are currently using this system to analyze the standardization process of the W3C, through its social network of standard setters.
Modified Opportunistic Deficit Round Robin Scheduling for improved QOS in IEEE 802.16 WBA networks
Venue: arXiv cs.NI 2009
Year: 2009

Packet and flow scheduling algorithms for WiMAX has been a topic of interest for a long time since the very inception of WiMAX networks. WiMAX offers advantages particularly in terms of Quality of service it offers over a longer range at the MAC level. In our work, we propose two credit based scheduling schemes one in which completed flows distributes the left over credits equally to all higher priority uncompleted flows(ODRREDC) and another in which completed flows give away all the excess credits to the highest priority uncompleted flow(ODRRSDC). Both the schemes are compatible with 802.16 MAC protocol and can efficiently serve real time bursty traffic with reduced latency and hence improved QOS for real time flows. We compare the two proposed schemes for their latency, bandwidth utilization and throughput for real time burst flows with the opportunity based Deficit Round Robin scheduling scheme. While the ODRR scheduler focuses on reducing the credits for the flows with errors, our approach also distributes these remaining credits together with the credits from completed flows equally among the higher priority uncompleted flows or totally to the highest priority uncompleted flow.
Educational Objectives Of Different Laboratory Types: A Comparative Study
Venue: arXiv cs.CY 2009
Year: 2009

Laboratory based courses play a critical role in scientific education. Automation is changing the nature of the laboratories, and there is a long running debate about the value of hands on versus simulated and remote laboratories. The remote lab technology has brought a significant improvement in communication within the Academic community and has improved students learning experiences. There are different educational objectives as criteria for judging the laboratories: Hands on advocates emphasize design skills, while remote lab advocates focus on conceptual understanding. Remote laboratories offer all the advantages of the new technology, but are often a poor replacement for real laboratory work. Remote laboratories are similar to simulation techniques in that they require minimal space and time, because the experiments can be rapidly configured and run over the Internet [Web]. But unlike simulations, they provide real data. This paper presents a comparative analysis for the educational objectives of the three laboratory techniques, hands on, simulated, and remote laboratories. In addition, it proposes enhancements for the remote lab activities leading to improving its performance.
A Survey on Recognition Based Graphical User Authentication Algorithms
Venue: arXiv cs.CR 2009
Year: 2009

Nowadays, user authentication is one of the important topics in information security. Strong textbased password schemes could provide with certain degree of security. However, the fact that strong passwords are difficult to memorize often leads their owners to write them down on papers or even save them in a computer file. Graphical authentication has been proposed as a possible alternative solution to textbased authentication, motivated particularly by the fact that humans can remember images better than text. In recent years, many networks, computer systems and Internet based environments try used graphical authentication technique for their users authentication. All of graphical passwords have two different aspects which are usability and security. Unfortunately none of these algorithms were being able to cover both of these aspects at the same time. In this paper, we described eight recognition based authentication algorithms in terms of their drawbacks and attacks. In the next section, the usability standards from ISO and the related attributes for graphical user authentication usability are discussed. The related attack patterns for graphical user authentication security part are also discussed. Finally, a comparison table of all recognition based algorithms is presented based on ISO and attack patterns standards.
Discussion on Supervisory Control by Solving Automata Equation
Venue: arXiv cs.OH 2009
Year: 2009

In this paper we consider the supervisory control problem through language equation solving. The equation solving approach allows to deal with more general topologies and to find a largest supervisor which can be used as a reservoir for deriving an optimal controller. We introduce the notions of solutions under partial controllability and partial observability, and we show how supervisory control problems with partial controllability and partial observability can be solved by employing equation solving methods.
Architectural Design Activities for JAS
Venue: arXiv cs.SE 2009
Year: 2009

The critical part for building any software system is its architecture. Architectural design is a design at a higher level of abstraction. A good architecture ensures that software will satisfy its requirement. This paper defines the most important activities of architectural design that used through building any software; also it applies these activities on one type of Electronic Commerce (EC) applications that is Job Agency System(JAS) to show how these activities can work through these types of applications.
Biogeography based Satellite Image Classification
Venue: arXiv cs.CV 2009
Year: 2009

Biogeography is the study of the geographical distribution of biological organisms. The mindset of the engineer is that we can learn from nature. Biogeography Based Optimization is a burgeoning nature inspired technique to find the optimal solution of the problem. Satellite image classification is an important task because it is the only way we can know about the land cover map of inaccessible areas. Though satellite images have been classified in past by using various techniques, the researchers are always finding alternative strategies for satellite image classification so that they may be prepared to select the most appropriate technique for the feature extraction task in hand. This paper is focused on classification of the satellite image of a particular land cover using the theory of Biogeography based Optimization. The original BBO algorithm does not have the inbuilt property of clustering which is required during image classification. Hence modifications have been proposed to the original algorithm and the modified algorithm is used to classify the satellite image of a given region. The results indicate that highly accurate land cover features can be extracted effectively when the proposed algorithm is used.
Refactoring of a Database
Venue: arXiv cs.DB 2009
Year: 2009

The technique of database refactoring is all about applying disciplined and controlled techniques to change an existing database schema. The problem is to successfully create a Database Refactoring Framework for databases. This paper concentrates on the feasibility of adapting this concept to work as a generic template. To retain the constraints regardless of the modifications to the metadata, the paper proposes a MetaData Manipulation Tool to facilitate change. The tool adopts a Template Design Pattern to make it database independent. The paper presents a drawback of using java for constraint extraction and proposes an alternative.
Genetic Programming Framework for Fingerprint Matching
Venue: arXiv cs.CR 2009
Year: 2009

A fingerprint matching is a very difficult problem. Minutiae based matching is the most popular and widely used technique for fingerprint matching. The minutiae points considered in automatic identification systems are based normally on termination and bifurcation points. In this paper we propose a new technique for fingerprint matching using minutiae points and genetic programming. The goal of this paper is extracting the mathematical formula that defines the minutiae points.