OpenRaiser/Intern-Atlas huggingface dataset:
Preference-based Search using Example-Critiquing with Suggestions
Venue: arXiv cs.AI 2011
Year: 2011

We consider interactive tools that help users search for their most preferred item in a large collection of options. In particular, we examine example-critiquing, a technique for enabling users to incrementally construct preference models by critiquing example options that are presented to them. We present novel techniques for improving the example-critiquing technology by adding suggestions to its displayed options. Such suggestions are calculated based on an analysis of users current preference model and their potential hidden preferences. We evaluate the performance of our model-based suggestion techniques with both synthetic and real users. Results show that such suggestions are highly attractive to users and can stimulate them to express more preferences to improve the chance of identifying their most preferred item by up to 78%.
Anytime Point-Based Approximations for Large POMDPs
Venue: arXiv cs.AI 2011
Year: 2011

The Partially Observable Markov Decision Process has long been recognized as a rich framework for real-world planning and control problems, especially in robotics. However exact solutions in this framework are typically computationally intractable for all but the smallest problems. A well-known technique for speeding up POMDP solving involves performing value backups at specific belief points, rather than over the entire belief simplex. The efficiency of this approach, however, depends greatly on the selection of points. This paper presents a set of novel techniques for selecting informative belief points which work well in practice. The point selection procedure is combined with point-based value backups to form an effective anytime POMDP algorithm called Point-Based Value Iteration (PBVI). The first aim of this paper is to introduce this algorithm and present a theoretical analysis justifying the choice of belief selection technique. The second aim of this paper is to provide a thorough empirical comparison between PBVI and other state-of-the-art POMDP methods, in particular the Perseus algorithm, in an effort to highlight their similarities and differences. Evaluation is performed using both standard POMDP domains and realistic robotic tasks.
Secure and Privacy- Aware Searching in Peer-to-Peer Networks
Venue: arXiv cs.CR 2011
Year: 2011

The existing peer-to-peer networks have several problems such as fake content distribution, free riding, white-washing and poor search scalability, lack of a robust trust model and absence of user privacy protection mechanism. Although, several trust management and semantic community-based mechanisms for combating free riding and distribution of malicious contents have been proposed by some researchers, most of these schemes lack scalability due to their high computational, communication and storage overhead. This paper presents a robust trust management scheme for P2P networks that utilizes topology adaptation by constructing an overlay of trusted peers where the neighbors are selected based on their trust ratings and content similarities. While increasing the search efficiency by intelligently exploiting the formation of semantic community structures by topology adaptation among the trustworthy peers, the scheme provides the users a very high level of privacy protection of their usage and consumption patterns of network resources. Simulation results demonstrate that the proposed scheme provides efficient searching to good peers while penalizing the malicious peers by increasing their search times as the network topology stabilizes.
An efficient algorithm to find a set of nearest elements in a mesh
Venue: arXiv cs.DS 2011
Year: 2011

A linear time algorithm to find a set of nearest elements in a mesh.
Rate-Dependent Analysis of the Asymptotic Behavior of Channel Polarization
Venue: arXiv cs.IT 2011
Year: 2011

For a binary-input memoryless symmetric channel $W$, we consider the asymptotic behavior of the polarization process in the large block-length regime when transmission takes place over $W$. In particular, we study the asymptotics of the cumulative distribution $\mathbb{P}(Z_n \leq z)$, where $\{Z_n\}$ is the Bhattacharyya process defined from $W$, and its dependence on the rate of transmission. On the basis of this result, we characterize the asymptotic behavior, as well as its dependence on the rate, of the block error probability of polar codes using the successive cancellation decoder. This refines the original bounds by Arıkan and Telatar. Our results apply to general polar codes based on $\ell \times \ell$ kernel matrices. We also provide lower bounds on the block error probability of polar codes using the MAP decoder. The MAP lower bound and the successive cancellation upper bound coincide when $\ell=2$, but there is a gap for $\ell>2$.
Eclectic Extraction of Propositional Rules from Neural Networks
Venue: arXiv cs.LG 2011
Year: 2011

