OpenRaiser/Intern-Atlas huggingface dataset:
We Can Remember It for You Wholesale: Implications of Data Remanence on the Use of RAM for True Random Number Generation on RFID Tags (RFIDSec 2009)
Venue: arXiv cs.CR 2009
Year: 2009

Random number generation is a fundamental security primitive for RFID devices. However, even this relatively simple requirement is beyond the capacity of today's average RFID tag. A recently proposed solution, Fingerprint Extraction and Random Number Generation in SRAM (FERNS) [14, 15], involves the use of onboard RAM as the source of "true" randomness. Unfortunately, practical considerations prevent this approach from reaching its full potential. First, this method must compete with other system functionalities for use of memory. Thus, the amount of uninitialized RAM available for utilization as a randomness generator may be severely restricted. Second, RAM is subject to data remanence; there is a time period after losing power during which stored data remains intact in memory. This means that after a portion of memory has been used for entropy collection once it will require a relatively extended period of time without power before it can be reused. In a usable RFID based security application, which requires multiple or long random numbers, this may lead to unacceptably high delays. In this paper, we show that data remanence negatively affects RAM based random number generation. We demonstrate the practical considerations that must be taken into account when using RAM as an entropy source. We also discuss the implementation of a true random number generator on Intel's WISP RFID tag, which is the first such implementation to the authors' best knowledge. By relating this to the requirements of some popular RFID authentication protocols, we assess the (im)practicality of utilizing memory based randomness techniques on resource constrained devices.
Augmenting Light Field to model Wave Optics effects
Venue: arXiv cs.CV 2009
Year: 2009

The ray-based 4D light field representation cannot be directly used to analyze diffractive or phase--sensitive optical elements. In this paper, we exploit tools from wave optics and extend the light field representation via a novel "light field transform". We introduce a key modification to the ray--based model to support the transform. We insert a "virtual light source", with potentially negative valued radiance for certain emitted rays. We create a look-up table of light field transformers of canonical optical elements. The two key conclusions are that (i) in free space, the 4D light field completely represents wavefront propagation via rays with real (positive as well as negative) valued radiance and (ii) at occluders, a light field composed of light field transformers plus insertion of (ray--based) virtual light sources represents resultant phase and amplitude of wavefronts. For free--space propagation, we analyze different wavefronts and coherence possibilities. For occluders, we show that the light field transform is simply based on a convolution followed by a multiplication operation. This formulation brings powerful concepts from wave optics to computer vision and graphics. We show applications in cubic-phase plate imaging and holographic displays.
Incorporating Integrity Constraints in Uncertain Databases
Venue: arXiv cs.DB 2009
Year: 2009

We develop an approach to incorporate additional knowledge, in the form of general purpose integrity constraints (ICs), to reduce uncertainty in probabilistic databases. While incorporating ICs improves data quality (and hence quality of answers to a query), it significantly complicates query processing. To overcome the additional complexity, we develop an approach to map an uncertain relation U with ICs to another uncertain relation U', that approximates the set of consistent worlds represented by U. Queries over U can instead be evaluated over U' achieving higher quality (due to reduced uncertainty in U') without additional complexity in query processing due to ICs. We demonstrate the effectiveness and scalability of our approach to large data-sets with complex constraints. We also present experimental results demonstrating the utility of incorporating integrity constraints in uncertain relations, in the context of an information extraction application.
Worst-case Compressibility of Discrete and Finite Distributions
Venue: arXiv cs.IT 2009
Year: 2009

In the worst-case distributed source coding (DSC) problem of [1], the smaller cardinality of the support-set describing the correlation in informant data, may neither imply that fewer informant bits are required nor that fewer informants need to be queried, to finish the data-gathering at the sink. It is important to formally address these observations for two reasons: first, to develop good worst-case information measures and second, to perform meaningful worst-case information-theoretic analysis of various distributed data-gathering problems. Towards this goal, we introduce the notions of bit-compressibility and informant-compressibility of support-sets. We consider DSC and distributed function computation problems and provide results on computing the bit- and informant- compressibilities regions of the support-sets as a function of their cardinality.
Fast search for Dirichlet process mixture models
Venue: arXiv cs.LG 2009
Year: 2009

Dirichlet process (DP) mixture models provide a flexible Bayesian framework for density estimation. Unfortunately, their flexibility comes at a cost: inference in DP mixture models is computationally expensive, even when conjugate distributions are used. In the common case when one seeks only a maximum a posteriori assignment of data points to clusters, we show that search algorithms provide a practical alternative to expensive MCMC and variational techniques. When a true posterior sample is desired, the solution found by search can serve as a good initializer for MCMC. Experimental results show that using these techniques is it possible to apply DP mixture models to very large data sets.
An Evolved Neural Controller for Bipdedal Walking with Dynamic Balance
Venue: arXiv cs.NE 2009
Year: 2009

We successfully evolved a neural network controller that produces dynamic walking in a simulated bipedal robot with compliant actuators, a difficult control problem. The evolutionary evaluation uses a detailed software simulation of a physical robot. We describe: 1) a novel theoretical method to encourage populations to evolve "around" local optima, which employs multiple demes and fitness functions of progressively increasing difficulty, and 2) the novel genetic representation of the neural controller.
BPDMN: A Conservative Extension of BPMN with Enhanced Data Representation Capabilities
Venue: arXiv cs.SE 2009
Year: 2009

