OpenRaiser/Intern-Atlas huggingface dataset:
An experimental study of exhaustive solutions for the Mastermind puzzle
Venue: arXiv cs.NE 2012
Year: 2012

Mastermind is in essence a search problem in which a string of symbols that is kept secret must be found by sequentially playing strings that use the same alphabet, and using the responses that indicate how close are those other strings to the secret one as hints. Although it is commercialized as a game, it is a combinatorial problem of high complexity, with applications on fields that range from computer security to genomics. As such a kind of problem, there are no exact solutions; even exhaustive search methods rely on heuristics to choose, at every step, strings to get the best possible hint. These methods mostly try to play the move that offers the best reduction in search space size in the next step; this move is chosen according to an empirical score. However, in this paper we will examine several state of the art exhaustive search methods and show that another factor, the presence of the actual solution among the candidate moves, or, in other words, the fact that the actual solution has the highest score, plays also a very important role. Using that, we will propose new exhaustive search approaches that obtain results which are comparable to the classic ones, and besides, are better suited as a basis for non-exhaustive search strategies such as evolutionary algorithms, since their behavior in a series of key indicators is better than the classical algorithms.
Cost Sensitive Reachability Heuristics for Handling State Uncertainty
Venue: arXiv cs.AI 2012
Year: 2012

While POMDPs provide a general platform for non-deterministic conditional planning under a variety of quality metrics they have limited scalability. On the other hand, non-deterministic conditional planners scale very well, but many lack the ability to optimize plan quality metrics. We present a novel generalization of planning graph based heuristics that helps conditional planners both scale and generate high quality plans when using actions with nonuniform costs. We make empirical comparisons with two state of the art planners to show the benefit of our techniques.
MAA*: A Heuristic Search Algorithm for Solving Decentralized POMDPs
Venue: arXiv cs.AI 2012
Year: 2012

