OpenRaiser/Intern-Atlas huggingface dataset:
Reversible Language Extensions and their Application in Debugging
Venue: arXiv cs.PL 2013
Year: 2013

A range of methodologies and techniques are available to guide the design and implementation of language extensions and domain-specific languages. A simple yet powerful technique is based on source-to-source transformations interleaved across the compilation passes of a base language. Despite being a successful approach, it has the main drawback that the input source code is lost in the process. When considering the whole workflow of program development (warning and error reporting, debugging, or even program analysis), program translations are no more powerful than a glorified macro language. In this paper, we propose an augmented approach to language extensions for Prolog, where symbolic annotations are included in the target program. These annotations allow selectively reversing the translated code. We illustrate the approach by showing that coupling it with minimal extensions to a generic Prolog debugger allows us to provide users with a familiar, source-level view during the debugging of programs which use a variety of language extensions, such as functional notation, DCGs, or CLP{Q,R}.
Fixed-to-Variable Length Distribution Matching
Venue: arXiv cs.IT 2013
Year: 2013

Fixed-to-variable length (f2v) matchers are used to reversibly transform an input sequence of independent and uniformly distributed bits into an output sequence of bits that are (approximately) independent and distributed according to a target distribution. The degree of approximation is measured by the informational divergence between the output distribution and the target distribution. An algorithm is developed that efficiently finds optimal f2v codes. It is shown that by encoding the input bits blockwise, the informational divergence per bit approaches zero as the block length approaches infinity. A relation to data compression by Tunstall coding is established.
Deadline is not Enough: How to Achieve Importance-aware Server-centric Data Centers via a Cross Layer Approach
Venue: arXiv cs.DC 2013
Year: 2013

Today's datacenters face important challenges for providing low-latency high-quality interactive services to meet user's expectation. For improving the application throughput, recent research works have embedded application deadline information into design of network flow schedule to meet the latency requirement. Here, arises a critical question: does application-level throughput mean providing better quality service? We note that there are usually a set of semantic related responses (or flows) for answering a query; and, some responses are highly correlative with the query while others do not. Thus, this observation motivates us to associate the importance of the contents with the application flows (or responses) in order to enhance the service quality. We first model the application importance maximization problem in a generic network and in a server-centric network. Since both of them are too complicated to be deployed in the real world, we propose the importance-aware delivery protocol, which is a distributed event-driven rate-based delivery control protocol, for server-centric datacenter networks. The proposed protocol is able to make use of the multiple disjoin paths of server-centric network, and jointly consider flow importance, flow size, and deadline to maximize the goodput of most-related semantic data of a query. Through real-data-based or synthetic simulations, the results show that our proposed protocol significantly outperforms D3 and MPTCP in terms of the precision at K and the sum of application-level importance.
Comparison between the two definitions of AI
Venue: arXiv cs.AI 2013
Year: 2013

Two different definitions of the Artificial Intelligence concept have been proposed in papers [1] and [2]. The first definition is informal. It says that any program that is cleverer than a human being, is acknowledged as Artificial Intelligence. The second definition is formal because it avoids reference to the concept of human being. The readers of papers [1] and [2] might be left with the impression that both definitions are equivalent and the definition in [2] is simply a formal version of that in [1]. This paper will compare both definitions of Artificial Intelligence and, hopefully, will bring a better understanding of the concept.
New Dimension Value Introduction for In-Memory What-If Analysis
Venue: arXiv cs.DB 2013
Year: 2013

OLAP systems operate on historical data and provide answers to analysts queries. Recent in-memory implementations provide significant performance improvement for real time ad-hoc analysis. Philosophy and techniques of what-if analysis on data warehouse and in-memory data store based OLAP systems have been covered in great detail before but exploration of new dimension value (attribute) introduction has been limited in the context of what-if analysis. We extend the approach of Andrey Balmin et al of using select modify operator on data graph to introduce new values for dimensions and measures in a read-only in-memory data store as scenarios. Our system constructs scenarios without materializing the rows and stores the row information as queries. The rows associated with the scenarios are constructed as and when required by an ad-hoc query.
The weight distributions of some cyclic codes with three or four nonzeros over F3
Venue: arXiv cs.IT 2013
Year: 2013

