OpenRaiser/Intern-Atlas huggingface dataset:
Simultaneously Sparse Solutions to Linear Inverse Problems with Multiple System Matrices and a Single Observation Vector
Venue: arXiv cs.NA 2009
Year: 2009

A linear inverse problem is proposed that requires the determination of multiple unknown signal vectors. Each unknown vector passes through a different system matrix and the results are added to yield a single observation vector. Given the matrices and lone observation, the objective is to find a simultaneously sparse set of unknown vectors that solves the system. We will refer to this as the multiple-system single-output (MSSO) simultaneous sparsity problem. This manuscript contrasts the MSSO problem with other simultaneous sparsity problems and conducts a thorough initial exploration of algorithms with which to solve it. Seven algorithms are formulated that approximately solve this NP-Hard problem. Three greedy techniques are developed (matching pursuit, orthogonal matching pursuit, and least squares matching pursuit) along with four methods based on a convex relaxation (iteratively reweighted least squares, two forms of iterative shrinkage, and formulation as a second-order cone program). The algorithms are evaluated across three experiments: the first and second involve sparsity profile recovery in noiseless and noisy scenarios, respectively, while the third deals with magnetic resonance imaging radio-frequency excitation pulse design.
Kernels for Feedback Arc Set In Tournaments
Venue: arXiv cs.DS 2009
Year: 2009

A tournament T=(V,A) is a directed graph in which there is exactly one arc between every pair of distinct vertices. Given a digraph on n vertices and an integer parameter k, the Feedback Arc Set problem asks whether the given digraph has a set of k arcs whose removal results in an acyclic digraph. The Feedback Arc Set problem restricted to tournaments is known as the k-Feedback Arc Set in Tournaments (k-FAST) problem. In this paper we obtain a linear vertex kernel for k-FAST. That is, we give a polynomial time algorithm which given an input instance T to k-FAST obtains an equivalent instance T' on O(k) vertices. In fact, given any fixed e>0, the kernelized instance has at most (2+e)k vertices. Our result improves the previous known bound of O(k^2) on the kernel size for k-FAST. Our kernelization algorithm solves the problem on a subclass of tournaments in polynomial time and uses a known polynomial time approximation scheme for k-FAST.
Pattern Based Term Extraction Using ACABIT System
Venue: arXiv cs.CL 2009
Year: 2009

In this paper, we propose a pattern-based term extraction approach for Japanese, applying ACABIT system originally developed for French. The proposed approach evaluates termhood using morphological patterns of basic terms and term variants. After extracting term candidates, ACABIT system filters out non-terms from the candidates based on log-likelihood. This approach is suitable for Japanese term extraction because most of Japanese terms are compound nouns or simple phrasal patterns.
Extremal problems in ordered graphs
Venue: arXiv cs.DM 2009
Year: 2009

In this thesis we consider ordered graphs (that is, graphs with a fixed linear ordering on their vertices). We summarize and further investigations on the number of edges an ordered graph may have while avoiding a fixed forbidden ordered graph as a subgraph. In particular, we take a step toward confirming a conjecture of Pach and Tardos regarding the number of edges allowed when the forbidden pattern is a tree by establishing an upper bound for a particular ordered graph for which existing techniques have failed. We also generalize a theorem of Geneson by establishing an upper bound on the number of edges allowed if the forbidden graphs fit a generalized notion of a matching.
Towards Hybrid Intensional Programming with JLucid, Objective Lucid, and General Imperative Compiler Framework in the GIPSY
Venue: arXiv cs.PL 2009
Year: 2009

