OpenRaiser/Intern-Atlas huggingface dataset:
Complexity of Propositional Abduction for Restricted Sets of Boolean Functions
Venue: arXiv cs.CC 2010
Year: 2010

Abduction is a fundamental and important form of non-monotonic reasoning. Given a knowledge base explaining how the world behaves it aims at finding an explanation for some observed manifestation. In this paper we focus on propositional abduction, where the knowledge base and the manifestation are represented by propositional formulae. The problem of deciding whether there exists an explanation has been shown to be SigmaP2-complete in general. We consider variants obtained by restricting the allowed connectives in the formulae to certain sets of Boolean functions. We give a complete classification of the complexity for all considerable sets of Boolean functions. In this way, we identify easier cases, namely NP-complete and polynomial cases; and we highlight sources of intractability. Further, we address the problem of counting the explanations and draw a complete picture for the counting complexity.
Optimism in Games with Non-Probabilistic Uncertainty
Venue: arXiv cs.GT 2010
Year: 2010

The paper studies one-shot two-player games with non-Bayesian uncertainty. The players have an attitude that ranges from optimism to pessimism in the face of uncertainty. Given the attitudes, each player forms a belief about the set of possible strategies of the other player. If these beliefs are consistent, one says that they form an uncertainty equilibrium. One then considers a two-phase game where the players first choose their attitude and then play the resulting game. The paper illustrates these notions with a number of games where the approach provides a new insight into the plausible strategies of the players.
On Channel-Discontinuity-Constraint Routing in Wireless Networks
Venue: arXiv cs.NI 2010
Year: 2010

Multi-channel wireless networks are increasingly being employed as infrastructure networks, e.g. in metro areas. Nodes in these networks frequently employ directional antennas to improve spatial throughput. In such networks, given a source and destination, it is of interest to compute an optimal path and channel assignment on every link in the path such that the path bandwidth is the same as that of the link bandwidth and such a path satisfies the constraint that no two consecutive links on the path are assigned the same channel, referred to as "Channel Discontinuity Constraint" (CDC). CDC-paths are also quite useful for TDMA system, where preferably every consecutive links along a path are assigned different time slots. This paper contains several contributions. We first present an $O(N^{2})$ distributed algorithm for discovering the shortest CDC-path between given source and destination. This improves the running time of the $O(N^{3})$ centralized algorithm of Ahuja et al. for finding the minimum-weight CDC-path. Our second result is a generalized $t$-spanner for CDC-path; For any $θ>0$ we show how to construct a sub-network containing only $O(\frac{N}θ)$ edges, such that that length of shortest CDC-paths between arbitrary sources and destinations increases by only a factor of at most $(1-2\sin{\tfracθ{2}})^{-2}$. We propose a novel algorithm to compute the spanner in a distributed manner using only $O(n\log{n})$ messages. An important conclusion of this scheme is in the case of directional antennas are used. In this case, it is enough to consider only the two closest nodes in each cone.
Branching-time model checking of one-counter processes
Venue: arXiv cs.LO 2010
Year: 2010

One-counter processes (OCPs) are pushdown processes which operate only on a unary stack alphabet. We study the computational complexity of model checking computation tree logic (CTL) over OCPs. A PSPACE upper bound is inherited from the modal mu-calculus for this problem. First, we analyze the periodic behaviour of CTL over OCPs and derive a model checking algorithm whose running time is exponential only in the number of control locations and a syntactic notion of the formula that we call leftward until depth. Thus, model checking fixed OCPs against CTL formulas with a fixed leftward until depth is in P. This generalizes a result of the first author, Mayr, and To for the expression complexity of CTL's fragment EF. Second, we prove that already over some fixed OCP, CTL model checking is PSPACE-hard. Third, we show that there already exists a fixed CTL formula for which model checking of OCPs is PSPACE-hard. For the latter, we employ two results from complexity theory: (i) Converting a natural number in Chinese remainder presentation into binary presentation is in logspace-uniform NC^1 and (ii) PSPACE is AC^0-serializable. We demonstrate that our approach can be used to answer further open questions.
Learning to Predict Combinatorial Structures
Venue: arXiv cs.LG 2010
Year: 2010

The major challenge in designing a discriminative learning algorithm for predicting structured data is to address the computational issues arising from the exponential size of the output space. Existing algorithms make different assumptions to ensure efficient, polynomial time estimation of model parameters. For several combinatorial structures, including cycles, partially ordered sets, permutations and other graph classes, these assumptions do not hold. In this thesis, we address the problem of designing learning algorithms for predicting combinatorial structures by introducing two new assumptions: (i) The first assumption is that a particular counting problem can be solved efficiently. The consequence is a generalisation of the classical ridge regression for structured prediction. (ii) The second assumption is that a particular sampling problem can be solved efficiently. The consequence is a new technique for designing and analysing probabilistic structured prediction models. These results can be applied to solve several complex learning problems including but not limited to multi-label classification, multi-category hierarchical classification, and label ranking.
Continuous Monitoring of Distributed Data Streams over a Time-based Sliding Window
Venue: arXiv cs.DS 2010
Year: 2010

