OpenRaiser/Intern-Atlas huggingface dataset:
A Vehicle for Research: Using Street Sweepers to Explore the Landscape of Environmental Community Action
Venue: arXiv cs.HC 2009
Year: 2009

Researchers are developing mobile sensing platforms to facilitate public awareness of environmental conditions. However, turning such awareness into practical community action and political change requires more than just collecting and presenting data. To inform research on mobile environmental sensing, we conducted design fieldwork with government, private, and public interest stakeholders. In parallel, we built an environmental air quality sensing system and deployed it on street sweeping vehicles in a major U.S. city; this served as a "research vehicle" by grounding our interviews and affording us status as environmental action researchers. In this paper, we present a qualitative analysis of the landscape of environmental action, focusing on insights that will help researchers frame meaningful technological interventions.
Optimal Embedding Into Star Metrics
Venue: arXiv cs.DS 2009
Year: 2009

We present an O(n^3 log^2 n)-time algorithm for the following problem: given a finite metric space X, create a star-topology network with the points of X as its leaves, such that the distances in the star are at least as large as in X, with minimum dilation. As part of our algorithm, we solve in the same time bound the parametric negative cycle detection problem: given a directed graph with edge weights that are increasing linear functions of a parameter lambda, find the smallest value of lambda such that the graph contains no negative-weight cycles.
Diversity-Multiplexing tradeoff of the Two-User Interference Channel
Venue: arXiv cs.IT 2009
Year: 2009

Diversity-Multiplexing tradeoff (DMT) is a coarse high SNR approximation of the fundamental tradeoff between data rate and reliability in a slow fading channel. In this paper, we characterize the fundamental DMT of the two user single antenna Gaussian interference channel. We show that the class of multilevel superposition coding schemes universally achieves (for all fading statistics) the DMT for the two-user interference channel. For the special case of symmetric DMT, when the two users have identical rate and diversity gain requirements, we characterize the DMT achieved by the Han-Kobayashi scheme, which corresponds to two level superposition coding.
Two-Level Fingerprinting Codes
Venue: arXiv cs.IT 2009
Year: 2009

We introduce the notion of two-level fingerprinting and traceability codes. In this setting, the users are organized in a hierarchical manner by classifying them into various groups; for instance, by dividing the distribution area into several geographic regions, and collecting users from the same region into one group. Two-level fingerprinting and traceability codes have the following property: As in traditional (one-level) codes, when given an illegal copy produced by a coalition of users, the decoder identifies one of the guilty users if the coalition size is less than a certain threshold $t$. Moreover, even when the coalition is of a larger size $s$ $(> t)$, the decoder still provides partial information by tracing one of the groups containing a guilty user. We establish sufficient conditions for a code to possess the two-level traceability property. In addition, we also provide constructions for two-level fingerprinting codes and characterize the corresponding set of achievable rates.
Selective Cooperative Relaying over Time-Varying Channels
Venue: arXiv cs.IT 2009
Year: 2009

In selective cooperative relaying only a single relay out of the set of available relays is activated, hence the available power and bandwidth resources are efficiently utilized. However, implementing selective cooperative relaying in time-varying channels may cause frequent relay switchings that deteriorate the overall performance. In this paper, we study the rate at which a relay switching occurs in selective cooperative relaying applications in time-varying fading channels. In particular, we derive closed-form expressions for the relay switching rate (measured in Hz) for opportunistic relaying (OR) and distributed switch and stay combining (DSSC). Additionally, expressions for the average relay activation time for both of the considered schemes are also provided, reflecting the average time that a selected relay remains active until a switching occurs. Numerical results manifest that DSSC yields considerably lower relay switching rates than OR, along with larger average relay activation times, rendering it a better candidate for implementation of relay selection in fast fading environments.
Quantization for Soft-Output Demodulators in Bit-Interleaved Coded Modulation Systems
Venue: arXiv cs.IT 2009
Year: 2009