Pure Lucid programs are concurrent with very fine granularity. Sequential Threads (STs) are functions introduced to enlarge the grain size; they are passed from server to workers by Communication Procedures (CPs) in the General Intensional Programming System (GIPSY). A JLucid program combines Java code for the STs with Lucid code for parallel control. Thus first, in this thesis, we describe the way in which the new JLucid compiler generates STs and CPs. JLucid also introduces array support. Further exploration goes through the additional transformations that the Lucid family of languages has undergone to enable the use of Java objects and their members, in the Generic Intensional Programming Language (GIPL), and Indexical Lucid: first, in the form of JLucid allowing the use of pseudo-objects, and then through the specifically-designed the Objective Lucid language. The syntax and semantic definitions of Objective Lucid and the meaning of Java objects within an intensional program are provided with discussions and examples. Finally, there are many useful scientific and utility routines written in many imperative programming languages other than Java, for example in C, C++, Fortran, Perl, etc. Therefore, it is wise to provide a framework to facilitate inclusion of these languages into the GIPSY and their use by Lucid programs. A General Imperative Compiler Framework and its concrete implementation is proposed to address this issue.
Bounded Delay Packet Scheduling in a Bounded Buffer
Venue: arXiv cs.DS 2009
Year: 2009

We study the problem of buffer management in QoS-enabled network switches in the bounded delay model where each packet is associated with a weight and a deadline. We consider the more realistic situation where the network switch has a finite buffer size. A 9.82-competitive algorithm is known for the case of multiple buffers (Azar and Levy, SWAT'06). Recently, for the case of a single buffer, a 3-competitive deterministic algorithm and a 2.618-competitive randomized algorithm was known (Li, INFOCOM'09). In this paper we give a simple deterministic 2-competitive algorithm for the case of a single buffer.
Scalable Probabilistic Similarity Ranking in Uncertain Databases (Technical Report)
Venue: arXiv cs.DB 2009
Year: 2009

This paper introduces a scalable approach for probabilistic top-k similarity ranking on uncertain vector data. Each uncertain object is represented by a set of vector instances that are assumed to be mutually-exclusive. The objective is to rank the uncertain data according to their distance to a reference object. We propose a framework that incrementally computes for each object instance and ranking position, the probability of the object falling at that ranking position. The resulting rank probability distribution can serve as input for several state-of-the-art probabilistic ranking models. Existing approaches compute this probability distribution by applying a dynamic programming approach of quadratic complexity. In this paper we theoretically as well as experimentally show that our framework reduces this to a linear-time complexity while having the same memory requirements, facilitated by incremental accessing of the uncertain vector instances in increasing order of their distance to the reference object. Furthermore, we show how the output of our method can be used to apply probabilistic top-k ranking for the objects, according to different state-of-the-art definitions. We conduct an experimental evaluation on synthetic and real data, which demonstrates the efficiency of our approach.
Improvements for multi-objective flow shop scheduling by Pareto Iterated Local Search
Venue: arXiv cs.AI 2009
Year: 2009

The article describes the proposition and application of a local search metaheuristic for multi-objective optimization problems. It is based on two main principles of heuristic search, intensification through variable neighborhoods, and diversification through perturbations and successive iterations in favorable regions of the search space. The concept is successfully tested on permutation flow shop scheduling problems under multiple objectives and compared to other local search approaches. While the obtained results are encouraging in terms of their quality, another positive attribute of the approach is its simplicity as it does require the setting of only very few parameters.
Rational Synthesis
Venue: arXiv cs.LO 2009
Year: 2009

Synthesis is the automated construction of a system from its specification. The system has to satisfy its specification in all possible environments. Modern systems often interact with other systems, or agents. Many times these agents have objectives of their own, other than to fail the system. Thus, it makes sense to model system environments not as hostile, but as composed of rational agents; i.e., agents that act to achieve their own objectives. We introduce the problem of synthesis in the context of rational agents (rational synthesis, for short). The input consists of a temporal-logic formula specifying the system and temporal-logic formulas specifying the objectives of the agents. The output is an implementation T of the system and a profile of strategies, suggesting a behavior for each of the agents. The output should satisfy two conditions. First, the composition of T with the strategy profile should satisfy the specification. Second, the strategy profile should be an equilibria in the sense that, in view of their objectives, agents have no incentive to deviate from the strategies assigned to them. We solve the rational-synthesis problem for various definitions of equilibria studied in game theory. We also consider the multi-valued case in which the objectives of the system and the agents are still temporal logic formulas, but involve payoffs from a finite lattice.
Verification of Timed Automata Using Rewrite Rules and Strategies
Venue: arXiv cs.LO 2009
Year: 2009

