OpenRaiser/Intern-Atlas huggingface dataset:
Distributed sensor failure detection in sensor networks
Venue: arXiv cs.NI 2011
Year: 2011

We investigate the problem of distributed sensors' failure detection in networks with a small number of defective sensors, whose measurements differ significantly from neighboring sensor measurements. Defective sensors are represented by non-zero values in binary sparse signals. We build on the sparse nature of the binary sensor failure signals and propose a new distributed detection algorithm based on Group Testing (GT). The distributed GT algorithm estimates the set of defective sensors from a small number of linearly independent binary messages exchanged by the sensors. The distributed GT algorithm uses a low complexity distance decoder that is robust to noisy messages. We first consider networks with only one defective sensor and determine the minimal number of linearly independent messages needed for detection of the defective sensor with high probability. We then extend our study to the detection of multiple defective sensors by modifying appropriately the message exchange protocol and the decoding procedure. We show through experimentation that, for small and medium sized networks, the number of messages required for successful detection is actually smaller than the minimal number computed in the analysis. Simulations demonstrate that the proposed method outperforms methods based on random walk measurements collection in terms of detection performance and convergence rate. Finally, the proposed method is resilient to network dynamics due to the effective gossip-based message dissemination protocol.
PDDL2.1 - The Art of the Possible? Commentary on Fox and Long
Venue: arXiv cs.AI 2011
Year: 2011

PDDL2.1 was designed to push the envelope of what planning algorithms can do, and it has succeeded. It adds two important features: durative actions,which take time (and may have continuous effects); and objective functions for measuring the quality of plans. The concept of durative actions is flawed; and the treatment of their semantics reveals too strong an attachment to the way many contemporary planners work. Future PDDL innovators should focus on producing a clean semantics for additions to the language, and let planner implementers worry about coupling their algorithms to problems expressed in the latest version of the language.
Improving Heuristics Through Relaxed Search - An Analysis of TP4 and HSP*a in the 2004 Planning Competition
Venue: arXiv cs.AI 2011
Year: 2011

The hm admissible heuristics for (sequential and temporal) regression planning are defined by a parameterized relaxation of the optimal cost function in the regression search space, where the parameter m offers a trade-off between the accuracy and computational cost of theheuristic. Existing methods for computing the hm heuristic require time exponential in m, limiting them to small values (m andlt= 2). The hm heuristic can also be viewed as the optimal cost function in a relaxation of the search space: this paper presents relaxed search, a method for computing this function partially by searching in the relaxed space. The relaxed search method, because it computes hm only partially, is computationally cheaper and therefore usable for higher values of m. The (complete) hm heuristic is combined with partial hm heuristics, for m = 3,..., computed by relaxed search, resulting in a more accurate heuristic. This use of the relaxed search method to improve on the hm heuristic is evaluated by comparing two optimal temporal planners: TP4, which does not use it, and HSP*a, which uses it but is otherwise identical to TP4. The comparison is made on the domains used in the 2004 International Planning Competition, in which both planners participated. Relaxed search is found to be cost effective in some of these domains, but not all. Analysis reveals a characterization of the domains in which relaxed search can be expected to be cost effective, in terms of two measures on the original and relaxed search spaces. In the domains where relaxed search is cost effective, expanding small states is computationally cheaper than expanding large states and small states tend to have small successor states.
Approximation Complexity of Complex-Weighted Degree-Two Counting Constraint Satisfaction Problems
Venue: arXiv cs.CC 2011
Year: 2011