The design of business processes involves the usage of modeling languages, tools and methodologies. In this paper we highlight and address a relevant limitation of the Business Process Modeling Notation (BPMN): its weak data representation capabilities. In particular, we extend it with data-specific constructs derived from existing data modeling notations and adapted to blend gracefully into BPMN diagrams. The extension has been developed taking existing modeling languages and requirement analyses into account: we characterize our notation using the Workfl ow Data Patterns and provide mappings to the main XML-based business process languages.
Distributed Opportunistic Scheduling With Two-Level Probing
Venue: arXiv cs.IT 2009
Year: 2009

Distributed opportunistic scheduling (DOS) is studied for wireless ad-hoc networks in which many links contend for the channel using random access before data transmissions. Simply put, DOS involves a process of joint channel probing and distributed scheduling for ad-hoc (peer-to-peer) communications. Since, in practice, link conditions are estimated with noisy observations, the transmission rate has to be backed off from the estimated rate to avoid transmission outages. Then, a natural question to ask is whether it is worthwhile for the link with successful contention to perform further channel probing to mitigate estimation errors, at the cost of additional probing. Thus motivated, this work investigates DOS with two-level channel probing by optimizing the tradeoff between the throughput gain from more accurate rate estimation and the resulting additional delay. Capitalizing on optimal stopping theory with incomplete information, we show that the optimal scheduling policy is threshold-based and is characterized by either one or two thresholds, depending on network settings. Necessary and sufficient conditions for both cases are rigorously established. In particular, our analysis reveals that performing second-level channel probing is optimal when the first-level estimated channel condition falls in between the two thresholds. Numerical results are provided to illustrate the effectiveness of the proposed DOS with two-level channel probing. We also extend our study to the case with limited feedback, where the feedback from the receiver to its transmitter takes the form of (0,1,e).
Related terms search based on WordNet / Wiktionary and its application in Ontology Matching
Venue: arXiv cs.IR 2009
Year: 2009

A set of ontology matching algorithms (for finding correspondences between concepts) is based on a thesaurus that provides the source data for the semantic distance calculations. In this wiki era, new resources may spring up and improve this kind of semantic search. In the paper a solution of this task based on Russian Wiktionary is compared to WordNet based algorithms. Metrics are estimated using the test collection, containing 353 English word pairs with a relatedness score assigned by human evaluators. The experiment shows that the proposed method is capable in principle of calculating a semantic distance between pair of words in any language presented in Russian Wiktionary. The calculation of Wiktionary based metric had required the development of the open-source Wiktionary parser software.
GMap: Drawing Graphs as Maps
Venue: arXiv cs.CG 2009
Year: 2009

Information visualization is essential in making sense out of large data sets. Often, high-dimensional data are visualized as a collection of points in 2-dimensional space through dimensionality reduction techniques. However, these traditional methods often do not capture well the underlying structural information, clustering, and neighborhoods. In this paper, we describe GMap: a practical tool for visualizing relational data with geographic-like maps. We illustrate the effectiveness of this approach with examples from several domains All the maps referenced in this paper can be found in http://www.research.att.com/~yifanhu/GMap
Multiple-Input Multiple-Output Gaussian Broadcast Channels with Common and Confidential Messages
Venue: arXiv cs.IT 2009
Year: 2009

This paper considers the problem of the multiple-input multiple-output (MIMO) Gaussian broadcast channel with two receivers (receivers 1 and 2) and two messages: a common message intended for both receivers and a confidential message intended only for receiver 1 but needing to be kept asymptotically perfectly secure from receiver 2. A matrix characterization of the secrecy capacity region is established via a channel enhancement argument. The enhanced channel is constructed by first splitting receiver 1 into two virtual receivers and then enhancing only the virtual receiver that decodes the confidential message. The secrecy capacity region of the enhanced channel is characterized using an extremal entropy inequality previously established for characterizing the capacity region of a degraded compound MIMO Gaussian broadcast channel.
On Cyclic and Nearly Cyclic Multiagent Interactions in the Plane
Venue: arXiv cs.MA 2009
Year: 2009