Artificial Neural Network is among the most popular algorithm for supervised learning. However, Neural Networks have a well-known drawback of being a "Black Box" learner that is not comprehensible to the Users. This lack of transparency makes it unsuitable for many high risk tasks such as medical diagnosis that requires a rational justification for making a decision. Rule Extraction methods attempt to curb this limitation by extracting comprehensible rules from a trained Network. Many such extraction algorithms have been developed over the years with their respective strengths and weaknesses. They have been broadly categorized into three types based on their approach to use internal model of the Network. Eclectic Methods are hybrid algorithms that combine the other approaches to attain more performance. In this paper, we present an Eclectic method called HERETIC. Our algorithm uses Inductive Decision Tree learning combined with information of the neural network structure for extracting logical rules. Experiments and theoretical analysis show HERETIC to be better in terms of speed and performance.
Distributed Maximal Matching: Greedy is Optimal
Venue: arXiv cs.DC 2011
Year: 2011

We study distributed algorithms that find a maximal matching in an anonymous, edge-coloured graph. If the edges are properly coloured with $k$ colours, there is a trivial greedy algorithm that finds a maximal matching in $k-1$ synchronous communication rounds. The present work shows that the greedy algorithm is optimal in the general case: any algorithm that finds a maximal matching in anonymous, $k$-edge-coloured graphs requires $k-1$ rounds. If we focus on graphs of maximum degree $Δ$, it is known that a maximal matching can be found in $O(Δ+ \log^* k)$ rounds, and prior work implies a lower bound of $Ω(\polylog(Δ) + \log^* k)$ rounds. Our work closes the gap between upper and lower bounds: the complexity is $Θ(Δ+ \log^* k)$ rounds. To our knowledge, this is the first linear-in-$Δ$ lower bound for the distributed complexity of a classical graph problem.
Exact Dynamic Support Tracking with Multiple Measurement Vectors using Compressive MUSIC
Venue: arXiv cs.IT 2011
Year: 2011

Dynamic tracking of sparse targets has been one of the important topics in array signal processing. Recently, compressed sensing (CS) approaches have been extensively investigated as a new tool for this problem using partial support information obtained by exploiting temporal redundancy. However, most of these approaches are formulated under single measurement vector compressed sensing (SMV-CS) framework, where the performance guarantees are only in a probabilistic manner. The main contribution of this paper is to allow \textit{deterministic} tracking of time varying supports with multiple measurement vectors (MMV) by exploiting multi-sensor diversity. In particular, we show that a novel compressive MUSIC (CS-MUSIC) algorithm with optimized partial support selection not only allows removal of inaccurate portion of previous support estimation but also enables addition of newly emerged part of unknown support. Numerical results confirm the theory.
Diversity Order Vs Rate in an AWGN Channel
Venue: arXiv cs.IT 2011
Year: 2011

We study the diversity order vs rate of an additive white Gaussian noise (AWGN) channel in the whole capacity region. We show that for discrete input as well as for continuous input, Gallager's upper bounds on error probability have exponential diversity in low and high rate region but only subexponential in the mid-rate region. For the best available lower bounds and for the practical codes one observes exponential diversity throughout the capacity region. However we also show that performance of practical codes is close to Gallager's upper bounds and the mid-rate subexponential diversity has a bearing on the performance of the practical codes. Finally we show that the upper bounds with Gaussian input provide good approximation throughout the capacity region even for finite constellation.
On the Parameterized Complexity of Default Logic and Autoepistemic Logic
Venue: arXiv cs.CC 2011
Year: 2011

We investigate the application of Courcelle's Theorem and the logspace version of Elberfeld etal. in the context of the implication problem for propositional sets of formulae, the extension existence problem for default logic, as well as the expansion existence problem for autoepistemic logic and obtain fixed-parameter time and space efficient algorithms for these problems. On the other hand, we exhibit, for each of the above problems, families of instances of a very simple structure that, for a wide range of different parameterizations, do not have efficient fixed-parameter algorithms (even in the sense of the large class XPnu), unless P=NP.
Energy Aware Scheduling for Weighted Completion Time and Weighted Tardiness
Venue: arXiv cs.DM 2011
Year: 2011