We study quantization of log-likelihood ratios (LLR) in bit-interleaved coded modulation (BICM) systems in terms of an equivalent discrete channel. We propose to design the quantizer such that the quantizer outputs become equiprobable. We investigate semi-analytically and numerically the ergodic and outage capacity over single- and multiple-antenna channels for different quantizers. Finally, we show bit error rate simulations for BICM systems with LLR quantization using a rate 1/2 low-density parity-check code.
Optimization of Energy Efficient Transmission in Underwater Sensor Networks
Venue: arXiv cs.NI 2009
Year: 2009

Underwater communication is a challenging topic due to its singular channel characteristics. Most protocols used in terrestrial wireless communication can not be directly applied in the underwater world. In this paper, we focus on the issue of energy efficient transmission in underwater sensor networks (UWSNs) and analyze this problem in a rigorous and theoretical way. We formalize an optimization problem which aims to minimize energy consumption and simultaneously accounts for other performance metrics such as the data reliability and the communication delay. With the help of Karush-Kuhn-Tucker conditions (KKT conditions), we derive a simple and explicit, but nevertheless accurate, approximate solution under reasonable assumptions. This approximate solution provides theoretical guidelines for designing durable and reliable UWSNs. Our result also shows that reliability and communication delay are crucial factors to the energy consumption for transmission.
Decomposing Coverings and the Planar Sensor Cover Problem
Venue: arXiv cs.CG 2009
Year: 2009

We show that a $k$-fold covering using translates of an arbitrary convex polygon can be decomposed into $Ω(k)$ covers (using an efficient algorithm). We generalize this result to obtain a constant factor approximation to the sensor cover problem where the ranges of the sensors are translates of a given convex polygon. The crucial ingredient in this generalization is a constant factor approximation algorithm for a one-dimensional version of the sensor cover problem, called the Restricted Strip Cover (RSC) problem, where sensors are intervals of possibly different lengths. Our algorithm for RSC improves on the previous $O(\log \log \log n)$ approximation.
Reliable Process for Security Policy Deployment
Venue: arXiv cs.CR 2009
Year: 2009

We focus in this paper on the problem of configuring and managing network security devices, such as Firewalls, Virtual Private Network (VPN) tunnels, and Intrusion Detection Systems (IDSs). Our proposal is the following. First, we formally specify the security requirements of a given system by using an expressive access control model. As a result, we obtain an abstract security policy, which is free of ambiguities, redundancies or unnecessary details. Second, we deploy such an abstract policy through a set of automatic compilations into the security devices of the system. This proposed deployment process not only simplifies the security administrator's job, but also guarantees a resulting configuration free of anomalies and/or inconsistencies.
Making Hand Geometry Verification System More Accurate Using Time Series Representation with R-K Band Learning
Venue: arXiv cs.CR 2009
Year: 2009

At present, applications of biometrics are rapidly increasing due to inconveniences in using traditional passwords and physical keys. Hand geometry, one of the most well-known biometrics, is implemented in many verification systems with various feature extraction methods. In recent work, a hand geometry verification system using time series conversion techniques and Dynamic Time Warping (DTW) distance measure with Sakoe-Chiba band has been proposed. This system demonstrates many advantages, especially ease of implementation and small storage space requirement using time series representation. In this paper, we propose a novel hand geometry verification system that exploits DTW distance measure and R-K band learning to further improve the system performance. Finally, our evaluation reveals that our proposed system outperforms the current system by a wide margin, in terms of False Acceptance Rate (FAR), False Rejection Rate (FRR), and Total Success Rate (TSR) at Equal Error Rate (EER).
A Nearly Optimal Construction of Flash Codes
Venue: arXiv cs.IT 2009
Year: 2009