We discuss certain types of cyclic and nearly cyclic interactions among N "point"-agents in the plane, leading to formations of interesting limiting geometric configurations. Cyclic pursuit and local averaging interactions have been analyzed in the context of multi-agent gathering. In this paper, we consider some nearly cyclic interactions that break symmetry leading to factor circulants rather than circulant interaction matrices.
On some counting problems for semi-linear sets
Venue: arXiv cs.DM 2009
Year: 2009

Let $X$ be a subset of $\N^t$ or $\Z^t$. We can associate with $X$ a function ${\cal G}_X:\N^t\longrightarrow\N$ which returns, for every $(n_1, ..., n_t)\in \N^t$, the number ${\cal G}_X(n_1, ..., n_t)$ of all vectors $x\in X$ such that, for every $i=1,..., t, |x_{i}| \leq n_{i}$. This function is called the {\em growth function} of $X$. The main result of this paper is that the growth function of a semi-linear set of $\N^t$ or $\Z^t$ is a box spline. By using this result and some theorems on semi-linear sets, we give a new proof of combinatorial flavour of a well-known theorem by Dahmen and Micchelli on the counting function of a system of Diophantine linear equations.
On the Convergence of Population Protocols When Population Goes to Infinity
Venue: arXiv cs.DC 2009
Year: 2009

Population protocols have been introduced as a model of sensor networks consisting of very limited mobile agents with no control over their own movement. A population protocol corresponds to a collection of anonymous agents, modeled by finite automata, that interact with one another to carry out computations, by updating their states, using some rules. Their computational power has been investigated under several hypotheses but always when restricted to finite size populations. In particular, predicates stably computable in the original model have been characterized as those definable in Presburger arithmetic. We study mathematically the convergence of population protocols when the size of the population goes to infinity. We do so by giving general results, that we illustrate through the example of a particular population protocol for which we even obtain an asymptotic development. This example shows in particular that these protocols seem to have a rather different computational power when a huge population hypothesis is considered.
Parallel AdaBoost Algorithm for Gabor Wavelet Selection in Face Recognition
Venue: arXiv cs.CV 2009
Year: 2009

In this paper, the problem of automatic Gabor wavelet selection for face recognition is tackled by introducing an automatic algorithm based on Parallel AdaBoosting method. Incorporating mutual information into the algorithm leads to the selection procedure not only based on classification accuracy but also on efficiency. Effective image features are selected by using properly chosen Gabor wavelets optimised with Parallel AdaBoost method and mutual information to get high recognition rates with low computational cost. Experiments are conducted using the well-known FERET face database. In proposed framework, memory and computation costs are reduced significantly and high classification accuracy is obtained.
A certifying algorithm for 3-colorability of P5-free graphs
Venue: arXiv cs.DM 2009
Year: 2009

We provide a certifying algorithm for the problem of deciding whether a P5- free graph is 3-colorable by showing there are exactly six finite graphs that are P5-free and not 3-colorable and minimal with respect to this property.
Message Passing Algorithms for Compressed Sensing
Venue: arXiv cs.IT 2009
Year: 2009

Compressed sensing aims to undersample certain high-dimensional signals, yet accurately reconstruct them by exploiting signal characteristics. Accurate reconstruction is possible when the object to be recovered is sufficiently sparse in a known basis. Currently, the best known sparsity-undersampling tradeoff is achieved when reconstructing by convex optimization -- which is expensive in important large-scale applications. Fast iterative thresholding algorithms have been intensively studied as alternatives to convex optimization for large-scale problems. Unfortunately known fast algorithms offer substantially worse sparsity-undersampling tradeoffs than convex optimization. We introduce a simple costless modification to iterative thresholding making the sparsity-undersampling tradeoff of the new algorithms equivalent to that of the corresponding convex optimization procedures. The new iterative-thresholding algorithms are inspired by belief propagation in graphical models. Our empirical measurements of the sparsity-undersampling tradeoff for the new algorithms agree with theoretical calculations. We show that a state evolution formalism correctly derives the true sparsity-undersampling tradeoff. There is a surprising agreement between earlier calculations based on random convex polytopes and this new, apparently very different theoretical formalism.
Recovering Signals from Lowpass Data
Venue: arXiv cs.IT 2009
Year: 2009

The problem of recovering a signal from its low frequency components occurs often in practical applications due to the lowpass behavior of many physical systems. Here we study in detail conditions under which a signal can be determined from its low-frequency content. We focus on signals in shift-invariant spaces generated by multiple generators. For these signals, we derive necessary conditions on the cutoff frequency of the lowpass filter as well as necessary and sufficient conditions on the generators such that signal recovery is possible. When the lowpass content is not sufficient to determine the signal, we propose appropriate pre-processing that can improve the reconstruction ability. In particular, we show that modulating the signal with one or more mixing functions prior to lowpass filtering, can ensure the recovery of the signal in many cases, and reduces the necessary bandwidth of the filter.
Web of Lossy Adapters for Interface Interoperability: An Algorithm and NP-completeness of Minimization
Venue: arXiv cs.SE 2009
Year: 2009