Because of efficient encoding and decoding algorithms, cyclic codes are an important family of linear block codes, and have applications in communica- tion and storage systems. However, their weight distributions are known only for a few cases mainly on the codes with one or two nonzeros. In this paper, the weight distributions of two classes of cyclic codes with three or four nonzeros are determined.
Benchmarking some Portuguese S&T system research units: 2nd Edition
Venue: arXiv cs.DL 2013
Year: 2013

The increasing use of productivity and impact metrics for evaluation and comparison, not only of individual researchers but also of institutions, universities and even countries, has prompted the development of bibliometrics. Currently, metrics are becoming widely accepted as an easy and balanced way to assist the peer review and evaluation of scientists and/or research units, provided they have adequate precision and recall. This paper presents a benchmarking study of a selected list of representative Portuguese research units, based on a fairly complete set of parameters: bibliometric parameters, number of competitive projects and number of PhDs produced. The study aimed at collecting productivity and impact data from the selected research units in comparable conditions i.e., using objective metrics based on public information, retrievable on-line and/or from official sources and thus verifiable and repeatable. The study has thus focused on the activity of the 2003-06 period, where such data was available from the latest official evaluation. The main advantage of our study was the application of automatic tools, achieving relevant results at a reduced cost. Moreover, the results over the selected units suggest that this kind of analyses will be very useful to benchmark scientific productivity and impact, and assist peer review.
Set-Membership Constrained Conjugate Gradient Beamforming Algorithms
Venue: arXiv cs.IT 2013
Year: 2013

In this work a constrained adaptive filtering strategy based on conjugate gradient (CG) and set-membership (SM) techniques is presented for adaptive beamforming. A constraint on the magnitude of the array output is imposed to derive an adaptive algorithm that performs data-selective updates when calculating the beamformer's parameters. We consider a linearly constrained minimum variance (LCMV) optimization problem with the bounded constraint based on this strategy and propose a CG type algorithm for implementation. The proposed algorithm has data-selective updates, a variable forgetting factor and performs one iteration per update to reduce the computational complexity. The updated parameters construct a space of feasible solutions that enforce the constraints. We also introduce two time-varying bounding schemes to measure the quality of the parameters that could be included in the parameter space. A comprehensive complexity and performance analysis between the proposed and existing algorithms are provided. Simulations are performed to show the enhanced convergence and tracking performance of the proposed algorithm as compared to existing techniques.
Correcting Camera Shake by Incremental Sparse Approximation
Venue: arXiv cs.CV 2013
Year: 2013

The problem of deblurring an image when the blur kernel is unknown remains challenging after decades of work. Recently there has been rapid progress on correcting irregular blur patterns caused by camera shake, but there is still much room for improvement. We propose a new blind deconvolution method using incremental sparse edge approximation to recover images blurred by camera shake. We estimate the blur kernel first from only the strongest edges in the image, then gradually refine this estimate by allowing for weaker and weaker edges. Our method competes with the benchmark deblurring performance of the state-of-the-art while being significantly faster and easier to generalize.
Orbit Problem Revisited
Venue: arXiv cs.CC 2013
Year: 2013

In this letter, we revisit the {\em orbit problem}, which was studied in \cite{HAR69,SHA79,KL86}. In \cite{KL86}, Kannan and Lipton proved that this problem is decidable in polynomial time. In this paper, we study the {\em approximate orbit problem}, and show that this problem is decidable except for one case.
Wireless Information and Power Transfer: A Dynamic Power Splitting Approach
Venue: arXiv cs.IT 2013
Year: 2013