The past decade has witnessed many interesting algorithms for maintaining statistics over a data stream. This paper initiates a theoretical study of algorithms for monitoring distributed data streams over a time-based sliding window (which contains a variable number of items and possibly out-of-order items). The concern is how to minimize the communication between individual streams and the root, while allowing the root, at any time, to be able to report the global statistics of all streams within a given error bound. This paper presents communication-efficient algorithms for three classical statistics, namely, basic counting, frequent items and quantiles. The worst-case communication cost over a window is $O(\frac{k} ε \log \frac{εN}{k})$ bits for basic counting and $O(\frac{k}ε \log \frac{N}{k})$ words for the remainings, where $k$ is the number of distributed data streams, $N$ is the total number of items in the streams that arrive or expire in the window, and $ε< 1$ is the desired error bound. Matching and nearly matching lower bounds are also obtained.
Reconstructing Experiences through Sketching
Venue: arXiv cs.HC 2010
Year: 2010

We present iScale, a survey tool for the retrospective elicitation of longitudinal user experience data. iScale employs sketching in imposing a process in the reconstruction of one's experiences with the aim to minimize retrospection bias. Two versions, the Constructive and the Value-Account iScale, were motivated by two distinct theories on how people reconstruct emotional experiences from memory. These two versions were tested in two separate studies. Study 1 aimed at providing qualitative insight into the use of iScale and compared its performance to that of free-hand sketching. Study 2 compared the two versions of iScale to free recall, a control condition that does not influence the reconstruction process. Significant differences between iScale and free recall were found. Overall, iScale resulted in an increase in the amount, the richness, and the test-retest reliability of recalled information. These results provide support for the viability of retrospective techniques as a cost-effective alternative to longitudinal studies.
Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation
Venue: arXiv cs.DS 2010
Year: 2010

The performance of a dynamic dictionary is measured mainly by its update time, lookup time, and space consumption. In terms of update time and lookup time there are known constructions that guarantee constant-time operations in the worst case with high probability, and in terms of space consumption there are known constructions that use essentially optimal space. However, although the first analysis of a dynamic dictionary dates back more than 45 years ago (when Knuth analyzed linear probing in 1963), the trade-off between these aspects of performance is still not completely understood. In this paper we settle two fundamental open problems: - We construct the first dynamic dictionary that enjoys the best of both worlds: it stores n elements using (1+epsilon)n memory words, and guarantees constant-time operations in the worst case with high probability. Specifically, for any epsilon = Ω((\log\log n / \log n)^{1/2} ) and for any sequence of polynomially many operations, with high probability over the randomness of the initialization phase, all operations are performed in constant time which is independent of epsilon. The construction is a two-level variant of cuckoo hashing, augmented with a "backyard" that handles a large fraction of the elements, together with a de-amortized perfect hashing scheme for eliminating the dependency on epsilon. - We present a variant of the above construction that uses only (1+o(1))B bits, where B is the information-theoretic lower bound for representing a set of size n taken from a universe of size u, and guarantees constant-time operations in the worst case with high probability, as before. This problem was open even in the amortized setting. One of the main ingredients of our construction is a permutation-based variant of cuckoo hashing, which significantly improves the space consumption of cuckoo hashing when dealing with a rather small universe.
The k-in-a-path problem for claw-free graphs
Venue: arXiv cs.DM 2010
Year: 2010

Testing whether there is an induced path in a graph spanning k given vertices is already NP-complete in general graphs when k=3. We show how to solve this problem in polynomial time on claw-free graphs, when k is not part of the input but an arbitrarily fixed integer.
Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements
Venue: arXiv cs.IT 2010
Year: 2010

This paper presents several novel theoretical results regarding the recovery of a low-rank matrix from just a few measurements consisting of linear combinations of the matrix entries. We show that properly constrained nuclear-norm minimization stably recovers a low-rank matrix from a constant number of noisy measurements per degree of freedom; this seems to be the first result of this nature. Further, the recovery error from noisy data is within a constant of three targets: 1) the minimax risk, 2) an oracle error that would be available if the column space of the matrix were known, and 3) a more adaptive oracle error which would be available with the knowledge of the column space corresponding to the part of the matrix that stands above the noise. Lastly, the error bounds regarding low-rank matrices are extended to provide an error bound when the matrix has full rank with decaying singular values. The analysis in this paper is based on the restricted isometry property (RIP) introduced in [6] for vectors, and in [22] for matrices.
Improving Human-Computer Interaction by Developing Culture-sensitive Applications based on Common Sense Knowledge
Venue: arXiv cs.HC 2010
Year: 2010