Flash memory is a non-volatile computer memory comprised of blocks of cells, wherein each cell can take on q different values or levels. While increasing the cell level is easy, reducing the level of a cell can be accomplished only by erasing an entire block. Since block erasures are highly undesirable, coding schemes - known as floating codes or flash codes - have been designed in order to maximize the number of times that information stored in a flash memory can be written (and re-written) prior to incurring a block erasure. An (n,k,t)_q flash code C is a coding scheme for storing k information bits in n cells in such a way that any sequence of up to t writes (where a write is a transition 0 -> 1 or 1 -> 0 in any one of the k bits) can be accommodated without a block erasure. The total number of available level transitions in n cells is n(q-1), and the write deficiency of C, defined as δ(C) = n(q-1) - t, is a measure of how close the code comes to perfectly utilizing all these transitions. For k > 6 and large n, the best previously known construction of flash codes achieves a write deficiency of O(qk^2). On the other hand, the best known lower bound on write deficiency is Ω(qk). In this paper, we present a new construction of flash codes that approaches this lower bound to within a factor logarithmic in k. To this end, we first improve upon the so-called "indexed" flash codes, due to Jiang and Bruck, by eliminating the need for index cells in the Jiang-Bruck construction. Next, we further increase the number of writes by introducing a new multi-stage (recursive) indexing scheme. We then show that the write deficiency of the resulting flash codes is O(qk\log k) if q \geq \log_2k, and at most O(k\log^2 k) otherwise.
Sum capacity of multi-source linear finite-field relay networks with fading
Venue: arXiv cs.IT 2009
Year: 2009

We study a fading linear finite-field relay network having multiple source-destination pairs. Because of the interference created by different unicast sessions, the problem of finding its capacity region is in general difficult. We observe that, since channels are time-varying, relays can deliver their received signals by waiting for appropriate channel realizations such that the destinations can decode their messages without interference. We propose a block Markov encoding and relaying scheme that exploits such channel variations. By deriving a general cut-set upper bound and an achievable rate region, we characterize the sum capacity for some classes of channel distributions and network topologies. For example, when the channels are uniformly distributed, the sum capacity is given by the minimum average rank of the channel matrices constructed by all cuts that separate the entire sources and destinations. We also describe other cases where the capacity is characterized.
Fast and Near-Optimal Matrix Completion via Randomized Basis Pursuit
Venue: arXiv cs.IT 2009
Year: 2009

Motivated by the philosophy and phenomenal success of compressed sensing, the problem of reconstructing a matrix from a sampling of its entries has attracted much attention recently. Such a problem can be viewed as an information-theoretic variant of the well-studied matrix completion problem, and the main objective is to design an efficient algorithm that can reconstruct a matrix by inspecting only a small number of its entries. Although this is an impossible task in general, Candès and co-authors have recently shown that under a so-called incoherence assumption, a rank $r$ $n\times n$ matrix can be reconstructed using semidefinite programming (SDP) after one inspects $O(nr\log^6n)$ of its entries. In this paper we propose an alternative approach that is much more efficient and can reconstruct a larger class of matrices by inspecting a significantly smaller number of the entries. Specifically, we first introduce a class of so-called stable matrices and show that it includes all those that satisfy the incoherence assumption. Then, we propose a randomized basis pursuit (RBP) algorithm and show that it can reconstruct a stable rank $r$ $n\times n$ matrix after inspecting $O(nr\log n)$ of its entries. Our sampling bound is only a logarithmic factor away from the information-theoretic limit and is essentially optimal. Moreover, the runtime of the RBP algorithm is bounded by $O(nr^2\log n+n^2r)$, which compares very favorably with the $Ω(n^4r^2\log^{12}n)$ runtime of the SDP-based algorithm. Perhaps more importantly, our algorithm will provide an exact reconstruction of the input matrix in polynomial time. By contrast, the SDP-based algorithm can only provide an approximate one in polynomial time.
On Lines, Joints, and Incidences in Three Dimensions
Venue: arXiv cs.CG 2009
Year: 2009