Constraint satisfaction problems have been studied in numerous fields with practical and theoretical interests. In recent years, major breakthroughs have been made in a study of counting constraint satisfaction problems (or #CSPs). In particular, a computational complexity classification of bounded-degree #CSPs has been discovered for all degrees except for two, where the "degree" of an input instance is the maximal number of times that each input variable appears in a given set of constraints. Despite the efforts of recent studies, however, a complexity classification of degree-2 #CSPs has eluded from our understandings. This paper challenges this open problem and gives its partial solution by applying two novel proof techniques--T_{2}-constructibility and parametrized symmetrization--which are specifically designed to handle "arbitrary" constraints under randomized approximation-preserving reductions. We partition entire constraints into four sets and we classify the approximation complexity of all degree-2 #CSPs whose constraints are drawn from two of the four sets into two categories: problems computable in polynomial-time or problems that are at least as hard as #SAT. Our proof exploits a close relationship between complex-weighted degree-2 #CSPs and Holant problems, which are a natural generalization of complex-weighted #CSPs.
The Degrees of Freedom of the 2-Hop, 2-User Interference Channel with Feedback
Venue: arXiv cs.IT 2011
Year: 2011

The layered two-hop, two-flow interference network is considered that consists of two sources, two relays and two destinations with the first hop network between he sources and the relays and the second hop network between relays and destinations both being i.i.d. Rayleigh fading Gaussian interference channels. Two feedback models are studied. In the first one, called the delayed channel state information at the sources (delayed CSI-S) model, the sources know all channel coefficients with a finite delay but the relays have no side information whatsoever. In the second feedback model, referred to as the limited Shannon feedback model, the relays know first hop channel coefficients instantaneously and the second hop channel with a finite delay and one relay knows the received signal of one of the destinations with a finite delay and the other relay knows the received signal of the other destination with a finite delay but there is no side information at the sources whatsoever. It is shown in this paper that under both these settings, the layered two-hop, two-flow interference channel has 4/3 degrees of freedom. The result is obtained by developing a broadcast-channel-type upper-bound and new achievability schemes based on the ideas of retrospective interference alignment and retro-cooperative interference alignment, respectively.
Object-oriented semantics of English in natural language understanding system
Venue: arXiv cs.CL 2011
Year: 2011

A new approach to the problem of natural language understanding is proposed. The knowledge domain under consideration is the social behavior of people. English sentences are translated into set of predicates of a semantic database, which describe persons, occupations, organizations, projects, actions, events, messages, machines, things, animals, location and time of actions, relations between objects, thoughts, cause-and-effect relations, abstract objects. There is a knowledge base containing the description of semantics of objects (functions and structure), actions (motives and causes), and operations.
More powerful biomolecular computers
Venue: arXiv cs.ET 2011
Year: 2011

Biomolecular computers, along with quantum computers, may be a future alternative for traditional, silicon-based computers. Main advantages of biomolecular computers are massive parallel processing of data, expanded capacity of storing information and compatibility with living organisms (first attempts of using biomolecular computers in cancer therapy through blocking of improper genetic information are described in Benenson et al.(2004). However, biomolecular computers have several drawbacks including time-consuming procedures of preparing of input, problems in detecting output signals and interference with by-products. Due to these obstacles, there are few laboratory implementations of theoretically designed DNA computers (like the Turing machine and pushdown automaton), but there are many implementations of DNA computers for particular problems. The first practical laboratory implementation of the general theoretical model of a machine performing DNA-based calculations was a simple two-symbol two-state finite automaton established by Benenson et al.(2001). In the present work, we propose a new attitude, extending the capability of DNA-based finite automaton, by employing two or potentially more restriction enzymes instead of one used in other works. This creates an opportunity to implement in laboratories of more complex finite automata and other theoretical models of computers: pushdown automata, Turing machines.
Learning Item Trees for Probabilistic Modelling of Implicit Feedback
Venue: arXiv cs.LG 2011
Year: 2011

User preferences for items can be inferred from either explicit feedback, such as item ratings, or implicit feedback, such as rental histories. Research in collaborative filtering has concentrated on explicit feedback, resulting in the development of accurate and scalable models. However, since explicit feedback is often difficult to collect it is important to develop effective models that take advantage of the more widely available implicit feedback. We introduce a probabilistic approach to collaborative filtering with implicit feedback based on modelling the user's item selection process. In the interests of scalability, we restrict our attention to tree-structured distributions over items and develop a principled and efficient algorithm for learning item trees from data. We also identify a problem with a widely used protocol for evaluating implicit feedback models and propose a way of addressing it using a small quantity of explicit feedback data.
Online Primal-Dual For Non-linear Optimization with Applications to Speed Scaling
Venue: arXiv cs.DS 2011
Year: 2011

We reinterpret some online greedy algorithms for a class of nonlinear "load-balancing" problems as solving a mathematical program online. For example, we consider the problem of assigning jobs to (unrelated) machines to minimize the sum of the alpha^{th}-powers of the loads plus assignment costs (the online Generalized Assignment Problem); or choosing paths to connect terminal pairs to minimize the alpha^{th}-powers of the edge loads (online routing with speed-scalable routers). We give analyses of these online algorithms using the dual of the primal program as a lower bound for the optimal algorithm, much in the spirit of online primal-dual results for linear problems. We then observe that a wide class of uni-processor speed scaling problems (with essentially arbitrary scheduling objectives) can be viewed as such load balancing problems with linear assignment costs. This connection gives new algorithms for problems that had resisted solutions using the dominant potential function approaches used in the speed scaling literature, as well as alternate, cleaner proofs for other known results.
The Fast Downward Planning System
Venue: arXiv cs.AI 2011
Year: 2011

Fast Downward is a classical planning system based on heuristic search. It can deal with general deterministic planning problems encoded in the propositional fragment of PDDL2.2, including advanced features like ADL conditions and effects and derived predicates (axioms). Like other well-known planners such as HSP and FF, Fast Downward is a progression planner, searching the space of world states of a planning task in the forward direction. However, unlike other PDDL planning systems, Fast Downward does not use the propositional PDDL representation of a planning task directly. Instead, the input is first translated into an alternative representation called multi-valued planning tasks, which makes many of the implicit constraints of a propositional planning task explicit. Exploiting this alternative representation, Fast Downward uses hierarchical decompositions of planning tasks for computing its heuristic function, called the causal graph heuristic, which is very different from traditional HSP-like heuristics based on ignoring negative interactions of operators. In this article, we give a full account of Fast Downwards approach to solving multi-valued planning tasks. We extend our earlier discussion of the causal graph heuristic to tasks involving axioms and conditional effects and present some novel techniques for search control that are used within Fast Downwards best-first search algorithm: preferred operators transfer the idea of helpful actions from local search to global best-first search, deferred evaluation of heuristic functions mitigates the negative effect of large branching factors on search performance, and multi-heuristic best-first search combines several heuristic evaluation functions within a single search algorithm in an orthogonal way. We also describe efficient data structures for fast state expansion (successor generators and axiom evaluators) and present a new non-heuristic search algorithm called focused iterative-broadening search, which utilizes the information encoded in causal graphs in a novel way. Fast Downward has proven remarkably successful: It won the "classical (i.e., propositional, non-optimising) track of the 4th International Planning Competition at ICAPS 2004, following in the footsteps of planners such as FF and LPG. Our experiments show that it also performs very well on the benchmarks of the earlier planning competitions and provide some insights about the usefulness of the new search enhancements.
Evaluation of a Bundling Technique for Parallel Coordinates
Venue: arXiv cs.GR 2011
Year: 2011

We describe a technique for bundled curve representations in parallel-coordinates plots and present a controlled user study evaluating their effectiveness. Replacing the traditional C^0 polygonal lines by C^1 continuous piecewise Bezier curves makes it easier to visually trace data points through each coordinate axis. The resulting Bezier curves can then be bundled to visualize data with given cluster structures. Curve bundles are efficient to compute, provide visual separation between data clusters, reduce visual clutter, and present a clearer overview of the dataset. A controlled user study with 14 participants confirmed the effectiveness of curve bundling for parallel-coordinates visualization: 1) compared to polygonal lines, it is equally capable of revealing correlations between neighboring data attributes; 2) its geometric cues can be effective in displaying cluster information. For some datasets curve bundling allows the color perceptual channel to be applied to other data attributes, while for complex cluster patterns, bundling and color can represent clustering far more clearly than either alone.
Channel Quantization for Physical Layer Network-Coded Two-Way Relaying
Venue: arXiv cs.IT 2011
Year: 2011

