OpenRaiser/Intern-Atlas huggingface dataset:
Constraint-Based Heuristic On-line Test Generation from Non-deterministic I/O EFSMs
Venue: arXiv cs.SE 2012
Year: 2012

We are investigating on-line model-based test generation from non-deterministic output-observable Input/Output Extended Finite State Machine (I/O EFSM) models of Systems Under Test (SUTs). We propose a novel constraint-based heuristic approach (Heuristic Reactive Planning Tester (xRPT)) for on-line conformance testing non-deterministic SUTs. An indicative feature of xRPT is the capability of making reasonable decisions for achieving the test goals in the on-line testing process by using the results of off-line bounded static reachability analysis based on the SUT model and test goal specification. We present xRPT in detail and make performance comparison with other existing search strategies and approaches on examples with varying complexity.
Precoder Design for Multi-antenna Partial Decode-and-Forward (PDF) Cooperative Systems with Statistical CSIT and MMSE-SIC Receivers
Venue: arXiv cs.IT 2012
Year: 2012

Cooperative communication is an important technology in next generation wireless networks. Aside from conventional amplify-and-forward (AF) and decode-and-forward (DF) protocols, the partial decode-and-forward (PDF) protocol is an alternative relaying scheme that is especially promising for scenarios in which the relay node cannot reliably decode the complete source message. However, there are several important issues to be addressed regarding the application of PDF protocols. In this paper, we propose a PDF protocol and MIMO precoder designs at the source and relay nodes. The precoder designs are adapted based on statistical channel state information for correlated MIMO channels, and matched to practical minimum mean-square-error successive interference cancelation (MMSE-SIC) receivers at the relay and destination nodes. We show that under similar system settings, the proposed MIMO precoder design with PDF protocol and MMSE-SIC receivers achieves substantial performance enhancement compared with conventional baselines.
Can Intelligence Explode?
Venue: arXiv cs.AI 2012
Year: 2012

The technological singularity refers to a hypothetical scenario in which technological advances virtually explode. The most popular scenario is the creation of super-intelligent algorithms that recursively create ever higher intelligences. It took many decades for these ideas to spread from science fiction to popular science magazines and finally to attract the attention of serious philosophers. David Chalmers' (JCS 2010) article is the first comprehensive philosophical analysis of the singularity in a respected philosophy journal. The motivation of my article is to augment Chalmers' and to discuss some issues not addressed by him, in particular what it could mean for intelligence to explode. In this course, I will (have to) provide a more careful treatment of what intelligence actually is, separate speed from intelligence explosion, compare what super-intelligent participants and classical human observers might experience and do, discuss immediate implications for the diversity and value of life, consider possible bounds on intelligence, and contemplate intelligences right at the singularity.
The FC-rank of a context-free language
Venue: arXiv cs.FL 2012
Year: 2012

We prove that the finite condensation rank (FC-rank) of the lexicographic ordering of a context-free language is strictly less than $ω^ω$.
Relational Reinforcement Learning in Infinite Mario
Venue: arXiv cs.AI 2012
Year: 2012

Relational representations in reinforcement learning allow for the use of structural information like the presence of objects and relationships between them in the description of value functions. Through this paper, we show that such representations allow for the inclusion of background knowledge that qualitatively describes a state and can be used to design agents that demonstrate learning behavior in domains with large state and actions spaces such as computer games.
Functions that preserve p-randomness
Venue: arXiv cs.CC 2012
Year: 2012

We show that polynomial-time randomness (p-randomness) is preserved under a variety of familiar operations, including addition and multiplication by a nonzero polynomial-time computable real number. These results follow from a general theorem: If $I$ is an open interval in the reals, $f$ is a function mapping $I$ into the reals, and $r$ in $I$ is p-random, then $f(r)$ is p-random provided 1. $f$ is p-computable on the dyadic rational points in $I$, and 2. $f$ varies sufficiently at $r$, i.e., there exists a real constant $C > 0$ such that either (a) $(f(x) - f(r))/(x-r) > C$ for all $x$ in $I$ with $x \ne r$, or (b) $(f(x) - f(r))(x-r) < -C$ for all $x$ in $I$ with $x \ne r$. Our theorem implies in particular that any analytic function about a p-computable point whose power series has uniformly p-computable coefficients preserves p-randomness in its open interval of absolute convergence. Such functions include all the familiar functions from first-year calculus.
Solving Tantrix via Integer Programming
Venue: arXiv cs.DM 2012
Year: 2012