We extend (and somewhat simplify) the algebraic proof technique of Guth and Katz \cite{GK}, to obtain several sharp bounds on the number of incidences between lines and points in three dimensions. Specifically, we show: (i) The maximum possible number of incidences between $n$ lines in $\reals^3$ and $m$ of their joints (points incident to at least three non-coplanar lines) is $Θ(m^{1/3}n)$ for $m\ge n$, and $Θ(m^{2/3}n^{2/3}+m+n)$ for $m\le n$. (ii) In particular, the number of such incidences cannot exceed $O(n^{3/2})$. (iii) The bound in (i) also holds for incidences between $n$ lines and $m$ arbitrary points (not necessarily joints), provided that no plane contains more than O(n) points and each point is incident to at least three lines. As a preliminary step, we give a simpler proof of (an extension of) the bound $O(n^{3/2})$, established by Guth and Katz, on the number of joints in a set of $n$ lines in $\reals^3$. We also present some further extensions of these bounds, and give a proof of Bourgain's conjecture on incidences between points and lines in 3-space, which constitutes a simpler alternative to the proof of \cite{GK}.
Une CNS pour l'acheminement de messages instantanément stabilisant
Venue: arXiv cs.DC 2009
Year: 2009

A snap-stabilizing algorithm ensures that it always behaves according to its specifications whenever it starts from an arbitrary configuration. In this paper, we interest in the message forwarding problem in a message-switched network. We must manage network ressources in order to deliver messages to any processor of the network. In this goal, we need information given by a routing algorithm. But, due to the context of stabilization, this information can be initially corrupted. It is why the existence of snap-stabilizing algorithms for this task (proved in [CDV09]) implies that we can ask the system to begin forwarding messages even if routing tables are initially corrupted. In this paper, we generalize the previous result given a necessary and sufficient condition to solve the forwarding problem in a snap-stabilizing way.
Improved Adaptive Group Testing Algorithms with Applications to Multiple Access Channels and Dead Sensor Diagnosis
Venue: arXiv cs.DS 2009
Year: 2009

We study group-testing algorithms for resolving broadcast conflicts on a multiple access channel (MAC) and for identifying the dead sensors in a mobile ad hoc wireless network. In group-testing algorithms, we are asked to identify all the defective items in a set of items when we can test arbitrary subsets of items. In the standard group-testing problem, the result of a test is binary--the tested subset either contains defective items or not. In the more generalized versions we study in this paper, the result of each test is non-binary. For example, it may indicate whether the number of defective items contained in the tested subset is zero, one, or at least two. We give adaptive algorithms that are provably more efficient than previous group testing algorithms. We also show how our algorithms can be applied to solve conflict resolution on a MAC and dead sensor diagnosis. Dead sensor diagnosis poses an interesting challenge compared to MAC resolution, because dead sensors are not locally detectable, nor are they themselves active participants.
On the Secrecy Rate of Interference Networks using structured codes
Venue: arXiv cs.IT 2009
Year: 2009

This paper shows that structured transmission schemes are a good choice for secret communication over interference networks with an eavesdropper. Structured transmission is shown to exploit channel asymmetries and thus perform better than randomly generated codebooks for such channels. For a class of interference channels, we show that an equivocation sumrate that is within two bits of the maximum possible legitimate communication sum-rate is achievable using lattice codes.
Accelerator-Oriented Algorithm Transformation for Temporal Data Mining
Venue: arXiv cs.DC 2009
Year: 2009

Temporal data mining algorithms are becoming increasingly important in many application domains including computational neuroscience, especially the analysis of spike train data. While application scientists have been able to readily gather multi-neuronal datasets, analysis capabilities have lagged behind, due to both lack of powerful algorithms and inaccessibility to powerful hardware platforms. The advent of GPU architectures such as Nvidia's GTX 280 offers a cost-effective option to bring these capabilities to the neuroscientist's desktop. Rather than port existing algorithms onto this architecture, we advocate the need for algorithm transformation, i.e., rethinking the design of the algorithm in a way that need not necessarily mirror its serial implementation strictly. We present a novel implementation of a frequent episode discovery algorithm by revisiting "in-the-large" issues such as problem decomposition as well as "in-the-small" issues such as data layouts and memory access patterns. This is non-trivial because frequent episode discovery does not lend itself to GPU-friendly data-parallel mapping strategies. Applications to many datasets and comparisons to CPU as well as prior GPU implementations showcase the advantages of our approach.
Formalizing Safety Requirements Using Controlling Automata
Venue: arXiv cs.SE 2009
Year: 2009