The design of modulation schemes for the physical layer network-coded two way relaying scenario is considered with the protocol which employs two phases: Multiple access (MA) Phase and Broadcast (BC) phase. It was observed by Koike-Akino et al. that adaptively changing the network coding map used at the relay according to the channel conditions greatly reduces the impact of multiple access interference which occurs at the relay during the MA phase. In other words, the set of all possible channel realizations (the complex plane) is quantized into a finite number of regions, with a specific network coding map giving the best performance in a particular region. We highlight the issues associated with the scheme proposed by Koike-Akino et al. and propose a scheme which solves these issues. We obtain a quantization of the set of all possible channel realizations analytically for the case when $M$-PSK (for $M$ any power of 2) is the signal set used during the MA phase. It is shown that the complex plane can be classified into two regions: a region in which any network coding map which satisfies the so called exclusive law gives the same best performance and a region in which the choice of the network coding map affects the performance, which is further quantized based on the choice of the network coding map which optimizes the performance. The quantization thus obtained analytically, leads to the same as the one obtained using computer search for 4-PSK signal set by Koike-Akino et al., when specialized for $M=4.$
Space-efficient Local Computation Algorithms
Venue: arXiv cs.DS 2011
Year: 2011

Recently Rubinfeld et al. (ICS 2011, pp. 223--238) proposed a new model of sublinear algorithms called \emph{local computation algorithms}. In this model, a computation problem $F$ may have more than one legal solution and each of them consists of many bits. The local computation algorithm for $F$ should answer in an online fashion, for any index $i$, the $i^{\mathrm{th}}$ bit of some legal solution of $F$. Further, all the answers given by the algorithm should be consistent with at least one solution of $F$. In this work, we continue the study of local computation algorithms. In particular, we develop a technique which under certain conditions can be applied to construct local computation algorithms that run not only in polylogarithmic time but also in polylogarithmic \emph{space}. Moreover, these local computation algorithms are easily parallelizable and can answer all parallel queries consistently. Our main technical tools are pseudorandom numbers with bounded independence and the theory of branching processes.
Sensitivity Analysis for Declarative Relational Query Languages with Ordinal Ranks
Venue: arXiv cs.DB 2011
Year: 2011