Tantrix is a puzzle to make a loop by connecting lines drawn on hexagonal tiles, and the objective of this research is to solve it by a computer. For this purpose, we give a problem setting of solving Tantrix as arranging tiles in an appropriate shape and making a loop at the same time within a given hexagonal lattice board. We then formulate it as an integer program by expressing the rules of Tantrix as its constraints, and solve it by a mathematical programming solver to have a solution. As a result, we establish a formulation that solves Tantrix of moderate sizes, and even when the solutions are invalid only by elementary constraints, we achieved it by introducing additional constraints and an artificial objective function to avoid flaws in invalid solutions. By this approach we are successful in solving Tantrix of size up to 50.
mlpy: Machine Learning Python
Venue: arXiv cs.MS 2012
Year: 2012

mlpy is a Python Open Source Machine Learning library built on top of NumPy/SciPy and the GNU Scientific Libraries. mlpy provides a wide range of state-of-the-art machine learning methods for supervised and unsupervised problems and it is aimed at finding a reasonable compromise among modularity, maintainability, reproducibility, usability and efficiency. mlpy is multiplatform, it works with Python 2 and 3 and it is distributed under GPL3 at the website http://mlpy.fbk.eu.
Adaptive sensing using deterministic partial Hadamard matrices
Venue: arXiv cs.IT 2012
Year: 2012

This paper investigates the construction of deterministic matrices preserving the entropy of random vectors with a given probability distribution. In particular, it is shown that for random vectors having i.i.d. discrete components, this is achieved by selecting a subset of rows of a Hadamard matrix such that (i) the selection is deterministic (ii) the fraction of selected rows is vanishing. In contrast, it is shown that for random vectors with i.i.d. continuous components, no partial Hadamard matrix of reduced dimension allows to preserve the entropy. These results are in agreement with the results of Wu-Verdu on almost lossless analog compression. This paper is however motivated by the complexity attribute of Hadamard matrices, which allows the use of efficient and stable reconstruction algorithms. The proof technique is based on a polar code martingale argument and on a new entropy power inequality for integer-valued random variables.
A Lexical Analysis Tool with Ambiguity Support
Venue: arXiv cs.CL 2012
Year: 2012

Lexical ambiguities naturally arise in languages. We present Lamb, a lexical analyzer that produces a lexical analysis graph describing all the possible sequences of tokens that can be found within the input string. Parsers can process such lexical analysis graphs and discard any sequence of tokens that does not produce a valid syntactic sentence, therefore performing, together with Lamb, a context-sensitive lexical analysis in lexically-ambiguous language specifications.
Filling-Based Techniques Applied to Object Projection Feature Estimation
Venue: arXiv cs.CV 2012
Year: 2012

3D motion tracking is a critical task in many computer vision applications. Unsupervised markerless 3D motion tracking systems determine the most relevant object in the screen and then track it by continuously estimating its projection features (center and area) from the edge image and a point inside the relevant object projection (namely, inner point), until the tracking fails. Existing object projection feature estimation techniques are based on ray-casting from the inner point. These techniques present three main drawbacks: when the inner point is surrounded by edges, rays may not reach other relevant areas; as a consequence of that issue, the estimated features may greatly vary depending on the position of the inner point relative to the object projection; and finally, increasing the number of rays being casted and the ray-casting iterations (which would make the results more accurate and stable) increases the processing time to the point the tracking cannot be performed on the fly. In this paper, we analyze an intuitive filling-based object projection feature estimation technique that solves the aforementioned problems but is too sensitive to edge miscalculations. Then, we propose a less computing-intensive modification to that technique that would not be affected by the existing techniques issues and would be no more sensitive to edge miscalculations than ray-casting-based techniques.
Physical Layer Security with Uncoordinated Helpers Implementing Cooperative Jamming
Venue: arXiv cs.IT 2012
Year: 2012

A wireless communication network is considered, consisting of a source (Alice), a destination (Bob) and an eavesdropper (Eve), each equipped with a single antenna. The communication is assisted by multiple helpers, each equipped with two antennas, which implement cooperative jamming, i.e., transmitting noise to confound Eve. The optimal structure of the jamming noise that maximizes the secrecy rate is derived. A nulling noise scenario is also considered, in which each helper transmits noise that nulls out at Bob. Each helper only requires knowledge of its own link to Bob to determine the noise locally. For the optimally structured noise, global information of all the links is required. Although analysis shows that under the two-antenna per helper scenario the nulling solution is sub-optimal in terms of the achievable secrecy rate, simulations show that the performance difference is rather small, with the inexpensive and easy to implement nulling scheme performing near optimal.
Optimal Transmission Policies for Energy Harvesting Two-hop Networks
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, a two-hop communication system with energy harvesting nodes is considered. Unlike battery powered wireless nodes, both the source and the relay are able to harvest energy from environment during communication, therefore, both data and energy causality over the two hops need to be considered. Assuming both nodes know the harvested energies in advance, properties of optimal transmission policies to maximize the delivered data by a given deadline are identified. Using these properties, optimal power allocation and transmission schedule for the case in which both nodes harvest two energy packets is developed.
The Complexity of Online Manipulation of Sequential Elections
Venue: arXiv cs.GT 2012
Year: 2012