Scavenging energy from ambient radio signals, namely wireless energy harvesting (WEH), has recently drawn significant attention. In this paper, we consider a point-to-point wireless link over the flat-fading channel, where the receiver replenishes energy via WEH from the signals sent by the transmitter. We consider a SISO (single-input single-output) system where the single-antenna receiver cannot decode information and harvest energy independently from the same signal received. Under this practical constraint, we propose a dynamic power splitting (DPS) scheme, where the received signal is split into two streams with adjustable power levels for information decoding and energy harvesting separately based on the instantaneous channel condition that is assumed to be known at the receiver. We derive the optimal power splitting rule at the receiver to achieve various trade-offs between the maximum ergodic capacity for information transfer and the maximum average harvested energy for power transfer. Moreover, for the case when the channel state information is also known at the transmitter, we investigate the joint optimization of transmitter power control and receiver power splitting. Finally, we extend the result for DPS to the SIMO (single-input multiple-output) system and investigate a low-complexity power splitting scheme termed antenna switching.
Outage Capacity for the Optical MIMO Channel
Venue: arXiv cs.IT 2013
Year: 2013

MIMO processing techniques in fiber optical communications have been proposed as a promising approach to meet increasing demand for information throughput. In this context, the multiple channels correspond to the multiple modes and/or multiple cores in the fiber. In this paper we characterize the distribution of the mutual information with Gaussian input in a simple channel model for this system. Assuming significant cross talk between cores, negligible backscattering and near-lossless propagation in the fiber, we model the transmission channel as a random complex unitary matrix. The loss in the transmission may be parameterized by a number of unutilized channels in the fiber. We analyze the system in a dual fashion. First, we evaluate a closed-form expression for the outage probability, which is handy for small matrices. We also apply the asymptotic approach, in particular the Coulomb gas method from statistical mechanics, to obtain closed-form results for the ergodic mutual information, its variance as well as the outage probability for Gaussian input in the limit of large number of cores/modes. By comparing our analytic results to simulations, we see that, despite the fact that this method is nominally valid for large number of modes, our method is quite accurate even for small to modest number of channels.
Multi-scale Visual Attention & Saliency Modelling with Decision Theory
Venue: arXiv cs.CV 2013
Year: 2013

Bottom-up saliency, an early human visual processing, behaves like binary classification of interest and null hypothesis. Its discriminant power, mutual information of image features and class distribution, is closely related to saliency value by the well-known centre-surround theory. As classification accuracy very much depends on window sizes, the discriminant saliency (power) varies according to sampling scales. Discriminating power estimation in multi-scales framework needs integrating with wavelet transformation and then estimating statistical discrepancy of two consecutive scales (centre-surround windows) by Hidden Markov Tree (HMT) model. Finally, multi-scale discriminant saliency (MDIS) maps are combined by the maximum information rule to synthesize a final saliency map. All MDIS maps are evaluated with standard quantitative tools (NSS,LCC,AUC) on N.Bruce's database with ground truth data as eye-tracking locations ; as well assessed qualitatively by visual examination of individual cases. For evaluating MDIS against well-known AIM saliency method, simulations are needed and described in details with several interesting conclusions, drawn for further research directions.
Safe Schedulability of Bounded-Rate Multi-Mode Systems
Venue: arXiv cs.LO 2013
Year: 2013

