OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Higher Order Derivatives of Objective Functions Composed of Matrix Operations
Venue: arXiv cs.DS 2009
Year: 2009

This paper is concerned with the efficient evaluation of higher-order derivatives of functions $f$ that are composed of matrix operations. I.e., we want to compute the $D$-th derivative tensor $\nabla^D f(X) \in \mathbb R^{N^D}$, where $f:\mathbb R^{N} \to \mathbb R$ is given as an algorithm that consists of many matrix operations. We propose a method that is a combination of two well-known techniques from Algorithmic Differentiation (AD): univariate Taylor propagation on scalars (UTPS) and first-order forward and reverse on matrices. The combination leads to a technique that we would like to call univariate Taylor propagation on matrices (UTPM). The method inherits many desirable properties: It is easy to implement, it is very efficient and it returns not only $\nabla^D f$ but yields in the process also the derivatives $\nabla^d f$ for $d \leq D$. As performance test we compute the gradient $\nabla f(X)$ % and the Hessian $\nabla_A^2 f(A)$ by a combination of forward and reverse mode of $f(X) = \trace (X^{-1})$ in the reverse mode of AD for $X \in \mathbb R^{n \times n}$. We observe a speedup of about 100 compared to UTPS. Due to the nature of the method, the memory footprint is also small and therefore can be used to differentiate functions that are not accessible by standard methods due to limited physical memory.
Abstract Interpretation for Probabilistic Termination of Biological Systems
Venue: arXiv cs.LO 2009
Year: 2009

In a previous paper the authors applied the Abstract Interpretation approach for approximating the probabilistic semantics of biological systems, modeled specifically using the Chemical Ground Form calculus. The methodology is based on the idea of representing a set of experiments, which differ only for the initial concentrations, by abstracting the multiplicity of reagents present in a solution, using intervals. In this paper, we refine the approach in order to address probabilistic termination properties. More in details, we introduce a refinement of the abstract LTS semantics and we abstract the probabilistic semantics using a variant of Interval Markov Chains. The abstract probabilistic model safely approximates a set of concrete experiments and reports conservative lower and upper bounds for probabilistic termination.
Faster FAST(Feedback Arc Set in Tournaments)
Venue: arXiv cs.DS 2009
Year: 2009

We present an algorithm that finds a feedback arc set of size $k$ in a tournament in time $n^{O(1)}2^{O(\sqrt{k})}$. This is asymptotically faster than the running time of previously known algorithms for this problem.
Standardization of the formal representation of lexical information for NLP
Venue: arXiv cs.CL 2009
Year: 2009

A survey of dictionary models and formats is presented as well as a presentation of corresponding recent standardisation activities.
An Implementation of the Language Lambda Prolog Organized around Higher-Order Pattern Unification
Venue: arXiv cs.PL 2009
Year: 2009

This thesis concerns the implementation of Lambda Prolog, a higher-order logic programming language that supports the lambda-tree syntax approach to representing and manipulating formal syntactic objects. Lambda Prolog achieves its functionality by extending a Prolog-like language by using typed lambda terms as data structures that it then manipulates via higher-order unification and some new program-level abstraction mechanisms. These additional features raise new implementation questions that must be adequately addressed for Lambda Prolog to be an effective programming tool. We consider these questions here, providing eventually a virtual machine and compilation based realization. A key idea is the orientation of the computation model of Lambda Prolog around a restricted version of higher-order unification with nice algorithmic properties and appearing to encompass most interesting applications. Our virtual machine embeds a treatment of this form of unification within the structure of the Warren Abstract Machine that is used in traditional Prolog implementations. Along the way, we treat various auxiliary issues such as the low-level representation of lambda terms, the implementation of reduction on such terms and the optimized processing of types in computation. We also develop an actual implementation of Lambda Prolog called Teyjus Version 2. A characteristic of this system is that it realizes an emulator for the virtual machine in the C language a compiler in the OCaml language. We present a treatment of the software issues that arise from this kind of mixing of languages within one system and we discuss issues relevant to the portability of our virtual machine emulator across arbitrary architectures. Finally, we assess the the efficacy of our various design ideas through experiments carried out using the system.
Laser Actuated Presentation System
Venue: arXiv cs.HC 2009
Year: 2009

We present here a pattern sensitive PowerPoint presentation scheme. The presentation is actuated by simple patterns drawn on the presentation screen by a laser pointer. A specific pattern corresponds to a particular command required to operate the presentation. Laser spot on the screen is captured by a RGB webcam with a red filter mounted, and its location is identified at the blue layer of each captured frame by estimating the mean position of the pixels whose intensity is above a given threshold value. Measured Reliability, Accuracy and Latency of our system are 90%, 10 pixels (in the worst case) and 38 ms respectively.
Coordination via Interaction Constraints I: Local Logic
Venue: arXiv cs.LO 2009
Year: 2009