Most work on manipulation assumes that all preferences are known to the manipulators. However, in many settings elections are open and sequential, and manipulators may know the already cast votes but may not know the future votes. We introduce a framework, in which manipulators can see the past votes but not the future ones, to model online coalitional manipulation of sequential elections, and we show that in this setting manipulation can be extremely complex even for election systems with simple winner problems. Yet we also show that for some of the most important election systems such manipulation is simple in certain settings. This suggests that when using sequential voting, one should pay great attention to the details of the setting in choosing one's voting rule. Among the highlights of our classifications are: We show that, depending on the size of the manipulative coalition, the online manipulation problem can be complete for each level of the polynomial hierarchy or even for PSPACE. We obtain the most dramatic contrast to date between the nonunique-winner and unique-winner models: Online weighted manipulation for plurality is in P in the nonunique-winner model, yet is coNP-hard (constructive case) and NP-hard (destructive case) in the unique-winner model. And we obtain what to the best of our knowledge are the first P^NP[1]-completeness and P^NP-completeness results in the field of computational social choice, in particular proving such completeness for, respectively, the complexity of 3-candidate and 4-candidate (and unlimited-candidate) online weighted coalition manipulation of veto elections.
Connectivity in one-dimensional ad hoc networks with an access point
Venue: arXiv cs.DM 2012
Year: 2012

In this paper, we study the connectivity in one-dimensional ad hoc wireless networks with an fixed access point. In recent years, various closed expressions for the probability of connectivity on one-dimensional networks (interval graphs) have been derived by many researchers. We will provide some numerical validation for them by means of extensive simulations.
Stochastic Database Cracking: Towards Robust Adaptive Indexing in Main-Memory Column-Stores
Venue: arXiv cs.DB 2012
Year: 2012

Modern business applications and scientific databases call for inherently dynamic data storage environments. Such environments are characterized by two challenging features: (a) they have little idle system time to devote on physical design; and (b) there is little, if any, a priori workload knowledge, while the query and data workload keeps changing dynamically. In such environments, traditional approaches to index building and maintenance cannot apply. Database cracking has been proposed as a solution that allows on-the-fly physical data reorganization, as a collateral effect of query processing. Cracking aims to continuously and automatically adapt indexes to the workload at hand, without human intervention. Indexes are built incrementally, adaptively, and on demand. Nevertheless, as we show, existing adaptive indexing methods fail to deliver workload-robustness; they perform much better with random workloads than with others. This frailty derives from the inelasticity with which these approaches interpret each query as a hint on how data should be stored. Current cracking schemes blindly reorganize the data within each query's range, even if that results into successive expensive operations with minimal indexing benefit. In this paper, we introduce stochastic cracking, a significantly more resilient approach to adaptive indexing. Stochastic cracking also uses each query as a hint on how to reorganize data, but not blindly so; it gains resilience and avoids performance bottlenecks by deliberately applying certain arbitrary choices in its decision-making. Thereby, we bring adaptive indexing forward to a mature formulation that confers the workload-robustness previous approaches lacked. Our extensive experimental study verifies that stochastic cracking maintains the desired properties of original database cracking while at the same time it performs well with diverse realistic workloads.
How to Price Shared Optimizations in the Cloud
Venue: arXiv cs.DB 2012
Year: 2012

Data-management-as-a-service systems are increasingly being used in collaborative settings, where multiple users access common datasets. Cloud providers have the choice to implement various optimizations, such as indexing or materialized views, to accelerate queries over these datasets. Each optimization carries a cost and may benefit multiple users. This creates a major challenge: how to select which optimizations to perform and how to share their cost among users. The problem is especially challenging when users are selfish and will only report their true values for different optimizations if doing so maximizes their utility. In this paper, we present a new approach for selecting and pricing shared optimizations by using Mechanism Design. We first show how to apply the Shapley Value Mechanism to the simple case of selecting and pricing additive optimizations, assuming an offline game where all users access the service for the same time-period. Second, we extend the approach to online scenarios where users come and go. Finally, we consider the case of substitutive optimizations. We show analytically that our mechanisms induce truth- fulness and recover the optimization costs. We also show experimentally that our mechanisms yield higher utility than the state-of-the-art approach based on regret accumulation.
Joint Estimation of Angle and Delay of Radio Wave Arrival under Multiplicative Noise Environment
Venue: arXiv cs.CE 2012
Year: 2012