The advent of Web 3.0, claiming for personalization in interactive systems (Lassila & Hendler, 2007), and the need for systems capable of interacting in a more natural way in the future society flooded with computer systems and devices (Harper et al., 2008) show that great advances in HCI should be done. This chapter presents some contributions of LIA for the future of HCI, defending that using common sense knowledge is a possibility for improving HCI, especially because people assign meaning to their messages based on their common sense and, therefore, the use of this knowledge in developing user interfaces can make them more intuitive to the end-user. Moreover, as common sense knowledge varies from group to group of people, it can be used for developing applications capable of giving different feedback for different target groups, as the applications presented along this chapter illustrate, allowing, in this way, interface personalization taking into account cultural issues. For the purpose of using common sense knowledge in the development and design of computer systems, it is necessary to provide an architecture that allows it. This chapter presents LIAs approaches for common sense knowledge acquisition, representation and use, as well as for natural language processing, contributing with those ones who intent to get into this challenging world to get started.
Tutoring System for Dance Learning
Venue: arXiv cs.IR 2010
Year: 2010

Recent advances in hardware sophistication related to graphics display, audio and video devices made available a large number of multimedia and hypermedia applications. These multimedia applications need to store and retrieve the different forms of media like text, hypertext, graphics, still images, animations, audio and video. Dance is one of the important cultural forms of a nation and dance video is one such multimedia types. Archiving and retrieving the required semantics from these dance media collections is a crucial and demanding multimedia application. This paper summarizes the difference dance video archival techniques and systems. Keywords: Multimedia, Culture Media, Metadata archival and retrieval systems, MPEG-7, XML.
Discovering Knowledge from Multi-modal Lecture Recordings
Venue: arXiv cs.MM 2010
Year: 2010

Educational media mining is the process of converting raw media data from educational systems to useful information that can be used to design learning systems, answer research questions and allow personalized learning experiences. Knowledge discovery encompasses a wide range of techniques ranging from database queries to more recent developments in machine learning and language technology. Educational media mining techniques are now being used in IT Services research worldwide. Multi-modal Lecture Recordings is one of the important types of educational media and this paper explores the research challenges for mining lecture recordings for the efficient personalized learning experiences. Keywords: Educational Media Mining; Lecture Recordings, Multimodal Information System, Personalized Learning; Online Course Ware; Skills and Competences;
On a Tree and a Path with no Geometric Simultaneous Embedding
Venue: arXiv cs.CG 2010
Year: 2010

Two graphs $G_1=(V,E_1)$ and $G_2=(V,E_2)$ admit a geometric simultaneous embedding if there exists a set of points P and a bijection M: P -> V that induce planar straight-line embeddings both for $G_1$ and for $G_2$. While it is known that two caterpillars always admit a geometric simultaneous embedding and that two trees not always admit one, the question about a tree and a path is still open and is often regarded as the most prominent open problem in this area. We answer this question in the negative by providing a counterexample. Additionally, since the counterexample uses disjoint edge sets for the two graphs, we also negatively answer another open question, that is, whether it is possible to simultaneously embed two edge-disjoint trees. As a final result, we study the same problem when some constraints on the tree are imposed. Namely, we show that a tree of depth 2 and a path always admit a geometric simultaneous embedding. In fact, such a strong constraint is not so far from closing the gap with the instances not admitting any solution, as the tree used in our counterexample has depth 4.
Asynchronous deterministic rendezvous in bounded terrains
Venue: arXiv cs.CG 2010
Year: 2010

Two mobile agents (robots) have to meet in an a priori unknown bounded terrain modeled as a polygon, possibly with polygonal obstacles. Agents are modeled as points, and each of them is equipped with a compass. Compasses of agents may be incoherent. Agents construct their routes, but the actual walk of each agent is decided by the adversary: the movement of the agent can be at arbitrary speed, the agent may sometimes stop or go back and forth, as long as the walk of the agent in each segment of its route is continuous, does not leave it and covers all of it. We consider several scenarios, depending on three factors: (1) obstacles in the terrain are present, or not, (2) compasses of both agents agree, or not, (3) agents have or do not have a map of the terrain with their positions marked. The cost of a rendezvous algorithm is the worst-case sum of lengths of the agents' trajectories until their meeting. For each scenario we design a deterministic rendezvous algorithm and analyze its cost. We also prove lower bounds on the cost of any deterministic rendezvous algorithm in each case. For all scenarios these bounds are tight.
How to meet asynchronously (almost) everywhere
Venue: arXiv cs.DS 2010
Year: 2010

