Local noncuppability in R/M

Given any [c], [a], [d] xxxxxxxxR/M such that [d] ≤ [a] ≤ [c], [a] is locally noncuppable between [c] and [d] if [d] < [a] ≤ [c] and [a] ∨ [b] < [c] for any [b] xxxxxxxxR/M such that [d] ≤ [b] < [c]. It will be shown that given any nonzero [c] xxxxxxxxR/M, there are [a], [d] xxxxxxxxR/M such that [d] < [a] ≤ [c] and [a] is locally noncuppable between [c] and [d].     

PP-Lowness and a Simple Definition of AWPP

Abstract. We show that the counting classes AWPP and APP [FFKL], [L] are more robust than previously thought. Our results identify a sufficient condition for a language to be low for PP, and we show that this condition is at least as weak as other previously studied criteria. We extend a result of Köbler et al. by proving that all sparse co-C ₌ P languages are in APP, and are thus PP-low. Our results also imply that AWPP ?eq APP, and thus APP contains many other established subclasses of PP-low, thereby reducing several different lowness results to membership in APP. We also show that AWPP and APP are Σ ⁰ ₂ -definable classes. Some of our results are reminiscent of amplifying certainty in probabilistic computation.     

Bisection forAx=λBx with matrices of variable band width

Some extensions of the bisection method and of the inverse vector iteration for the general eigenvalue problemAx=λBx with symmetric matrices are given. A version with restricted pivoting is applied to sparse matricesA andB in which case the decomposition ofA-μB can be performed within an extended envelope with respect to the envelopeA andB. The effect of these refinements is illustrated by an example.     

Contraction-Free Linear Depth Sequent Calculi for Intuitionistic Propositional Logic with the Subformula Property and Minimal Depth Counter-Models

In this paper we present LSJ, a contraction-free sequent calculus for Intuitionistic propositional logic whose proofs are linearly bounded in the length of the formula to be proved and satisfy the subformula property. We also introduce a sequent calculus RJ for intuitionistic unprovability with the same properties of LSJ. We show that from a refutation of RJ of a sequent σ we can extract a Kripke counter-model for σ. Finally, we provide a procedure that given a sequent σ returns either a proof of σ in LSJ or a refutation in RJ such that the extracted counter-model is of minimal depth.     

MPaaS: Mobility prediction as a service in telecom cloud

Mobile applications and services relying on mobility prediction have recently spurred lots of interest. In this paper, we propose mobility prediction based on cellular traces as an infrastructural level service of telecom cloud. Mobility Prediction as a Service (MPaaS) embeds mobility mining and forecasting algorithms into a cloud-based user location tracking framework. By empowering MPaaS, the hosted 3rd-party and value-added services can benefit from online mobility prediction. Particularly we took Mobility-aware Personalization and Predictive Resource Allocation as key features to elaborate how MPaaS drives new fashion of mobile cloud applications. Due to the randomness of human mobility patterns, mobility predicting remains a very challenging task in MPaaS research. Our preliminary study observed collective behavioral patterns (CBP) in mobility of crowds, and proposed a CBP-based mobility predictor. MPaaS system equips a hybrid predictor fusing both CBP-based scheme and Markov-based predictor to provide telecom cloud with large-scale mobility prediction capacity.     

Minimum Manhattan Network Problem in Normed Planes with Polygonal Balls: A Factor 2.5 Approximation Algorithm

Let ${\mathcal{B}}$ be a centrally symmetric convex polygon of ?² and ‖p?q‖ be the distance between two points p,q∈?² in the normed plane whose unit ball is ${\mathcal{B}}$ . For a set T of n points (terminals) in ?², a ${\mathcal{B}}$ -network on T is a network N(T)=(V,E) with the property that its edges are parallel to the directions of ${\mathcal{B}}$ and for every pair of terminals t _i and t _j , the network N(T) contains a shortest ${\mathcal{B}}$ -path between them, i.e., a path of length ‖t _i ?t _j ‖. A minimum ${\mathcal{B}}$ -network on T is a ${\mathcal{B}}$ -network of minimum possible length. The problem of finding minimum ${\mathcal{B}}$ -networks has been introduced by Gudmundsson, Levcopoulos, and Narasimhan (APPROX’99) in the case when the unit ball ${\mathcal{B}}$ is a square (and hence the distance ‖p?q‖ is the l ₁ or the l _∞-distance between p and q) and it has been shown recently by Chin, Guo, and Sun (Symposium on Computational Geometry, pp. 393–402, 2009) to be strongly NP-complete. Several approximation algorithms (with factors 8, 4, 3, and 2) for the minimum Manhattan problem are known. In this paper, we propose a factor 2.5 approximation algorithm for the minimum ${\mathcal{B}}$ -network problem. The algorithm employs a simplified version of the strip-staircase decomposition proposed in our paper (Chepoi et al. in Theor. Comput. Sci. 390:56–69, 2008, and APPROX-RANDOM, pp. 40–51, 2005) and subsequently used in other factor 2 approximation algorithms for the minimum Manhattan problem.     