We propose a novel technique for joint estimation of angle and delay of radio wave arrival in a multipath mobile communication channel using knowledge of the transmitted pulse shape function. Employing an array of sensors to sample the radio received signal, and subsequent array signal processing can provide the characterization of a high-rank channel in terms of the multipath angles of arrival and time delays. Although several works have been reported in the literature for estimation of the high-rank channel parameters, we are not aware of any work that deals with the problem of estimation in a fading channel, which essentially leads to a multiplicative noise environment.
Statistical Approach for Selecting Elite Ants
Venue: arXiv cs.NE 2012
Year: 2012

Applications of ACO algorithms to obtain better solutions for combinatorial optimization problems have become very popular in recent years. In ACO algorithms, group of agents repeatedly perform well defined actions and collaborate with other ants in order to accomplish the defined task. In this paper, we introduce new mechanisms for selecting the Elite ants dynamically based on simple statistical tools. We also investigate the performance of newly proposed mechanisms.
Label Cover instances with large girth and the hardness of approximating basic k-spanner
Venue: arXiv cs.DS 2012
Year: 2012

We study the well-known Label Cover problem under the additional requirement that problem instances have large girth. We show that if the girth is some $k$, the problem is roughly $2^{\log^{1-ε} n/k}$ hard to approximate for all constant $ε> 0$. A similar theorem was claimed by Elkin and Peleg [ICALP 2000], but their proof was later found to have a fundamental error. We use the new proof to show inapproximability for the basic $k$-spanner problem, which is both the simplest problem in graph spanners and one of the few for which super-logarithmic hardness was not known. Assuming $NP \not\subseteq BPTIME(2^{polylog(n)})$, we show that for every $k \geq 3$ and every constant $ε> 0$ it is hard to approximate the basic $k$-spanner problem within a factor better than $2^{(\log^{1-ε} n) / k}$ (for large enough $n$). A similar hardness for basic $k$-spanner was claimed by Elkin and Peleg [ICALP 2000], but the error in their analysis of Label Cover made this proof fail as well. Thus for the problem of Label Cover with large girth we give the first non-trivial lower bound. For the basic $k$-spanner problem we improve the previous best lower bound of $Ω(\log n)/k$ by Kortsarz [Algorithmica 1998]. Our main technique is subsampling the edges of 2-query PCPs, which allows us to reduce the degree of a PCP to be essentially equal to the soundness desired. This turns out to be enough to essentially guarantee large girth.
A rearrangement step with potential uses in priority queues
Venue: arXiv cs.DS 2012
Year: 2012

Link-based data structures, such as linked lists and binary search trees, have many well-known rearrangement steps allowing for efficient implementations of insertion, deletion, and other operations. We describe a rearrangement primitive designed for link-based, heap-ordered priority queues in the comparison model, such as those similar to Fibonacci heaps or binomial heaps. In its most basic form, the primitive rearranges a collection of heap-ordered perfect binary trees. Doing so offers a data structure control on the number of trees involved in such a collection, in particular keeping this number logarithmic in the number of elements. The rearrangement step is free from an amortized complexity standpoint (using an appropriate potential function).
A Personalized Tag-Based Recommendation in Social Web Systems
Venue: arXiv cs.SI 2012
Year: 2012

Tagging activity has been recently identified as a potential source of knowledge about personal interests, preferences, goals, and other attributes known from user models. Tags themselves can be therefore used for finding personalized recommendations of items. In this paper, we present a tag-based recommender system which suggests similar Web pages based on the similarity of their tags from a Web 2.0 tagging application. The proposed approach extends the basic similarity calculus with external factors such as tag popularity, tag representativeness and the affinity between user and tag. In order to study and evaluate the recommender system, we have conducted an experiment involving 38 people from 12 countries using data from Del.icio.us, a social bookmarking web system on which users can share their personal bookmarks.
Certified Approximation of Parametric Space Curves with Cubic B-spline Curves
Venue: arXiv cs.CG 2012
Year: 2012

Approximating complex curves with simple parametric curves is widely used in CAGD, CG, and CNC. This paper presents an algorithm to compute a certified approximation to a given parametric space curve with cubic B-spline curves. By certified, we mean that the approximation can approximate the given curve to any given precision and preserve the geometric features of the given curve such as the topology, singular points, etc. The approximated curve is divided into segments called quasi-cubic Bézier curve segments which have properties similar to a cubic rational Bézier curve. And the approximate curve is naturally constructed as the associated cubic rational Bézier curve of the control tetrahedron of a quasi-cubic curve. A novel optimization method is proposed to select proper weights in the cubic rational Bézier curve to approximate the given curve. The error of the approximation is controlled by the size of its tetrahedron, which converges to zero by subdividing the curve segments. As an application, approximate implicit equations of the approximated curves can be computed. Experiments show that the method can approximate space curves of high degrees with high precision and very few cubic Bézier curve segments.