We present multi-agent A* (MAA*), the first complete and optimal heuristic search algorithm for solving decentralized partially-observable Markov decision problems (DEC-POMDPs) with finite horizon. The algorithm is suitable for computing optimal plans for a cooperative group of agents that operate in a stochastic environment such as multirobot coordination, network traffic control, `or distributed resource allocation. Solving such problems efiectively is a major challenge in the area of planning under uncertainty. Our solution is based on a synthesis of classical heuristic search and decentralized control theory. Experimental results show that MAA* has significant advantages. We introduce an anytime variant of MAA* and conclude with a discussion of promising extensions such as an approach to solving infinite horizon problems.
Models for Truthful Online Double Auctions
Venue: arXiv cs.GT 2012
Year: 2012

Online double auctions (DAs) model a dynamic two-sided matching problem with private information and self-interest, and are relevant for dynamic resource and task allocation problems. We present a general method to design truthful DAs, such that no agent can benefit from misreporting its arrival time, duration, or value. The family of DAs is parameterized by a pricing rule, and includes a generalization of McAfee's truthful DA to this dynamic setting. We present an empirical study, in which we study the allocative-surplus and agent surplus for a number of different DAs. Our results illustrate that dynamic pricing rules are important to provide good market efficiency for markets with high volatility or low volume.
On the Value of Correlation
Venue: arXiv cs.GT 2012
Year: 2012

Correlated equilibrium (Aumann, 1974) generalizes Nash equilibrium to allow correlation devices. Aumann showed an example of a game, and of a correlated equilibrium in this game, in which the agents' surplus (expected sum of payo s) is greater than their surplus in all mixed-strategy equilibria. Following the idea initiated by the price of anarchy literature (Koutsoupias & Papadimitriou, 1999;Papadimitriou, 2001) this suggests the study of two major measures for the value of correlation in a game with non-negative payoffs: 1. The ratio between the maximal surplus obtained in a correlated equilibrium to the maximal surplus obtained in a mixed-strategy equilibrium. We refer to this ratio as the mediation value. 2. The ratio between the maximal surplus to the maximal surplus obtained in a correlated equilibrium. We refer to this ratio as the enforcement value. In this work we initiate the study of the mediation and enforcement values, providing several general results on the value of correlation as captured by these concepts. We also present a set of results for the more specialized case of congestion games (Rosenthal,1973), a class of games that received a lot of attention in the recent literature.
On Privacy-Preserving Histograms
Venue: arXiv cs.DS 2012
Year: 2012

We advance the approach initiated by Chawla et al. for sanitizing (census) data so as to preserve the privacy of respondents while simultaneously extracting "useful" statistical information. First, we extend the scope of their techniques to a broad and rich class of distributions, specifically, mixtures of highdimensional balls, spheres, Gaussians, and other "nice" distributions. Second, we randomize the histogram constructions to preserve spatial characteristics of the data, allowing us to approximate various quantities of interest, e.g., cost of the minimum spanning tree on the data, in a privacy-preserving fashion.
Counterexample-guided Planning
Venue: arXiv cs.AI 2012
Year: 2012

Planning in adversarial and uncertain environments can be modeled as the problem of devising strategies in stochastic perfect information games. These games are generalizations of Markov decision processes (MDPs): there are two (adversarial) players, and a source of randomness. The main practical obstacle to computing winning strategies in such games is the size of the state space. In practice therefore, one typically works with abstractions of the model. The diffculty is to come up with an abstraction that is neither too coarse to remove all winning strategies (plans), nor too fine to be intractable. In verification, the paradigm of counterexample-guided abstraction refinement has been successful to construct useful but parsimonious abstractions automatically. We extend this paradigm to probabilistic models (namely, perfect information games and, as a special case, MDPs). This allows us to apply the counterexample-guided abstraction paradigm to the AI planning problem. As special cases, we get planning algorithms for MDPs and deterministic systems that automatically construct system abstractions.
Bayes Blocks: An Implementation of the Variational Bayesian Building Blocks Framework
Venue: arXiv cs.MS 2012
Year: 2012

A software library for constructing and learning probabilistic models is presented. The library offers a set of building blocks from which a large variety of static and dynamic models can be built. These include hierarchical models for variances of other variables and many nonlinear models. The underlying variational Bayesian machinery, providing for fast and robust estimation but being mathematically rather involved, is almost completely hidden from the user thus making it very easy to use the library. The building blocks include Gaussian, rectified Gaussian and mixture-of-Gaussians variables and computational nodes which can be combined rather freely.
Planning in POMDPs Using Multiplicity Automata
Venue: arXiv cs.AI 2012
Year: 2012

Planning and learning in Partially Observable MDPs (POMDPs) are among the most challenging tasks in both the AI and Operation Research communities. Although solutions to these problems are intractable in general, there might be special cases, such as structured POMDPs, which can be solved efficiently. A natural and possibly efficient way to represent a POMDP is through the predictive state representation (PSR) - a representation which recently has been receiving increasing attention. In this work, we relate POMDPs to multiplicity automata- showing that POMDPs can be represented by multiplicity automata with no increase in the representation size. Furthermore, we show that the size of the multiplicity automaton is equal to the rank of the predictive state representation. Therefore, we relate both the predictive state representation and POMDPs to the well-founded multiplicity automata literature. Based on the multiplicity automata representation, we provide a planning algorithm which is exponential only in the multiplicity automata rank rather than the number of states of the POMDP. As a result, whenever the predictive state representation is logarithmic in the standard POMDP representation, our planning algorithm is efficient.
Sufficient conditions for convergence of Loopy Belief Propagation
Venue: arXiv cs.AI 2012
Year: 2012

We derive novel sufficient conditions for convergence of Loopy Belief Propagation (also known as the Sum-Product algorithm) to a unique fixed point. Our results improve upon previously known conditions. For binary variables with (anti-)ferromagnetic interactions, our conditions seem to be sharp.
Learning to Map Sentences to Logical Form: Structured Classification with Probabilistic Categorial Grammars
Venue: arXiv cs.CL 2012
Year: 2012

This paper addresses the problem of mapping natural language sentences to lambda-calculus encodings of their meaning. We describe a learning algorithm that takes as input a training set of sentences labeled with expressions in the lambda calculus. The algorithm induces a grammar for the problem, along with a log-linear model that represents a distribution over syntactic and semantic analyses conditioned on the input sentence. We apply the method to the task of learning natural language interfaces to databases and show that the learned parsers outperform previous methods in two benchmark database domains.
Velocity/Position Integration Formula (II): Application to Inertial Navigation Computation
Venue: arXiv cs.RO 2012
Year: 2012

Inertial navigation applications are usually referenced to a rotating frame. Consideration of the navigation reference frame rotation in the inertial navigation algorithm design is an important but so far less seriously treated issue, especially for ultra-high-speed flying aircraft or the future ultra-precision navigation system of several meters per hour. This paper proposes a rigorous approach to tackle the issue of navigation frame rotation in velocity/position computation by use of the newly-devised velocity/position integration formulae in the Part I companion paper. The two integration formulae set a well-founded cornerstone for the velocity/position algorithms design that makes the comprehension of the inertial navigation computation principle more accessible to practitioners, and different approximations to the integrals involved will give birth to various velocity/position update algorithms. Two-sample velocity and position algorithms are derived to exemplify the design process. In the context of level-flight airplane examples, the derived algorithm is analytically and numerically compared to the typical algorithms existing in the literature. The results throw light on the problems in existing algorithms and the potential benefits of the derived algorithm.
Achievable Sum-Rates in Gaussian Multiple-Access Channels with MIMO-AF-Relay and Direct Links
Venue: arXiv cs.IT 2012
Year: 2012

We consider a single-antenna Gaussian multiple-access channel (MAC) with a multiple-antenna amplify-and-forward (AF) relay, where, contrary to many previous works, also the direct links between transmitters and receiver are taken into account. For this channel, we investigate two transmit schemes: Sending and relaying all signals jointly or using a time-division multiple-access (TDMA) structure, where only one transmitter uses the channel at a time. While the optimal relaying matrices and time slot durations are found for the latter scheme, we provide upper and lower bounds on the achievable sum-rate for the former one. These bounds are evaluated by Monte Carlo simulations, where it turns out that they are very close to each other. Moreover, these bounds are compared to the sum-rates achieved by the TDMA scheme. For the asymptotic case of high available transmit power at the relay, an analytic expression is given, which allows to determine the superior scheme.
Syntactic vs. Semantic Locality: How Good Is a Cheap Approximation?
Venue: arXiv cs.AI 2012
Year: 2012

Extracting a subset of a given OWL ontology that captures all the ontology's knowledge about a specified set of terms is a well-understood task. This task can be based, for instance, on locality-based modules (LBMs). These come in two flavours, syntactic and semantic, and a syntactic LBM is known to contain the corresponding semantic LBM. For syntactic LBMs, polynomial extraction algorithms are known, implemented in the OWL API, and being used. In contrast, extracting semantic LBMs involves reasoning, which is intractable for OWL 2 DL, and these algorithms had not been implemented yet for expressive ontology languages. We present the first implementation of semantic LBMs and report on experiments that compare them with syntactic LBMs extracted from real-life ontologies. Our study reveals whether semantic LBMs are worth the additional extraction effort, compared with syntactic LBMs.
Fast Constructions of Light-Weight Spanners for General Graphs
Venue: arXiv cs.DS 2012
Year: 2012

To our knowledge, there are only two known algorithms for constructing sparse and light spanners for general graphs. One of them is the greedy algorithm of Alth$\ddot{o}$fer et al. \cite{ADDJS93}, analyzed by Chandra et al. in SoCG'92. The greedy algorithm consructs, for every \emph{weighted} undirected $n$-vertex $m$-edge graph $G = (V,E)$ and any integer $k \ge 1$, a $(2k-1)$-spanner with $O(n^{1 + 1/k})$ edges and weight $O(k \cdot n^{(1+\eps)/k}) \cdot ω(MST(G))$, for any $\eps > 0$. The drawback of the greedy algorithm is that it requires $O(m \cdot (n^{1 + 1/k} + n \cdot \log n))$ time. The other algorithm is due to Awerbuch et al. \cite{ABP91}. It constructs $O(k)$-spanners with $O(k \cdot n^{1 + 1/k} \cdot Λ)$ edges, weight $O(k^2 \cdot n^{1/k} \cdot Λ) \cdot ω(MST(G))$, within time $O(m \cdot k \cdot n^{1/k} \cdot Λ)$, where $Λ$ is the logarithm of the aspect ratio of the graph. The running time of both these algorithms is unsatisfactory. Moreover, the usually faster algorithm of \cite{ABP91} pays for the speedup by significantly increasing both the stretch, the sparsity, and the weight of the resulting spanner. In this paper we devise an efficient algorithm for constructing sparse and light spanners. Specifically, our algorithm constructs $((2k-1) \cdot (1+\eps))$-spanners with $O(k \cdot n^{1 + 1/k})$ edges and weight $O(k \cdot n^{1/k}) \cdot ω(MST(G))$, where $\eps > 0$ is an arbitrarily small constant. The running time of our algorithm is $O(k \cdot m + \min\{n \cdot \log n,m \cdot α(n)\})$. Moreover, by slightly increasing the running time we can reduce the other parameters. These results address an open problem from the ESA'04 paper by Roditty and Zwick \cite{RZ04}.
Performance Evaluation of Widely used Portknoking Algorithms
Venue: arXiv cs.NI 2012
Year: 2012

Port knocking is a technique by which only a single packet or special sequence will permit the firewall to open a port on a machine where all ports are blocked by default. It is a passive authorization technique which offers firewall-level authentication to ensure authorized access to potentially vulnerable network services. In this paper, we present performance evaluation and analytical comparison of three widely used port knocking (PK) algorithms, Aldaba, FWKNOP and SIG-2. Comparative analysis is based upon ten selected parameters; Platforms (Supported OS), Implementation (PK, SPA or both), Protocols (UDP, TCP, ICMP), Out of Order packet delivery, NAT (Network Address Translation), Encryption Algorithms, Root privileges (For installation and operation), Weak Passwords, Replay Attacks and IPv6 compatibility. Based upon these parameters, relative performance score has been given to each algorithm. Finally, we deduce that FWKNOP due to compatibility with windows client is the most efficient among chosen PK implementations.
DSDV, DYMO, OLSR: Link Duration and Path Stability
Venue: arXiv cs.NI 2012
Year: 2012

In this paper, we evaluate and compare the impact of link duration and path stability of routing protocols; Destination Sequence Distance vector (DSDV), Dynamic MANET On- Demand (DYMO) and Optimized Link State Routing (OLSR) at different number of connections and node density. In order to improve the efficiency of selected protocols; we enhance DYMO and OLSR. Simulation and comparison of both default and enhanced routing protocols is carried out under the performance parameters; Packet Delivery Ratio (PDR), Average End-to End Delay (AE2ED) and Normalized Routing Overhead (NRO). From the results, we observe that DYMO performs better than DSDV, MOD-OLSR and OLSR in terms of PDR, AE2ED, link duration and path stability at the cost of high value of NRO.
Seamless Infrastructure independent Multi Homed NEMO Handoff Using Effective and Timely IEEE 802.21 MIH triggers
Venue: arXiv cs.NI 2012
Year: 2012

Handoff performance of NEMO BS protocol with existent improvement proposals is still not sufficient for real time and QoS-sensitive applications and further optimizations are needed. When dealing with single homed NEMO, handoff latency and packet loss become irreducible all optimizations included, so that it is impossible to meet requirements of the above applications. Then, How to combine the different Fast handoff approaches remains an open research issue and needs more investigation. In this paper, we propose a new Infrastructure independent handoff approach combining multihoming and intelligent Make-Before-Break Handoff. Based on required Handoff time estimation, L2 and L3 handoffs are initiated using effective and timely MIH triggers, reducing so the anticipation time and increasing the probability of prediction. We extend MIH services to provide tunnel establishment and switching before link break. Thus, the handoff is performed in background with no latency and no packet loss while pingpong scenario is almost avoided. In addition, our proposal saves cost and power consumption by optimizing the time of simultaneous use of multiple interfaces. We provide also NS2 simulation experiments identifying suitable parameter values used for estimation and validating the proposed model
Precoding Methods for MISO Broadcast Channel with Delayed CSIT
Venue: arXiv cs.IT 2012
Year: 2012

Recent information theoretic results suggest that precoding on the multi-user downlink MIMO channel with delayed channel state information at the transmitter (CSIT) could lead to data rates much beyond the ones obtained without any CSIT, even in extreme situations when the delayed channel feedback is made totally obsolete by a feedback delay exceeding the channel coherence time. This surprising result is based on the ideas of interference repetition and alignment which allow the receivers to reconstruct information symbols which canceling out the interference completely, making it an optimal scheme in the infinite SNR regime. In this paper, we formulate a similar problem, yet at finite SNR. We propose a first construction for the precoder which matches the previous results at infinite SNR yet reaches a useful trade-off between interference alignment and signal enhancement at finite SNR, allowing for significant performance improvements in practical settings. We present two general precoding methods with arbitrary number of users by means of virtual MMSE and mutual information optimization, achieving good compromise between signal enhancement and interference alignment. Simulation results show substantial improvement due to the compromise between those two aspects.
Can One Achieve Multiuser Diversity in Uplink Multi-Cell Networks?
Venue: arXiv cs.IT 2012
Year: 2012

We introduce a distributed opportunistic scheduling (DOS) strategy, based on two pre-determined thresholds, for uplink $K$-cell networks with time-invariant channel coefficients. Each base station (BS) opportunistically selects a mobile station (MS) who has a large signal strength of the desired channel link among a set of MSs generating a sufficiently small interference to other BSs. Then, performance on the achievable throughput scaling law is analyzed. As our main result, it is shown that the achievable sum-rate scales as $K\log(\text{SNR}\log N)$ in a high signal-to-noise ratio (SNR) regime, if the total number of users in a cell, $N$, scales faster than $\text{SNR}^{\frac{K-1}{1-ε}}$ for a constant $ε\in(0,1)$. This result indicates that the proposed scheme achieves the multiuser diversity gain as well as the degrees-of-freedom gain even under multi-cell environments. Simulation results show that the DOS provides a better sum-rate throughput over conventional schemes.
Predictive Software Measures based on Z Specifications - A Case Study
Venue: arXiv cs.SE 2012
Year: 2012

Estimating the effort and quality of a system is a critical step at the beginning of every software project. It is necessary to have reliable ways of calculating these measures, and, it is even better when the calculation can be done as early as possible in the development life-cycle. Having this in mind, metrics for formal specifications are examined with a view to correlations to complexity and quality-based code measures. A case study, based on a Z specification and its implementation in ADA, analyzes the practicability of these metrics as predictors.
Metric Problems for Quadrics in Multidimensional Space
Venue: arXiv cs.SC 2012
Year: 2012

Given the equations of the first and the second order surfaces in multidimensional space, our goal is to construct a univariate polynomial one of the zeros of which coincides with the square of the distance between these surfaces. To achieve this goal we employ Elimination Theory methods. The proposed approach is also extended for the case of parameter dependent surfaces.
Stackelberg Shortest Path Tree Game, Revisited
Venue: arXiv cs.DS 2012
Year: 2012

Let $G(V,E)$ be a directed graph with $n$ vertices and $m$ edges. The edges $E$ of $G$ are divided into two types: $E_F$ and $E_P$. Each edge of $E_F$ has a fixed price. The edges of $E_P$ are the priceable edges and their price is not fixed a priori. Let $r$ be a vertex of $G$. For an assignment of prices to the edges of $E_P$, the revenue is given by the following procedure: select a shortest path tree $T$ from $r$ with respect to the prices (a tree of cheapest paths); the revenue is the sum, over all priceable edges $e$, of the product of the price of $e$ and the number of vertices below $e$ in $T$. Assuming that $k=|E_P|\ge 2$ is a constant, we provide a data structure whose construction takes $O(m+n\log^{k-1} n)$ time and with the property that, when we assign prices to the edges of $E_P$, the revenue can be computed in $(\log^{k-1} n)$. Using our data structure, we save almost a linear factor when computing the optimal strategy in the Stackelberg shortest paths tree game of [D. Bil{ò} and L. Gual{à} and G. Proietti and P. Widmayer. Computational aspects of a 2-Player Stackelberg shortest paths tree game. Proc. WINE 2008].