Bounded-rate multi-mode systems (BMMS) are hybrid systems that can switch freely among a finite set of modes, and whose dynamics is specified by a finite number of real-valued variables with mode-dependent rates that can vary within given bounded sets. The schedulability problem for BMMS is defined as an infinite-round game between two players---the scheduler and the environment---where in each round the scheduler proposes a time and a mode while the environment chooses an allowable rate for that mode, and the state of the system changes linearly in the direction of the rate vector. The goal of the scheduler is to keep the state of the system within a pre-specified safe set using a non-Zeno schedule, while the goal of the environment is the opposite. Green scheduling under uncertainty is a paradigmatic example of BMMS where a winning strategy of the scheduler corresponds to a robust energy-optimal policy. We present an algorithm to decide whether the scheduler has a winning strategy from an arbitrary starting state, and give an algorithm to compute such a winning strategy, if it exists. We show that the schedulability problem for BMMS is co-NP complete in general, but for two variables it is in PTIME. We also study the discrete schedulability problem where the environment has only finitely many choices of rate vectors in each mode and the scheduler can make decisions only at multiples of a given clock period, and show it to be EXPTIME-complete.
Decomposition by Partial Linearization: Parallel Optimization of Multi-Agent Systems
Venue: arXiv cs.IT 2013
Year: 2013

We propose a novel decomposition framework for the distributed optimization of general nonconvex sum-utility functions arising naturally in the system design of wireless multiuser interfering systems. Our main contributions are: i) the development of the first class of (inexact) Jacobi best-response algorithms with provable convergence, where all the users simultaneously and iteratively solve a suitably convexified version of the original sum-utility optimization problem; ii) the derivation of a general dynamic pricing mechanism that provides a unified view of existing pricing schemes that are based, instead, on heuristics; and iii) a framework that can be easily particularized to well-known applications, giving rise to very efficient practical (Jacobi or Gauss-Seidel) algorithms that outperform existing adhoc methods proposed for very specific problems. Interestingly, our framework contains as special cases well-known gradient algorithms for nonconvex sum-utility problems, and many blockcoordinate descent schemes for convex functions.
On the Fundamental Feedback-vs-Performance Tradeoff over the MISO-BC with Imperfect and Delayed CSIT
Venue: arXiv cs.IT 2013
Year: 2013

This work considers the multiuser multiple-input single-output (MISO) broadcast channel (BC), where a transmitter with M antennas transmits information to K single-antenna users, and where - as expected - the quality and timeliness of channel state information at the transmitter (CSIT) is imperfect. Motivated by the fundamental question of how much feedback is necessary to achieve a certain performance, this work seeks to establish bounds on the tradeoff between degrees-of-freedom (DoF) performance and CSIT feedback quality. Specifically, this work provides a novel DoF region outer bound for the general K-user MISO BC with partial current CSIT, which naturally bridges the gap between the case of having no current CSIT (only delayed CSIT, or no CSIT) and the case with full CSIT. The work then characterizes the minimum CSIT feedback that is necessary for any point of the sum DoF, which is optimal for the case with M >= K, and the case with M=2, K=3.
Security and Privacy Issues in Wireless Mesh Networks: A Survey
Venue: arXiv cs.CR 2013
Year: 2013

This book chapter identifies various security threats in wireless mesh network (WMN). Keeping in mind the critical requirement of security and user privacy in WMNs, this chapter provides a comprehensive overview of various possible attacks on different layers of the communication protocol stack for WMNs and their corresponding defense mechanisms. First, it identifies the security vulnerabilities in the physical, link, network, transport, application layers. Furthermore, various possible attacks on the key management protocols, user authentication and access control protocols, and user privacy preservation protocols are presented. After enumerating various possible attacks, the chapter provides a detailed discussion on various existing security mechanisms and protocols to defend against and wherever possible prevent the possible attacks. Comparative analyses are also presented on the security schemes with regards to the cryptographic schemes used, key management strategies deployed, use of any trusted third party, computation and communication overhead involved etc. The chapter then presents a brief discussion on various trust management approaches for WMNs since trust and reputation-based schemes are increasingly becoming popular for enforcing security in wireless networks. A number of open problems in security and privacy issues for WMNs are subsequently discussed before the chapter is finally concluded.
A Combination Framework for Complexity
Venue: arXiv cs.CC 2013
Year: 2013