The ever increasing adoption of mobile devices with limited energy storage capacity, on the one hand, and more awareness of the environmental impact of massive data centres and server pools, on the other hand, have both led to an increased interest in energy management algorithms. The main contribution of this paper is to present several new constant factor approximation algorithms for energy aware scheduling problems where the objective is to minimize weighted completion time plus the cost of the energy consumed, in the one machine non-preemptive setting, while allowing release dates and deadlines.Unlike previous known algorithms these new algorithms can handle general job-dependent energy cost functions, extending the application of these algorithms to settings outside the typical CPU-energy one. These new settings include problems where in addition, or instead, of energy costs we also have maintenance costs, wear and tear, replacement costs, etc., which in general depend on the speed at which the machine runs but also depend on the types of jobs processed. Our algorithms also extend to approximating weighted tardiness plus energy cost, an inherently more difficult problem that has not been addressed in the literature.
Analytical Forms for Most Likely Matrices Derived from Incomplete Information
Venue: arXiv cs.IT 2011
Year: 2011

Consider a rectangular matrix describing some type of communication or transportation between a set of origins and a set of destinations, or a classification of objects by two attributes. The problem is to infer the entries of the matrix from limited information in the form of constraints, generally the sums of the elements over various subsets of the matrix, such as rows, columns, etc, or from bounds on these sums, down to individual elements. Such problems are routinely addressed by applying the maximum entropy method to compute the matrix numerically, but in this paper we derive analytical, closed-form solutions. For the most complicated cases we consider the solution depends on the root of a non-linear equation, for which we provide an analytical approximation in the form of a power series. Some of our solutions extend to 3-dimensional matrices. Besides being valid for matrices of arbitrary size, the analytical solutions exhibit many of the appealing properties of maximum entropy, such as precise use of the available data, intuitive behavior with respect to changes in the constraints, and logical consistency.
Block-Orthogonal Space-Time Code Structure and Its Impact on QRDM Decoding Complexity Reduction
Venue: arXiv cs.IT 2011
Year: 2011

Full-rate space time codes (STC) with rate = number of transmit antennas have high multiplexing gain, but high decoding complexity even when decoded using reduced-complexity decoders such as sphere or QRDM decoders. In this paper, we introduce a new code property of STC called block-orthogonal property, which can be exploited by QR-decomposition-based decoders to achieve significant decoding complexity reduction without performance loss. We show that such complexity reduction principle can benefit the existing algebraic codes such as Perfect and DjABBA codes due to their inherent (but previously undiscovered) block-orthogonal property. In addition, we construct and optimize new full-rate BOSTC (Block-Orthogonal STC) that further maximize the QRDM complexity reduction potential. Simulation results of bit error rate (BER) performance against decoding complexity show that the new BOSTC outperforms all previously known codes as long as the QRDM decoder operates in reduced-complexity mode, and the code exhibits a desirable complexity saturation property.
Wireless Connectivity and Capacity
Venue: arXiv cs.DS 2011
Year: 2011

Given $n$ wireless transceivers located in a plane, a fundamental problem in wireless communications is to construct a strongly connected digraph on them such that the constituent links can be scheduled in fewest possible time slots, assuming the SINR model of interference. In this paper, we provide an algorithm that connects an arbitrary point set in $O(\log n)$ slots, improving on the previous best bound of $O(\log^2 n)$ due to Moscibroda. This is complemented with a super-constant lower bound on our approach to connectivity. An important feature is that the algorithms allow for bi-directional (half-duplex) communication. One implication of this result is an improved bound of $Ω(1/\log n)$ on the worst-case capacity of wireless networks, matching the best bound known for the extensively studied average-case. We explore the utility of oblivious power assignments, and show that essentially all such assignments result in a worst case bound of $Ω(n)$ slots for connectivity. This rules out a recent claim of a $O(\log n)$ bound using oblivious power. On the other hand, using our result we show that $O(\min(\log Δ, \log n \cdot (\log n + \log \log Δ)))$ slots suffice, where $Δ$ is the ratio between the largest and the smallest links in a minimum spanning tree of the points. Our results extend to the related problem of minimum latency aggregation scheduling, where we show that aggregation scheduling with $O(\log n)$ latency is possible, improving upon the previous best known latency of $O(\log^3 n)$. We also initiate the study of network design problems in the SINR model beyond strong connectivity, obtaining similar bounds for biconnected and $k$-edge connected structures.
Parallel Instantiation of ASP Programs: Techniques and Experiments
Venue: arXiv cs.PL 2011
Year: 2011