By using different interface adapters for different methods, it is possible to construct a maximally covering web of interface adapters which incurs minimum loss during interface adaptation. We introduce a polynomial-time algorithm that can achieve this. However, we also show that minimizing the number of adapters included in a maximally covering web of interface adapters is an NP-complete problem.
Optimal Routing and Power Control for a Single Cell, Dense, Ad Hoc Wireless Network
Venue: arXiv cs.NI 2009
Year: 2009

We consider a dense, ad hoc wireless network, confined to a small region. The wireless network is operated as a single cell, i.e., only one successful transmission is supported at a time. Data packets are sent between sourcedestination pairs by multihop relaying. We assume that nodes self-organise into a multihop network such that all hops are of length d meters, where d is a design parameter. There is a contention based multiaccess scheme, and it is assumed that every node always has data to send, either originated from it or a transit packet (saturation assumption). In this scenario, we seek to maximize a measure of the transport capacity of the network (measured in bit-meters per second) over power controls (in a fading environment) and over the hop distance d, subject to an average power constraint. We first argue that for a dense collection of nodes confined to a small region, single cell operation is efficient for single user decoding transceivers. Then, operating the dense ad hoc wireless network (described above) as a single cell, we study the hop length and power control that maximizes the transport capacity for a given network power constraint.
Interchanging distance and capacity in probabilistic mappings
Venue: arXiv cs.DS 2009
Year: 2009

Harald Racke [STOC 2008] described a new method to obtain hierarchical decompositions of networks in a way that minimizes the congestion. Racke's approach is based on an equivalence that he discovered between minimizing congestion and minimizing stretch (in a certain setting). Here we present Racke's equivalence in an abstract setting that is more general than the one described in Racke's work, and clarifies the power of Racke's result. In addition, we present a related (but different) equivalence that was developed by Yuval Emek [ESA 2009] and is only known to apply to planar graphs.
Self-adaptive web intrusion detection system
Venue: arXiv cs.NI 2009
Year: 2009

The evolution of the web server contents and the emergence of new kinds of intrusions make necessary the adaptation of the intrusion detection systems (IDS). Nowadays, the adaptation of the IDS requires manual -- tedious and unreactive -- actions from system administrators. In this paper, we present a self-adaptive intrusion detection system which relies on a set of local model-based diagnosers. The redundancy of diagnoses is exploited, online, by a meta-diagnoser to check the consistency of computed partial diagnoses, and to trigger the adaptation of defective diagnoser models (or signatures) in case of inconsistency. This system is applied to the intrusion detection from a stream of HTTP requests. Our results show that our system 1) detects intrusion occurrences sensitively and precisely, 2) accurately self-adapts diagnoser model, thus improving its detection accuracy.
USUM: Update Summary Generation System
Venue: arXiv cs.IR 2009
Year: 2009

Huge amount of information is present in the World Wide Web and a large amount is being added to it frequently. A query-specific summary of multiple documents is very helpful to the user in this context. Currently, few systems have been proposed for query-specific, extractive multi-document summarization. If a summary is available for a set of documents on a given query and if a new document is added to the corpus, generating an updated summary from the scratch is time consuming and many a times it is not practical/possible. In this paper we propose a solution to this problem. This is especially useful in a scenario where the source documents are not accessible. We cleverly embed the sentences of the current summary into the new document and then perform query-specific summary generation on that document. Our experimental results show that the performance of the proposed approach is good in terms of both quality and efficiency.
The Living Application: a Self-Organising System for Complex Grid Tasks
Venue: arXiv cs.DC 2009
Year: 2009

We present the living application, a method to autonomously manage applications on the grid. During its execution on the grid, the living application makes choices on the resources to use in order to complete its tasks. These choices can be based on the internal state, or on autonomously acquired knowledge from external sensors. By giving limited user capabilities to a living application, the living application is able to port itself from one resource topology to another. The application performs these actions at run-time without depending on users or external workflow tools. We demonstrate this new concept in a special case of a living application: the living simulation. Today, many simulations require a wide range of numerical solvers and run most efficiently if specialized nodes are matched to the solvers. The idea of the living simulation is that it decides itself which grid machines to use based on the numerical solver currently in use. In this paper we apply the living simulation to modelling the collision between two galaxies in a test setup with two specialized computers. This simulation switces at run-time between a GPU-enabled computer in the Netherlands and a GRAPE-enabled machine that resides in the United States, using an oct-tree N-body code whenever it runs in the Netherlands and a direct N-body solver in the United States.