ELAN is a powerful language and environment for specifying and prototyping deduction systems in a language based on rewrite rules controlled by strategies. Timed automata is a class of continuous real-time models of reactive systems for which efficient model-checking algorithms have been devised. In this paper, we show that these algorithms can very easily be prototyped in the ELAN system. This paper argues through this example that rewriting based systems relying on rules and strategies are a good framework to prototype, study and test rather efficiently symbolic model-checking algorithms, i.e. algorithms which involve combination of graph exploration rules, deduction rules, constraint solving techniques and decision procedures.
Mathematical Interpretation between Genotype and Phenotype Spaces and Induced Geometric Crossovers
Venue: arXiv cs.NE 2009
Year: 2009

In this paper, we present that genotype-phenotype mapping can be theoretically interpreted using the concept of quotient space in mathematics. Quotient space can be considered as mathematically-defined phenotype space in the evolutionary computation theory. The quotient geometric crossover has the effect of reducing the search space actually searched by geometric crossover, and it introduces problem knowledge in the search by using a distance better tailored to the specific solution interpretation. Quotient geometric crossovers are directly applied to the genotype space but they have the effect of the crossovers performed on phenotype space. We give many example applications of the quotient geometric crossover.
The Compound Capacity of Polar Codes
Venue: arXiv cs.IT 2009
Year: 2009

We consider the compound capacity of polar codes under successive cancellation decoding for a collection of binary-input memoryless output-symmetric channels. By deriving a sequence of upper and lower bounds, we show that in general the compound capacity under successive decoding is strictly smaller than the unrestricted compound capacity.
Effective Personalized Recommendation in Collaborative Tagging Systems
Venue: arXiv cs.IR 2009
Year: 2009

Recently, collaborative tagging systems have attracted more and more attention and have been widely applied in web systems. Tags provide highly abstracted information about personal preferences and item content, and are therefore potential to help in improving better personalized recommendations. In this paper, we propose a tag-based recommendation algorithm considering the personal vocabulary and evaluate it in a real-world dataset: Del.icio.us. Experimental results demonstrate that the usage of tag information can significantly improve the accuracy of personalized recommendations.
Neural Modeling and Control of Diesel Engine with Pollution Constraints
Venue: arXiv cs.LG 2009
Year: 2009

The paper describes a neural approach for modelling and control of a turbocharged Diesel engine. A neural model, whose structure is mainly based on some physical equations describing the engine behaviour, is built for the rotation speed and the exhaust gas opacity. The model is composed of three interconnected neural submodels, each of them constituting a nonlinear multi-input single-output error model. The structural identification and the parameter estimation from data gathered on a real engine are described. The neural direct model is then used to determine a neural controller of the engine, in a specialized training scheme minimising a multivariable criterion. Simulations show the effect of the pollution constraint weighting on a trajectory tracking of the engine speed. Neural networks, which are flexible and parsimonious nonlinear black-box models, with universal approximation capabilities, can accurately describe or control complex nonlinear systems, with little a priori theoretical knowledge. The presented work extends optimal neuro-control to the multivariable case and shows the flexibility of neural optimisers. Considering the preliminary results, it appears that neural networks can be used as embedded models for engine control, to satisfy the more and more restricting pollutant emission legislation. Particularly, they are able to model nonlinear dynamics and outperform during transients the control schemes based on static mappings.
Reachability-time games on timed automata
Venue: arXiv cs.CC 2009
Year: 2009