We present sensitivity analysis for results of query executions in a relational model of data extended by ordinal ranks. The underlying model of data results from the ordinary Codd's model of data in which we consider ordinal ranks of tuples in data tables expressing degrees to which tuples match queries. In this setting, we show that ranks assigned to tuples are insensitive to small changes, i.e., small changes in the input data do not yield large changes in the results of queries.
A Survey of Ocean Simulation and Rendering Techniques in Computer Graphics
Venue: arXiv cs.GR 2011
Year: 2011

This paper presents a survey of ocean simulation and rendering methods in computer graphics. To model and animate the ocean's surface, these methods mainly rely on two main approaches: on the one hand, those which approximate ocean dynamics with parametric, spectral or hybrid models and use empirical laws from oceanographic research. We will see that this type of methods essentially allows the simulation of ocean scenes in the deep water domain, without breaking waves. On the other hand, physically-based methods use Navier-Stokes Equations (NSE) to represent breaking waves and more generally ocean surface near the shore. We also describe ocean rendering methods in computer graphics, with a special interest in the simulation of phenomena such as foam and spray, and light's interaction with the ocean surface.
Failure Filtrations for Fenced Sensor Networks
Venue: arXiv cs.CG 2011
Year: 2011

In this paper we consider the question of sensor network coverage for a 2-dimensional domain. We seek to compute the probability that a set of sensors fails to cover given only non-metric, local (who is talking to whom) information and a probability distribution of failure of each node. This builds on the work of de Silva and Ghrist who analyzed this problem in the deterministic situation. We first show that a it is part of a slightly larger class of problems which is #P-complete, and thus fast algorithms likely do not exist unless P$=$NP. We then give a deterministic algorithm which is feasible in the case of a small set of sensors, and give a dynamic algorithm for an arbitrary set of sensors failing over time which utilizes a new criterion for coverage based on the one proposed by de Silva and Ghrist. These algorithms build on the theory of topological persistence.
A Novel comprehensive method for real time Video Motion Detection Surveillance
Venue: arXiv cs.CV 2011
Year: 2011

This article describes a comprehensive system for surveillance and monitoring applications. The development of an efficient real time video motion detection system is motivated by their potential for deployment in the areas where security is the main concern. The paper presents a platform for real time video motion detection and subsequent generation of an alarm condition as set by the parameters of the control system. The prototype consists of a mobile platform mounted with RF camera which provides continuous feedback of the environment. The received visual information is then analyzed by user for appropriate control action, thus enabling the user to operate the system from a remote location. The system is also equipped with the ability to process the image of an object and generate control signals which are automatically transmitted to the mobile platform to track the object.
#h00t: Censorship Resistant Microblogging
Venue: arXiv cs.CR 2011
Year: 2011

Microblogging services such as Twitter are an increasingly important way to communicate, both for individuals and for groups through the use of hashtags that denote topics of conversation. However, groups can be easily blocked from communicating through blocking of posts with the given hashtags. We propose #h00t, a system for censorship resistant microblogging. #h00t presents an interface that is much like Twitter, except that hashtags are replaced with very short hashes (e.g., 24 bits) of the group identifier. Naturally, with such short hashes, hashtags from different groups may collide and #h00t users will actually seek to create collisions. By encrypting all posts with keys derived from the group identifiers, #h00t client software can filter out other groups' posts while making such filtering difficult for the adversary. In essence, by leveraging collisions, groups can tunnel their posts in other groups' posts. A censor could not block a given group without also blocking the other groups with colliding hashtags. We evaluate the feasibility of #h00t through traces collected from Twitter, showing that a single modern computer has enough computational throughput to encrypt every tweet sent through Twitter in real time. We also use these traces to analyze the bandwidth and anonymity tradeoffs that would come with different variations on how group identifiers are encoded and hashtags are selected to purposefully collide with one another.