Effective condition number and its applications

Consider the over-determined system Fx = b where ${{\bf F}\in\mathcal{R}^{m \times n}, m \geq n}$ and rank (F) = r ≤ n, the effective condition number is defined by ${{\rm Cond_{-}eff }= \frac {\|{\bf b}\|}{\sigma_r\|{\bf x}\|}}$ , where the singular values of F are given as σ _max = σ ₁ ≥ σ ₂ ≥ . . . ≥ σ _r > 0 and σ _r+1 = . . . = σ _n = 0. For the general perturbed system (A+ΔA)(x+Δx) = b+Δb involving both ΔA and Δb, the new error bounds pertinent to Cond_eff are derived. Next, we apply the effective condition number to the solutions of Motz’s problem by the collocation Trefftz methods (CTM). Motz’s problem is the benchmark of singularity problems. We choose the general particular solutions ${v_L = \sum\nolimits_{k=0}^L d_k (\frac {r}{R_p})^{k+\frac 12}}$ ${{\rm cos}(k +\frac 12)\theta}$ with a radius parameter R _p . The CTM is used to seek the coefficients d _i by satisfying the boundary conditions only. Based on the new effective condition number, the optimal parameter R _p = 1 is found. which is completely in accordance with the numerical results. However, if based on the traditional condition number Cond, the optimal choice of R _p is misleading. Under the optimal choice R _p = 1, the Cond grows exponentially as L increases, but Cond_eff is only linear. The smaller effective condition number explains well the very accurate solutions obtained. The error analysis in [14,15] and the stability analysis in this paper grant the CTM to become the most efficient and competent boundary method.     

Query reverse engineering