Answer Set Programming (ASP) is a powerful logic-based programming language, which is enjoying increasing interest within the scientific community and (very recently) in industry. The evaluation of ASP programs is traditionally carried out in two steps. At the first step an input program P undergoes the so-called instantiation (or grounding) process, which produces a program P' semantically equivalent to P, but not containing any variable; in turn, P' is evaluated by using a backtracking search algorithm in the second step. It is well-known that instantiation is important for the efficiency of the whole evaluation, might become a bottleneck in common situations, is crucial in several realworld applications, and is particularly relevant when huge input data has to be dealt with. At the time of this writing, the available instantiator modules are not able to exploit satisfactorily the latest hardware, featuring multi-core/multi-processor SMP (Symmetric MultiProcessing) technologies. This paper presents some parallel instantiation techniques, including load-balancing and granularity control heuristics, which allow for the effective exploitation of the processing power offered by modern SMP machines. This is confirmed by an extensive experimental analysis herein reported. To appear in Theory and Practice of Logic Programming (TPLP). KEYWORDS: Answer Set Programming, Instantiation, Parallelism, Heuristics
A Near-Optimal Sublinear-Time Algorithm for Approximating the Minimum Vertex Cover Size
Venue: arXiv cs.DS 2011
Year: 2011

We give a nearly optimal sublinear-time algorithm for approximating the size of a minimum vertex cover in a graph G. The algorithm may query the degree deg(v) of any vertex v of its choice, and for each 1 <= i <= deg(v), it may ask for the i-th neighbor of v. Letting VC_opt(G) denote the minimum size of vertex cover in G, the algorithm outputs, with high constant success probability, an estimate VC_estimate(G) such that VC_opt(G) <= VC_estimate(G) <= 2 * VC_opt(G) + epsilon*n, where epsilon is a given additive approximation parameter. We refer to such an estimate as a (2,epsilon)-estimate. The query complexity and running time of the algorithm are ~O(avg_deg * poly(1/epsilon)), where avg_deg denotes the average vertex degree in the graph. The best previously known sublinear algorithm, of Yoshida et al. (STOC 2009), has query complexity and running time O(d^4/epsilon^2), where d is the maximum degree in the graph. Given the lower bound of Omega(avg_deg) (for constant epsilon) for obtaining such an estimate (with any constant multiplicative factor) due to Parnas and Ron (TCS 2007), our result is nearly optimal. In the case that the graph is dense, that is, the number of edges is Theta(n^2), we consider another model, in which the algorithm may ask, for any pair of vertices u and v, whether there is an edge between u and v. We show how to adapt the algorithm that uses neighbor queries to this model and obtain an algorithm that outputs a (2,epsilon)-estimate of the size of a minimum vertex cover whose query complexity and running time are ~O(n) * poly(1/epsilon).
Efficient Encoding of Watermark Numbers as Reducible Permutation Graphs
Venue: arXiv cs.DS 2011
Year: 2011