In a reachability-time game, players Min and Max choose moves so that the time to reach a final state in a timed automaton is minimised or maximised, respectively. Asarin and Maler showed decidability of reachability-time games on strongly non-Zeno timed automata using a value iteration algorithm. This paper complements their work by providing a strategy improvement algorithm for the problem. It also generalizes their decidability result because the proposed strategy improvement algorithm solves reachability-time games on all timed automata. The exact computational complexity of solving reachability-time games is also established: the problem is EXPTIME-complete for timed automata with at least two clocks.
Exploring Peer Review in the Computer Science Classroom
Venue: arXiv cs.CY 2009
Year: 2009

In computer science, students could benefit from more opportunities to learn important, high-level concepts and to improve their learning skills. Peer review is one method to encourage this by providing students with the opportunity to evaluate other people's work and to receive feedback on their own projects. This allows for rich learning experience but it is not immediately obvious how to create a programming project review that will improve the students' conceptual understanding, require higher level thinking, and be engaging. The current literature does not typically address differences between review implementations or provide reasons for design decisions. This work explored how two different types of reviews affected the students' learning of concepts, high-level thinking, and engagement. There were indications that the type of review affected how well students addressed the concept they were reviewing and the comments' length. This shows that the review's type may affect student engagement and conceptual learning. There were also differences in how they reviewed the concepts of Abstraction, Decomposition, and Encapsulation, suggesting that the concepts are being learned in different ways. Both of these results have an impact on the use of peer review computer science but need further investigation.
Secure Network Coding for Wiretap Networks of Type II
Venue: arXiv cs.IT 2009
Year: 2009

We consider the problem of securing a multicast network against a wiretapper that can intercept the packets on a limited number of arbitrary network edges of its choice. We assume that the network employs the network coding technique to simultaneously deliver the packets available at the source to all the receivers. We show that this problem can be looked at as a network generalization of the wiretap channel of type II introduced in a seminal paper by Ozarow and Wyner. In particular, we show that the transmitted information can be secured by using the Ozarow-Wyner approach of coset coding at the source on top of the existing network code. This way, we quickly and transparently recover some of the results available in the literature on secure network coding for wiretap networks. Moreover, we derive new bounds on the required alphabet size that are independent of the network size and devise an algorithm for the construction of secure network codes. We also look at the dual problem and analyze the amount of information that can be gained by the wiretapper as a function of the number of wiretapped edges.
Various thresholds for $\ell_1$-optimization in compressed sensing
Venue: arXiv cs.IT 2009
Year: 2009

Recently, \cite{CRT,DonohoPol} theoretically analyzed the success of a polynomial $\ell_1$-optimization algorithm in solving an under-determined system of linear equations. In a large dimensional and statistical context \cite{CRT,DonohoPol} proved that if the number of equations (measurements in the compressed sensing terminology) in the system is proportional to the length of the unknown vector then there is a sparsity (number of non-zero elements of the unknown vector) also proportional to the length of the unknown vector such that $\ell_1$-optimization succeeds in solving the system. In this paper, we provide an alternative performance analysis of $\ell_1$-optimization and obtain the proportionality constants that in certain cases match or improve on the best currently known ones from \cite{DonohoPol,DT}.
On the Geometry of Differential Privacy
Venue: arXiv cs.CC 2009
Year: 2009