Wegner describes coordination as constrained interaction. We take this approach literally and define a coordination model based on interaction constraints and partial, iterative and interactive constraint satisfaction. Our model captures behaviour described in terms of synchronisation and data flow constraints, plus various modes of interaction with the outside world provided by external constraint symbols, on-the-fly constraint generation, and coordination variables. Underlying our approach is an engine performing (partial) constraint satisfaction of the sets of constraints. Our model extends previous work on three counts: firstly, a more advanced notion of external interaction is offered; secondly, our approach enables local satisfaction of constraints with appropriate partial solutions, avoiding global synchronisation over the entire constraints set; and, as a consequence, constraint satisfaction can finally occur concurrently, and multiple parts of a set of constraints can be solved and interact with the outside world in an asynchronous manner, unless synchronisation is required by the constraints. This paper describes the underlying logic, which enables a notion of local solution, and relates this logic to the more global approach of our previous work based on classical logic.
Interference Alignment Under Limited Feedback for MIMO Interference Channels
Venue: arXiv cs.IT 2009
Year: 2009

While interference alignment schemes have been employed to realize the full multiplexing gain of $K$-user interference channels, the analyses performed so far have predominantly focused on the case when global channel knowledge is available at each node of the network. This paper considers the problem where each receiver knows its channels from all the transmitters and feeds back this information using a limited number of bits to all other terminals. In particular, channel quantization over the composite Grassmann manifold is proposed and analyzed. It is shown, for $K$-user multiple-input, multiple-output (MIMO) interference channels, that when the transmitters use an interference alignment strategy as if the quantized channel estimates obtained via this limited feedback are perfect, the full sum degrees of freedom of the interference channel can be achieved as long as the feedback bit rate scales sufficiently fast with the signal-to-noise ratio. Moreover, this is only one extreme point of a continuous tradeoff between achievable degrees of freedom region and user feedback rate scalings which are allowed to be non-identical. It is seen that a slower scaling of feedback rate for any one user leads to commensurately fewer degrees of freedom for that user alone.
An affine-intuitionistic system of types and effects: confluence and termination
Venue: arXiv cs.LO 2009
Year: 2009

We present an affine-intuitionistic system of types and effects which can be regarded as an extension of Barber-Plotkin Dual Intuitionistic Linear Logic to multi-threaded programs with effects. In the system, dynamically generated values such as references or channels are abstracted into a finite set of regions. We introduce a discipline of region usage that entails the confluence (and hence determinacy) of the typable programs. Further, we show that a discipline of region stratification guarantees termination.
Modular Workflow Engine for Distributed Services using Lightweight Java Clients
Venue: arXiv cs.SE 2009
Year: 2009

In this article we introduce the concept and the first implementation of a lightweight client-server-framework as middleware for distributed computing. On the client side an installation without administrative rights or privileged ports can turn any computer into a worker node. Only a Java runtime environment and the JAR files comprising the workflow client are needed. To connect all clients to the engine one open server port is sufficient. The engine submits data to the clients and orchestrates their work by workflow descriptions from a central database. Clients request new task descriptions periodically, thus the system is robust against network failures. In the basic set-up, data up- and downloads are handled via HTTP communication with the server. The performance of the modular system could additionally be improved using dedicated file servers or distributed network file systems. We demonstrate the design features of the proposed engine in real-world applications from mechanical engineering. We have used this system on a compute cluster in design-of-experiment studies, parameter optimisations and robustness validations of finite element structures.
A Multidatabase System as 4-Tiered Client-Server Distributed Heterogeneous Database System
Venue: arXiv cs.DB 2009
Year: 2009

In this paper, we describe a multidatabase system as 4tiered Client-Server DBMS architectures. We discuss their functional components and provide an overview of their performance characteristics. The first component of this proposed system is a web based interface or Graphical User Interface, which resides on top of the Client Application Program, the second component of the system is a client Application program running in an application server, which resides on top of the Global Database Management System, the third component of the system is a Global Database Management System and global schema of the multidatabase system server, which resides on top of the distributed heterogeneous local component database system servers, and the fourth component is remote heterogeneous local component database system servers. Transaction submitted from client interface to a multidatabase system server through an application server will be decomposed into a set of sub queries and will be executed at various remote heterogeneous local component database servers and also in case of information retrieval all sub queries will be composed and will get back results to the end users.
Object Oriented Approach for Integration of Heterogeneous Databases in a Multidatabase System and Local Schemas Modifications Propagation
Venue: arXiv cs.DB 2009
Year: 2009