Two mobile agents (robots) with distinct labels have to meet in an arbitrary, possibly infinite, unknown connected graph or in an unknown connected terrain in the plane. Agents are modeled as points, and the route of each of them only depends on its label and on the unknown environment. The actual walk of each agent also depends on an asynchronous adversary that may arbitrarily vary the speed of the agent, stop it, or even move it back and forth, as long as the walk of the agent in each segment of its route is continuous, does not leave it and covers all of it. Meeting in a graph means that both agents must be at the same time in some node or in some point inside an edge of the graph, while meeting in a terrain means that both agents must be at the same time in some point of the terrain. Does there exist a deterministic algorithm that allows any two agents to meet in any unknown environment in spite of this very powerfull adversary? We give deterministic rendezvous algorithms for agents starting at arbitrary nodes of any anonymous connected graph (finite or infinite) and for agents starting at any interior points with rational coordinates in any closed region of the plane with path-connected interior. While our algorithms work in a very general setting ? agents can, indeed, meet almost everywhere ? we show that none of the above few limitations imposed on the environment can be removed. On the other hand, our algorithm also guarantees the following approximate rendezvous for agents starting at arbitrary interior points of a terrain as above: agents will eventually get at an arbitrarily small positive distance from each other.
Online Correlation Clustering
Venue: arXiv cs.DS 2010
Year: 2010

We study the online clustering problem where data items arrive in an online fashion. The algorithm maintains a clustering of data items into similarity classes. Upon arrival of v, the relation between v and previously arrived items is revealed, so that for each u we are told whether v is similar to u. The algorithm can create a new cluster for v and merge existing clusters. When the objective is to minimize disagreements between the clustering and the input, we prove that a natural greedy algorithm is O(n)-competitive, and this is optimal. When the objective is to maximize agreements between the clustering and the input, we prove that the greedy algorithm is .5-competitive; that no online algorithm can be better than .834-competitive; we prove that it is possible to get better than 1/2, by exhibiting a randomized algorithm with competitive ratio .5+c for a small positive fixed constant c.
Optimal Thresholds for GMD Decoding with (L+1)/L-extended Bounded Distance Decoders
Venue: arXiv cs.IT 2010
Year: 2010

We investigate threshold-based multi-trial decoding of concatenated codes with an inner Maximum-Likelihood decoder and an outer error/erasure (L+1)/L-extended Bounded Distance decoder, i.e. a decoder which corrects e errors and t erasures if e(L+1)/L + t <= d - 1, where d is the minimum distance of the outer code and L is a positive integer. This is a generalization of Forney's GMD decoding, which was considered only for L = 1, i.e. outer Bounded Minimum Distance decoding. One important example for (L+1)/L-extended Bounded Distance decoders is decoding of L-Interleaved Reed-Solomon codes. Our main contribution is a threshold location formula, which allows to optimally erase unreliable inner decoding results, for a given number of decoding trials and parameter L. Thereby, the term optimal means that the residual codeword error probability of the concatenated code is minimized. We give an estimation of this probability for any number of decoding trials.
Redundancy in Systems which Entertain a Model of Themselves: Interaction Information and the Self-organization of Anticipation
Venue: arXiv cs.IR 2010
Year: 2010

Mutual information among three or more dimensions (mu-star = - Q) has been considered as interaction information. However, Krippendorff (2009a, 2009b) has shown that this measure cannot be interpreted as a unique property of the interactions and has proposed an alternative measure of interaction information based on iterative approximation of maximum entropies. Q can then be considered as a measure of the difference between interaction information and redundancy generated in a model entertained by an observer. I argue that this provides us with a measure of the imprint of a second-order observing system -- a model entertained by the system itself -- on the underlying information processing. The second-order system communicates meaning hyper-incursively; an observation instantiates this meaning-processing within the information processing. The net results may add to or reduce the prevailing uncertainty. The model is tested empirically for the case where textual organization can be expected to contain intellectual organization in terms of distributions of title words, author names, and cited references.
Pure Parsimony Xor Haplotyping
Venue: arXiv cs.CE 2010
Year: 2010

The haplotype resolution from xor-genotype data has been recently formulated as a new model for genetic studies. The xor-genotype data is a cheaply obtainable type of data distinguishing heterozygous from homozygous sites without identifying the homozygous alleles. In this paper we propose a formulation based on a well-known model used in haplotype inference: pure parsimony. We exhibit exact solutions of the problem by providing polynomial time algorithms for some restricted cases and a fixed-parameter algorithm for the general case. These results are based on some interesting combinatorial properties of a graph representation of the solutions. Furthermore, we show that the problem has a polynomial time k-approximation, where k is the maximum number of xor-genotypes containing a given SNP. Finally, we propose a heuristic and produce an experimental analysis showing that it scales to real-world large instances taken from the HapMap project.