We consider the noise complexity of differentially private mechanisms in the setting where the user asks $d$ linear queries $f\colon\Rn\to\Re$ non-adaptively. Here, the database is represented by a vector in $\Rn$ and proximity between databases is measured in the $\ell_1$-metric. We show that the noise complexity is determined by two geometric parameters associated with the set of queries. We use this connection to give tight upper and lower bounds on the noise complexity for any $d \leq n$. We show that for $d$ random linear queries of sensitivity~1, it is necessary and sufficient to add $\ell_2$-error $Θ(\min\{d\sqrt{d}/ε,d\sqrt{\log (n/d)}/ε\})$ to achieve $ε$-differential privacy. Assuming the truth of a deep conjecture from convex geometry, known as the Hyperplane conjecture, we can extend our results to arbitrary linear queries giving nearly matching upper and lower bounds. Our bound translates to error $O(\min\{d/ε,\sqrt{d\log(n/d)}/ε\})$ per answer. The best previous upper bound (Laplacian mechanism) gives a bound of $O(\min\{d/\eps,\sqrt{n}/ε\})$ per answer, while the best known lower bound was $Ω(\sqrt{d}/ε)$. In contrast, our lower bound is strong enough to separate the concept of differential privacy from the notion of approximate differential privacy where an upper bound of $O(\sqrt{d}/ε)$ can be achieved.
A multiobjective Tabu framework for the optimization and evaluation of wireless systems
Venue: arXiv cs.NI 2009
Year: 2009

This chapter will focus on the multiobjective formulation of an optimization problem and highlight the assets of a multiobjective Tabu implementation for such problems. An illustration of a specific Multiobjective Tabu heuristic (referred to as MO Tabu in the following) will be given for 2 particular problems arising in wireless systems. The first problem addresses the planning of access points for a WLAN network with some Quality of Service requirements and the second one provides an evaluation mean to assess the performance evaluation of a wireless sensor network. The chapter will begin with an overview of multiobjective (MO) optimization featuring the definitions and concepts of the domain (e.g. Dominance, Pareto front,...) and the main MO search heuristics available so far. We will then emphasize on the definition of a problem as a multiobjective optimization problem and illustrate it by the two examples from the field of wireless networking. The next part will focus on MO Tabu, a Tabu-inspired multiobjective heuristic and describe its assets compared to other MO heuristics. The last part of the chapter will show the results obtained with this MO Tabu strategy on the 2 wireless networks related problems. Conclusion on the use of Tabu as a multiobjective heuristic will be drawn based on the results presented so far.
Un système modulaire d'acquisition automatique de traductions à partir du Web
Venue: arXiv cs.CL 2009
Year: 2009

We present a method of automatic translation (French/English) of Complex Lexical Units (CLU) for aiming at extracting a bilingual lexicon. Our modular system is based on linguistic properties (compositionality, polysemy, etc.). Different aspects of the multilingual Web are used to validate candidate translations and collect new terms. We first build a French corpus of Web pages to collect CLU. Three adapted processing stages are applied for each linguistic property : compositional and non polysemous translations, compositional polysemous translations and non compositional translations. Our evaluation on a sample of CLU shows that our technique based on the Web can reach a very high precision.
Cross-layer Resource Allocation Scheme for Multi-band High Rate UWB Systems
Venue: arXiv cs.NI 2009
Year: 2009

In this paper, we investigate the use of a cross-layer allocation mechanism for the high-rate ultra-wideband (UWB) systems. The aim of this paper is twofold. First, through the cross-layer approach that provides a new service differentiation approach to the fully distributed UWB systems, we support traffic with quality of service (QoS) guarantee in a multi-user context. Second, we exploit the effective SINR method that represents the characteristics of multiple sub-carrier SINRs in the multi-band WiMedia solution proposed for UWB systems, in order to provide the channel state information needed for the multi-user sub-band allocation. This new approach improves the system performance and optimizes the spectrum utilization with a low cost data exchange between the different users while guaranteeing the required QoS. In addition, this new approach solves the problem of the cohabitation of more than three users in the same WiMedia channel.
Experimental DML over digital repositories in Japan
Venue: arXiv cs.DL 2009
Year: 2009

In this paper the authors show an overview of Virtual Digital Mathematics Library in Japan (DML-JP), contents of which consist of metadata harvested from institutional repositories in Japan and digital repositories in the world. DML-JP is, in a sense, a subject specific repository which collaborate with various digital repositories. Beyond portal website, DML-JP provides subject-specific metadata through OAI-ORE. By the schema it is enabled that digital repositories can load the rich metadata which were added by mathematicians.