Safety is an important element of dependability. It is defined as the absence of accidents. Most accidents involving software-intensive systems have been system accidents, which are caused by unsafe inter-system or inter-component interactions. To validate the absence of system hazards concerning dysfunctional interactions, industrials call for approaches of modeling system safety requirements and interaction constraints among components. This paper proposes such a formalism, namely interface control systems (or shortly C-Systems). An interface C-System is composed of an interface automaton and a controlling automaton, which formalizes safe interactions and restricts system behavior at the meta level. This framework differs from the framework of traditional model checking. It explicitly separates the tasks of product engineers and safety engineers, and provides a top-down technique for modeling a system with safety constraints, and for automatically composing a safe system that conforms to safety requirements. The contributions of this work include formalizing safety requirements and a way of automatically ensuring system safety.
Identifying Influential Bloggers: Time Does Matter
Venue: arXiv cs.IR 2009
Year: 2009

Blogs have recently become one of the most favored services on the Web. Many users maintain a blog and write posts to express their opinion, experience and knowledge about a product, an event and every subject of general or specific interest. More users visit blogs to read these posts and comment them. This "participatory journalism" of blogs has such an impact upon the masses that Keller and Berry argued that through blogging "one American in tens tells the other nine how to vote, where to eat and what to buy" \cite{keller1}. Therefore, a significant issue is how to identify such influential bloggers. This problem is very new and the relevant literature lacks sophisticated solutions, but most importantly these solutions have not taken into account temporal aspects for identifying influential bloggers, even though the time is the most critical aspect of the Blogosphere. This article investigates the issue of identifying influential bloggers by proposing two easily computed blogger ranking methods, which incorporate temporal aspects of the blogging activity. Each method is based on a specific metric to score the blogger's posts. The first metric, termed MEIBI, takes into consideration the number of the blog post's inlinks and its comments, along with the publication date of the post. The second metric, MEIBIX, is used to score a blog post according to the number and age of the blog post's inlinks and its comments. These methods are evaluated against the state-of-the-art influential blogger identification method utilizing data collected from a real-world community blog site. The obtained results attest that the new methods are able to better identify significant temporal patterns in the blogging behaviour.
Secure Degrees of Freedom for Gaussian Channels with Interference: Structured Codes Outperform Gaussian Signaling
Venue: arXiv cs.IT 2009
Year: 2009

In this work, we prove that a positive secure degree of freedom is achievable for a large class of Gaussian channels as long as the channel is not degraded and the channel is fully connected. This class includes the MAC wire-tap channel, the 2-user interference channel with confidential messages, the 2-user interference channel with an external eavesdropper. Best known achievable schemes to date for these channels use Gaussian signaling. In this work, we show that structured codes outperform Gaussian random codes at high SNR when channel gains are real numbers.
An Immune System Inspired Approach to Automated Program Verification
Venue: arXiv cs.NE 2009
Year: 2009

An immune system inspired Artificial Immune System (AIS) algorithm is presented, and is used for the purposes of automated program verification. Relevant immunological concepts are discussed and the field of AIS is briefly reviewed. It is proposed to use this AIS algorithm for a specific automated program verification task: that of predicting shape of program invariants. It is shown that the algorithm correctly predicts program invariant shape for a variety of benchmarked programs.
Average-Case Active Learning with Costs
Venue: arXiv cs.LG 2009
Year: 2009

We analyze the expected cost of a greedy active learning algorithm. Our analysis extends previous work to a more general setting in which different queries have different costs. Moreover, queries may have more than two possible responses and the distribution over hypotheses may be non uniform. Specific applications include active learning with label costs, active learning for multiclass and partial label queries, and batch mode active learning. We also discuss an approximate version of interest when there are very many queries.