One of the challenging problems in the multidatabase systems is to find the most viable solution to the problem of interoperability of distributed heterogeneous autonomous local component databases. This has resulted in the creation of a global schema over set of these local component database schemas to provide a uniform representation of local schemas. The aim of this paper is to use object oriented approach to integrate schemas of distributed heterogeneous autonomous local component database schemas into a global schema. The resulting global schema provides a uniform interface and high level of location transparency for retrieval of data from the local component databases. A set of integration operators are defined to integrate local schemas based on the semantic relevance of their classes and to provide a model independent representation of virtual classes of the global schema. The schematic representation and heterogeneity is also taken into account in the integration process. Justifications about Object Oriented Modal are also discussed. Bottom up local schema modifications propagation in Global schema is also considered to maintain Global schema as local schemas are autonomous and evolve over time. An example illustrates the applicability of the integration operator defined.
Comparison of Performance Metrics for QPSK and OQPSK Transmission Using Root Raised Cosine and Raised Cosine Pulse shaping Filters for Applications in Mobile Communication
Venue: arXiv cs.IT 2009
Year: 2009

Quadrature Phase Shift Keying (QPSK) and Offset Quadrature Phase Shift Keying (OQPSK) are two well accepted modulation techniques used in Code Division Multiple Access (CDMA) system. The Pulse Shaping Filters play an important role in digital transmission. The type of Pulse Shaping Filter used, and its behavior would influence the performance of the communication system. This in turn, would have an effect on the performance of the Mobile Communication system, in which the digital communication technique has been employed. In this paper we have presented comparative study of some performance parameters or performance metrics of a digital communication system like, Error Vector Magnitude (EVM), Magnitude Error, Phase Error and Bandwidth Efficiency for a QPSK transmission system. Root Raised Cosine (RRC) and Raised Cosine (RC) Pulse shaping filters have been used for comparison. The measurement results serve as a guideline to the system designer to select the proper pulse shaping filter with the appropriate value of filter roll off factor (a) in a QPSK modulated mobile communication system for optimal values of its different performance metrics.
Flow Splitting with Fate Sharing in a Next Generation Transport Services Architecture
Venue: arXiv cs.NI 2009
Year: 2009

The challenges of optimizing end-to-end performance over diverse Internet paths has driven widespread adoption of in-path optimizers, which can destructively interfere with TCP's end-to-end semantics and with each other, and are incompatible with end-to-end IPsec. We identify the architectural cause of these conflicts and resolve them in Tng, an experimental next-generation transport services architecture, by factoring congestion control from end-to-end semantic functions. Through a technique we call "queue sharing", Tng enables in-path devices to interpose on, split, and optimize congestion controlled flows without affecting or seeing the end-to-end content riding these flows. Simulations show that Tng's decoupling cleanly addresses several common performance problems, such as communication over lossy wireless links and reduction of buffering-induced latency on residential links. A working prototype and several incremental deployment paths suggest Tng's practicality.
Adaptive Limited Feedback for Sum-Rate Maximizing Beamforming in Cooperative Multicell Systems
Venue: arXiv cs.IT 2009
Year: 2009

Base station cooperation improves the sum-rates that can be achieved in cellular systems. Conventional cooperation techniques require sharing large amounts of information over finite-capacity backhaul links and assume that base stations have full channel state information (CSI) of all the active users in the system. In this paper, a new limited feedback strategy is proposed for multicell beamforming where cooperation is restricted to sharing only the CSI of active users among base stations. The system setup considered is a linear array of cells based on the Wyner model. Each cell contains single-antenna users and multi-antenna base stations. Closed-form expressions for the beamforming vectors that approximately maximize the sum-rates in a multicell system are first presented, assuming full CSI at the transmitter. For the more practical case of a finite-bandwidth feedback link, CSI of the desired and interfering channels is quantized at the receiver before being fed back to the base station. An upper bound on the mean loss in sum rate due to random vector quantization is derived. A new feedback-bit allocation strategy, to partition the available bits between the desired and interfering channels, is developed to approximately minimize the mean loss in sum-rate due to quantization. The proposed feedback-bit partitioning algorithm is shown, using simulations, to yield sum-rates close to the those obtained using full CSI at base stations.
Quotient Complexity of Closed Languages
Venue: arXiv cs.FL 2009
Year: 2009

A language L is prefix-closed if, whenever a word w is in L, then every prefix of w is also in L. We define suffix-, factor-, and subword-closed languages in the same way, where by subword we mean subsequence. We study the quotient complexity (usually called state complexity) of operations on prefix-, suffix-, factor-, and subword-closed languages. We find tight upper bounds on the complexity of the prefix-, suffix-, factor-, and subword-closure of arbitrary languages, and on the complexity of boolean operations, concatenation, star and reversal in each of the four classes of closed languages. We show that repeated application of positive closure and complement to a closed language results in at most four distinct languages, while Kleene closure and complement gives at most eight languages.
Reduced Complexity Angle-Doppler-Range Estimation for MIMO Radar That Employs Compressive Sensing
Venue: arXiv cs.IT 2009
Year: 2009