In this paper we present a combination framework for polynomial complexity analysis of term rewrite systems. The framework covers both derivational and runtime complexity analysis. We present generalisations of powerful complexity techniques, notably a generalisation of complexity pairs and (weak) dependency pairs. Finally, we also present a novel technique, called dependency graph decomposition, that in the dependency pair setting greatly increases modularity. We employ the framework in the automated complexity tool TCT. TCT implements a majority of the techniques found in the literature, witnessing that our framework is general enough to capture a very brought setting.
Block-to-Block Distribution Matching
Venue: arXiv cs.IT 2013
Year: 2013

In this work, binary block-to-block distribution matching is considered. m independent and uniformly distributed bits are mapped to n output bits resembling a target product distribution. A rate R is called achieved by a sequence of encoder-decoder pairs, if for m,n to infinity, (1) m/n approaches R, (2) the informational divergence per bit of the output distribution and the target distribution goes to zero, and (3) the probability of erroneous decoding goes to zero. It is shown that the maximum achievable rate is equal to the entropy of the target distribution. A practical encoder-decoder pair is constructed that provably achieves the maximum rate in the limit. Numerical results illustrate that the suggested system operates close to the limits with reasonable complexity. The key idea is to internally use a fixed-to-variable length matcher and to compensate underflow by random mapping and to cast an error when overflow occurs.
Open Access, library and publisher competition, and the evolution of general commerce
Venue: arXiv cs.DL 2013
Year: 2013

Discussions of the economics of scholarly communication are usually devoted to Open Access, rising journal prices, publisher profits, and boycotts. That ignores what seems a much more important development in this market. Publishers, through the oft-reviled "Big Deal" packages, are providing much greater and more egalitarian access to the journal literature, an approximation to true Open Access. In the process they are also marginalizing libraries, and obtaining a greater share of the resources going into scholarly communication. This is enabling a continuation of publisher profits as well as of what for decades has been called "unsustainable journal price escalation". It is also inhibiting the spread of Open Access, and potentially leading to an oligopoly of publishers controlling distribution through large-scale licensing. The "Big Deal" practices are worth studying for several general reasons. The degree to which publishers succeed in diminishing the role of libraries may be an indicator of the degree and speed at which universities transform themselves. More importantly, these "Big Deals" appear to point the way to the future of the whole economy, where progress is characterized by declining privacy, increasing price discrimination, increasing opaqueness in pricing, increasing reliance on low-paid or upaid work of others for profits, and business models that depend on customer inertia.
Design-Efficiency in Security
Venue: arXiv cs.CR 2013
Year: 2013

In this document, we present our applied results on balancing security and performance using a running example, which is based on sensor networks. These results are forming a basis for a new approach to balance security and performance, and therefore provide design-efficiency of key updates. We employ probabilistic model checking approach and present our modelling and analysis study using PRISM model checker.
Overview of EIREX 2012: Social Media
Venue: arXiv cs.IR 2013
Year: 2013

The third Information Retrieval Education through EXperimentation track (EIREX 2012) was run at the University Carlos III of Madrid, during the 2012 spring semester. EIREX 2012 is the third in a series of experiments designed to foster new Information Retrieval (IR) education methodologies and resources, with the specific goal of teaching undergraduate IR courses from an experimental perspective. For an introduction to the motivation behind the EIREX experiments, see the first sections of [Urbano et al., 2011a]. For information on other editions of EIREX and related data, see the website at http://ir.kr.inf.uc3m.es/eirex/. The EIREX series have the following goals: a) to help students get a view of the Information Retrieval process as they would find it in a real-world scenario, either industrial or academic; b) to make students realize the importance of laboratory experiments in Computer Science and have them initiated in their execution and analysis; c) to create a public repository of resources to teach Information Retrieval courses; d) to seek the collaboration and active participation of other Universities in this endeavor. This overview paper summarizes the results of the EIREX 2012 track, focusing on the creation of the test collection and the analysis to assess its reliability.