In a software watermarking environment, several graph theoretic watermark methods use numbers as watermark values, where some of these methods encode the watermark numbers as graph structures. In this paper we extended the class of error correcting graphs by proposing an efficient and easily implemented codec system for encoding watermark numbers as reducible permutation flow-graphs. More precisely, we first present an efficient algorithm which encodes a watermark number $w$ as self-inverting permutation $π^*$ and, then, an algorithm which encodes the self-inverting permutation $π^*$ as a reducible permutation flow-graph $F[π^*]$ by exploiting domination relations on the elements of $π^*$ and using an efficient DAG representation of $π^*$. The whole encoding process takes O(n) time and space, where $n$ is the binary size of the number $w$ or, equivalently, the number of elements of the permutation $π^*$. We also propose efficient decoding algorithms which extract the number $w$ from the reducible permutation flow-graph $F[π^*]$ within the same time and space complexity. The two main components of our proposed codec system, i.e., the self-inverting permutation $π^*$ and the reducible permutation graph $F[π^*]$, incorporate important structural properties which make our system resilient to attacks.
Feasible Automata for Two-Variable Logic with Successor on Data Words
Venue: arXiv cs.FL 2011
Year: 2011

We introduce an automata model for data words, that is words that carry at each position a symbol from a finite alphabet and a value from an unbounded data domain. The model is (semantically) a restriction of data automata, introduced by Bojanczyk, et. al. in 2006, therefore it is called weak data automata. It is strictly less expressive than data automata and the expressive power is incomparable with register automata. The expressive power of weak data automata corresponds exactly to existential monadic second order logic with successor +1 and data value equality \sim, EMSO2(+1,\sim). It follows from previous work, David, et. al. in 2010, that the nonemptiness problem for weak data automata can be decided in 2-NEXPTIME. Furthermore, we study weak Büchi automata on data omega-strings. They can be characterized by the extension of EMSO2(+1,\sim) with existential quantifiers for infinite sets. Finally, the same complexity bound for its nonemptiness problem is established by a nondeterministic polynomial time reduction to the nonemptiness problem of weak data automata.
Getting routers out of the core: Building an optical wide area network with "multipaths"
Venue: arXiv cs.NI 2011
Year: 2011

We propose an all-optical networking solution for a wide area network (WAN) based on the notion of multipoint-to-multipoint lightpaths that, for short, we call "multipaths". A multipath concentrates the traffic of a group of source nodes on a wavelength channel using an adapted MAC protocol and multicasts this traffic to a group of destination nodes that extract their own data from the confluent stream. The proposed network can be built using existing components and appears less complex and more efficient in terms of energy consumption than alternatives like OPS and OBS. The paper presents the multipath architecture and compares its energy consumption to that of a classical router-based ISP network. A flow-aware dynamic bandwidth allocation algorithm is proposed and shown to have excellent performance in terms of throughput and delay.
Discovering patterns of correlation and similarities in software project data with the Circos visualization tool
Venue: arXiv cs.SE 2011
Year: 2011

Software cost estimation based on multivariate data from completed projects requires the building of efficient models. These models essentially describe relations in the data, either on the basis of correlations between variables or of similarities between the projects. The continuous growth of the amount of data gathered and the need to perform preliminary analysis in order to discover patterns able to drive the building of reasonable models, leads the researchers towards intelligent and time-saving tools which can effectively describe data and their relationships. The goal of this paper is to suggest an innovative visualization tool, widely used in bioinformatics, which represents relations in data in an aesthetic and intelligent way. In order to illustrate the capabilities of the tool, we use a well known dataset from software engineering projects.
Supporting the Curation of Twitter User Lists
Venue: arXiv cs.SI 2011
Year: 2011

Twitter introduced lists in late 2009 as a means of curating tweets into meaningful themes. Lists were quickly adopted by media companies as a means of organising content around news stories. Thus the curation of these lists is important, they should contain the key information gatekeepers and present a balanced perspective on the story. Identifying members to add to a list on an emerging topic is a delicate process. From a network analysis perspective there are a number of views on the Twitter network that can be explored, e.g. followers, retweets mentions etc. We present a process for integrating these views in order to recommend authoritative commentators to include on a list. This process is evaluated on manually curated lists about unrest in Bahrain and the Iowa caucuses for the 2012 US election.