The authors recently proposed a MIMO radar system that is implemented by a small wireless network. By applying compressive sensing (CS) at the receive nodes, the MIMO radar super-resolution can be achieved with far fewer observations than conventional approaches. This previous work considered the estimation of direction of arrival and Doppler. Since the targets are sparse in the angle-velocity space, target information can be extracted by solving an l1 minimization problem. In this paper, the range information is exploited by introducing step frequency to MIMO radar with CS. The proposed approach is able to achieve high range resolution and also improve the ambiguous velocity. However, joint angle-Doppler-range estimation requires discretization of the angle-Doppler-range space which causes a sharp rise in the computational burden of the l1 minimization problem. To maintain an acceptable complexity, a technique is proposed to successively estimate angle, Doppler and range in a decoupled fashion. The proposed approach can significantly reduce the complexity without sacrificing performance.
Euclidean Prize-collecting Steiner Forest
Venue: arXiv cs.DS 2009
Year: 2009

In this paper, we consider Steiner forest and its generalizations, prize-collecting Steiner forest and k-Steiner forest, when the vertices of the input graph are points in the Euclidean plane and the lengths are Euclidean distances. First, we present a simpler analysis of the polynomial-time approximation scheme (PTAS) of Borradaile et al. [12] for the Euclidean Steiner forest problem. This is done by proving a new structural property and modifying the dynamic programming by adding a new piece of information to each dynamic programming state. Next we develop a PTAS for a well-motivated case, i.e., the multiplicative case, of prize-collecting and budgeted Steiner forest. The ideas used in the algorithm may have applications in design of a broad class of bicriteria PTASs. At the end, we demonstrate why PTASs for these problems can be hard in the general Euclidean case (and thus for PTASs we cannot go beyond the multiplicative case).
A Learning-Based Approach to Reactive Security
Venue: arXiv cs.CR 2009
Year: 2009

Despite the conventional wisdom that proactive security is superior to reactive security, we show that reactive security can be competitive with proactive security as long as the reactive defender learns from past attacks instead of myopically overreacting to the last attack. Our game-theoretic model follows common practice in the security literature by making worst-case assumptions about the attacker: we grant the attacker complete knowledge of the defender's strategy and do not require the attacker to act rationally. In this model, we bound the competitive ratio between a reactive defense algorithm (which is inspired by online learning theory) and the best fixed proactive defense. Additionally, we show that, unlike proactive defenses, this reactive strategy is robust to a lack of information about the attacker's incentives and knowledge.
Delay-Optimal Power and Subcarrier Allocation for OFDMA Systems via Stochastic Approximation
Venue: arXiv cs.LG 2009
Year: 2009

In this paper, we consider delay-optimal power and subcarrier allocation design for OFDMA systems with $N_F$ subcarriers, $K$ mobiles and one base station. There are $K$ queues at the base station for the downlink traffic to the $K$ mobiles with heterogeneous packet arrivals and delay requirements. We shall model the problem as a $K$-dimensional infinite horizon average reward Markov Decision Problem (MDP) where the control actions are assumed to be a function of the instantaneous Channel State Information (CSI) as well as the joint Queue State Information (QSI). This problem is challenging because it corresponds to a stochastic Network Utility Maximization (NUM) problem where general solution is still unknown. We propose an {\em online stochastic value iteration} solution using {\em stochastic approximation}. The proposed power control algorithm, which is a function of both the CSI and the QSI, takes the form of multi-level water-filling. We prove that under two mild conditions in Theorem 1 (One is the stepsize condition. The other is the condition on accessibility of the Markov Chain, which can be easily satisfied in most of the cases we are interested.), the proposed solution converges to the optimal solution almost surely (with probability 1) and the proposed framework offers a possible solution to the general stochastic NUM problem. By exploiting the birth-death structure of the queue dynamics, we obtain a reduced complexity decomposed solution with linear $\mathcal{O}(KN_F)$ complexity and $\mathcal{O}(K)$ memory requirement.
Communication of Science Shop Mediation: A Kaleidoscope of University-Society Relations
Venue: arXiv cs.CY 2009
Year: 2009

The Science Shop model was initiated in the Netherlands in the 1970s. Part of the model is the modest scale of the operation. The crucial idea behind the Science Shops involves a working relationship between knowledge-producing institutions like universities and citizen groups that need relevant questions answered. In providing this link, the relations between science and the public can be stimulated by providing such groups with access to the university and by offering active mediation of these questions. This research addresses the question of the external visibility of Science Shop work in terms of communications which reach beyond the local context of the participants. In addition to the question of the effects of this specific type of communication in terms of publications, institutional development, and curriculum development, we study the communication of the results in the press, the popular and grey literature, and other means of communication insofar as retrievable on distance through the Internet.