In this paper, we introduce a new problem termed query reverse engineering (QRE). Given a database \(D\) and a result table \(T\) —the output of some known or unknown query \(Q\) on \(D\) —the goal of QRE is to reverse-engineer a query \(Q'\) such that the output of query \(Q'\) on database \(D\) (denoted by \(Q'(D)\) ) is equal to \(T\) (i.e., \(Q(D)\) ). The QRE problem has useful applications in database usability, data analysis, and data security. In this work, we propose a data-driven approach, TALOS for Tree-based classifier with At Least One Semantics, that is based on a novel dynamic data classification formulation and extend the approach to efficiently support the three key dimensions of the QRE problem: whether the input query is known/unknown, supporting different query fragments, and supporting multiple database versions.     

Reasoning about temporal properties of rational play

This article is about defining a suitable logic for expressing classical game theoretical notions. We define an extension of alternating-time temporal logic (ATL) that enables us to express various rationality assumptions of intelligent agents. Our proposal, the logic ATLP (ATL with plausibility) allows us to specify sets of rational strategy profiles in the object language, and reason about agents’ play if only these strategy profiles were allowed. For example, we may assume the agents to play only Nash equilibria, Pareto-optimal profiles or undominated strategies, and ask about the resulting behaviour (and outcomes) under such an assumption. The logic also gives rise to generalized versions of classical solution concepts through characterizing patterns of payoffs by suitably parameterized formulae of ATLP. We investigate the complexity of model checking ATLP for several classes of formulae: It ranges from $\Delta_{\mathbf{3}}^{\mathbf{P}}$ to PSPACE in the general case and from $\Delta_{\mathbf{3}}^{\mathbf{P}}$ to $\Delta_{\mathbf{4}}^{\mathbf{P}}$ for the most interesting subclasses, and roughly corresponds to solving extensive games with imperfect information.     

On Succinct Greedy Drawings of Plane Triangulations and 3-Connected Plane Graphs

Geometric routing by using virtual locations is an elegant way for solving network routing problems. In its simplest form, greedy routing, a message is simply forwarded to a neighbor that is closer to the destination. It has been an open conjecture whether every 3-connected plane graph has a greedy drawing in the Euclidean plane R ² (by Papadimitriou and Ratajczak in Theor. Comp. Sci. 344(1):3–14, 2005). Leighton and Moitra (Discrete Comput. Geom. 44(3):686–705, 2010) recently settled this conjecture positively. One main drawback of this approach is that the coordinates of the virtual locations require Ω(nlogn) bits to represent (the same space usage as traditional routing table approaches). This makes greedy routing infeasible in applications. In this paper, we show that the classical Schnyder drawing in R ² of plane triangulations is greedy with respect to a simple natural metric function H(u,v) over R ² that is equivalent to Euclidean metric D _E (u,v) (in the sense that $D_{E}(u,v) \leq H(u,v) \leq2\sqrt{2}D_{E}(u,v)$ ). The drawing uses two integer coordinates between 0 and 2n?5, which can be represented by logn bits. We also show that the classical Schnyder drawing in R ² of 3-connected plane graphs is weakly greedy with respect to the same metric function H(?,?). The drawing uses two integer coordinates between 0 and f (where f is the number of internal faces of G).     

ANDES: efficient evaluation of NOT-twig queries in relational databases

Despite a large body of work on XPath query processing in relational environment, systematic study of queries containing not-predicates have received little attention in the literature. Particularly, several xml supports of industrial-strength commercial rdbms fail to efficiently evaluate such queries. In this paper, we present an efficient and novel strategy to evaluate not -twig queries in a tree-unaware relational environment. not -twig queries are XPath queries with ancestor–descendant and parent–child axis and contain one or more not-predicates. We propose a novel Dewey-based encoding scheme called Andes (ANcestor Dewey-based Encoding Scheme), which enables us to efficiently filter out elements satisfying a not-predicate by comparing their ancestor group identifiers. In this approach, a set of elements under the same common ancestor at a specific level in the xml tree is assigned same ancestor group identifier. Based on this scheme, we propose a novel sql translation algorithm for not-twig query evaluation. Experiments carried out confirm that our proposed approach built on top of an off-the-shelf commercial rdbms significantly outperforms state-of-the-art relational and native approaches. We also explore the query plans selected by a commercial relational optimizer to evaluate our translated queries in different input cardinality. Such exploration further validates the performance benefits of Andes.     

Iterations for solving linear variational inequalities on domains with nonlinear boundaries

This paper deals with numerical methods for solving linear variational inequalities on an arbitrary closed convex subsetC of ? ⁿ . Although there were numerous iterations studied for the caseC=? ₊ ⁿ , few were proposed for the case whenC is a closed convex subset. The essential difficulty in this case is the nonlinearities ofC's boundaries. In this paper iteration processes are designed for solving linear variational inequalities on an arbitrary closed convex subsetC. In our algorithms the computation of a linear variational inequality is decomposed into a sequence of problems of projecting a vector to the closed convex subsetC, which are computable as long as the equations describing the boundaries are given. In particular, using our iterations one can easily compute a solution whenC is one of the common closed convex subsets such as cube, ball, ellipsoid, etc. The non-accurate iteration, the estimate of the solutions on unbounded domains and the theory of approximating the boundaries are also established. Moreover, a necessary and sufficient condition is given for a vector to be an approximate solution. Finally, some numerical examples are presented, which show that the designed algorithms are effective and efficient. The exposition of this paper is self-contained.     

HumanTop: a multi-object tracking tabletop

In this paper, a computer vision based interactive multi-touch tabletop system called HumanTop is introduced. HumanTop implements a stereo camera vision subsystem which allows not only an accurate fingertip tracking algorithm but also a precise touch-over-the-working surface detection method. Based on a pair of visible spectra cameras, a novel synchronization circuit makes the camera caption and the image projection independent from each other, providing the minimum basis for the development of computer vision analysis based on visible spectrum cameras without any interference coming from the projector. The assembly of both cameras and the synchronization circuit is not only capable of performing an ad-hoc version of a depth camera, but it also introduces the recognition and tracking of textured planar objects, even when contents are projected over them. On the other hand HumanTop supports the tracking of sheets of paper and ID-code markers. This set of features makes the HumanTop a comprehensive, intuitive and versatile augmented tabletop that provides multitouch interaction with projective augmented reality on any flat surface. As an example to exploit all the capabilities of HumanTop, an educational application has been developed using an augmented book as a launcher to different didactic contents. A pilot study in which 28 fifth graders participated is presented. Results about efficiency, usability/satisfaction and motivation are provided. These results suggest that HumanTop is an interesting platform for the development of educational contents.     

Sustainable virtual communities: suggestions from the colonial model

While virtual community research has contributed to the understanding of the virtual community sustainability, a need for a systematic model exists. In this paper, we propose a model of sustainable virtual communities based on the sustainability properties of animal colonies in nature. The premise of our model is that if we manage to replicate the sustainability properties of colonial systems in virtual communities, they can become longer lasting. We also present the results of an exploratory case study. The study shows that colonial properties form a construct that predicts member perceptions of their community being sustainable. While our primary objective is the conceptual introduction of the colonial principles of sustainability, the case study provides some early indications that these principles may help design systems that can bind virtual communities more permanently.

Crystal: Integrating Structured Queries into a Tactic Language

We present the language CRStL (Control Rule Strategy Language, pronounce “crystal”) to formulate mathematical reasoning techniques as proof strategies in the context of the proof assistant Ωmega. The language is arranged in two levels, a query language to access mathematical knowledge maintained in development graphs, and a strategy language to annotate the results of these queries with further control information. The two-leveled structure of the language allows the specification of proof techniques in a declarative way. We present the syntax and semantics of CRStL and illustrate its use by examples.     

A Quantum Characterization Of NP

In this article, we introduce a new complexity class called PQMA _log(2). Informally, this is the class of languages for which membership has a logarithmic-size quantum proof with perfect completeness and soundness, which is polynomially close to 1 in a context where the verifier is provided a proof with two unentangled parts. We then show that PQMA _log(2) =? NP. For this to be possible, it is important, when defining the class, not to give too much power to the verifier. This result, when compared to the fact that QMA _log =? BQP, gives us new insight into the power of quantum information and the impact of entanglement.     

The Alexander Method — A technique for the processing of recursive axioms in deductive databases

We propose a technique for handling recursive axioms in deductive databases. More precisely, we solve the following problem: Given a relational query including virtual relations defined from axioms (Horn clauses, with variables in the conclusion predefined in the hypotheses), which can be recursive, how to translate this query into arelational program, i. e. a set of relational operations concerning only real relations (not virtual). Our solution has the following properties:

? the program to evaluate the query always terminates,

? the relational program is produced by a pure compilation of a source query and of the axioms, and is independent of the data values (there is no run-time),

? the relational operations are optimized: theyfocus towards the computation of the query, without needless computations.

As far as we know, the Alexander Method is the first solution exhibiting all these properties. This work is partly funded by Esprit Project 112 (KIMS).     

Complexity and Approximability of the Cover Polynomial

The cover polynomial and its geometric version introduced by Chung & Graham and D??Antona & Munarini, respectively, are two-variate graph polynomials for directed graphs. They count the (weighted) number of ways to cover a graph with disjoint directed cycles and paths, can be thought of as interpolations between determinant and permanent, and are proposed as directed analogues of the Tutte polynomial. Jaeger, Vertigan, and Welsh showed that the Tutte polynomial is #P-hard to evaluate at all but a few special points and curves. It turns out that the same holds for the cover polynomials: We prove that, in almost the whole plane, the problem of evaluating the cover polynomial and its geometric version is #P-hard under polynomial time Turing reductions, while only three points in the cover polynomial and two points in the geometric cover polynomial are easy. We also study the complexity of approximately evaluating the geometric cover polynomial. Under the reasonable complexity assumptions RP ?? NP and RFP ?? #P, we give a succinct characterization of a large class of points at which approximating the geometric cover polynomial within any polynomial factor is not possible.