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.     

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.     

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.     

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.     

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.     

The Mizar Mathematical Library in OMDoc: Translation and Applications

The Mizar Mathematical Library is one of the largest libraries of formalized and mechanically verified mathematics. Its language is highly optimized for authoring by humans. As in natural languages, the meaning of an expression is influenced by its (mathematical) context in a way that is natural to humans, but harder to specify for machine manipulation. Thus its custom file format can make the access to the library difficult. Indeed, the Mizar system itself is currently the only system that can fully operate on the Mizar library. This paper presents a translation of the Mizar library into the OMDoc format (Open Mathematical Documents), an XML-based representation format for mathematical knowledge. OMDoc is geared towards machine support and interoperability by making formula structure and context dependencies explicit. Thus, the Mizar library becomes accessible for a wide range of OMDoc-based tools for formal mathematics and knowledge management. We exemplify interoperability by indexing the translated library in the MathWebSearch engine, which provides an “applicable theorem search” service (almost) out of the box.     

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.     

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.     

Smart places: Multi-agent based smart mobile virtual community management system

Now-a-days advances in mobile device technology aim to build complex computational systems providing a maximum level of flexibility, decentralization, simplest form of interactivity, and ease of use. Recently, the launch of the agent-oriented platform JaCaMo and its Android client based platform JaCa-Android have provided an appropriate level of abstraction to build smart mobile client server systems providing these attributes. By using these platforms, we have developed a multi-agent based Smart Mobile Virtual Community Management System (SMVCMS) that makes it possible to provide a decentralized and open management of virtual communities. This paper addresses the design and architecture of our multi-agent server and client application. It elaborates different features of our system; such as how a participant in virtual communities is supported by a Jason agent that encapsulates the logic and the control of the participation in a virtual community (such as publishing posts, notifying members, making recommendations for the user, etc.). It also discusses how the set of CArtAgOartifacts provides the basic functionalities and operations giving access to the functionalities for knowledge exchange in virtual communities, and personal agents onAndroid exploit these artifacts to execute their tasks while achieving their individual and collective goals. We have employed SMVCMS in the context of Smart Cities and found that the system fulfills the desired goals, such as decentralization of community management, personalized automatic management and discovery of communities, autonomy of agents and flexibility so that any agent can create its own community with the maximum level of ease.     

MobiCloUP!: a PaaS for cloud services-based mobile applications

The integration of cloud computing and mobile computing has recently resulted in the Mobile Cloud Computing (MCC) paradigm which is defined as the availability of \(c\) loud services over a mobile ecosystem. Platform as a Service (PaaS) is a model of cloud computing that refers to high-level software systems delivered over Internet. This model typically enables developers to deliver Web applications as Software as a Service. With the aim of providing support to the MCC, in this work a PaaS called MobiCloUP! is proposed for mobile Web and native applications based on third-party cloud services such as Netflix, Instagram and Pinterest, to mention but a few. Unlike other commercial solutions such as force.com, Google \(^{\mathrm{TM}}\) App Engine and other academic proposals like MOSAIC, MobiCloUP! implements an automatic code generation programming model targeting rich mobile applications based on both Web standards such as HTML5, CSS3 and AJAX and Rich Internet Application frameworks like Adobe \(^{\textregistered }\) Flex. The MobiCloUP! core is a wizard tool that covers design, publish/deployment, development and maintenance phases for mobile development life-cycle. In order to validate our proposal, Web 2.0 services-based Web and native mobile applications were developed and deployed to the Cloud using MobiCloUP!. Finally, a qualitative-comparative evaluation was performed in order to validate the legitimacy of our proposal against other similar commercial proposals.     

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.     

A blind digital audio watermarking scheme based on EMD and UISA techniques

In this paper, a new perceptual spread spectrum audio watermarking scheme is discussed. The watermark embedding process is performed in the Empirical Mode Decomposition (EMD) domain, and the hybrid watermark extraction process is based on the combination of EMD and ISA (Independent Subspace Analysis) techniques, followed by the generic detection system, i.e. inverse perceptual filter, predictor filter and correlation based detector. Since the EMD decomposes the audio signal into several oscillating components–the intrinsic mode functions (IMF)–the watermark information can be inserted in more than one IMF, using spread spectrum modulation, allowing hence the increase of the insertion capacity. The imperceptibility of the inserted data is ensured by the use of a psychoacoustical model. The blind extraction of the watermark signal, from the received watermarked audio, consists in the separation of the watermark from the IMFs of the received audio signal. The separation is achieved by a new proposed under-determined ISA method, here referred to as UISA. The proposed hybrid watermarking system was applied to the SQAM (Sound Quality Assessment Material) audio database (Available at http://sound.media.mit.edu/mpeg4/audio/sqam/) and proved to have efficient detection performances in terms of Bit Error Rate (BER) compared to a generic perceptual spread spectrum watermarking system. The perceptual quality of the watermarked audio was objectively assessed using the PEMO-Q (Tool for objective perceptual assessment of audio quality) algorithm. Also, using our technique, we can extract the different watermarks without using any information of original signal or the inserted watermark. Experimental results exhibit that the transparency and high robustness of the watermarked audio can be achieved simultaneously with a substantial increase of the amount of information transmitted. A reliability of 1.8 10^???4 (against 1.5 10^???2 for the generic system), for a bit rate of 400 bits/s, can be achieved when the channel is not disturbed.     

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.     

Improving Head Movement Tolerance of Cross-Ratio Based Eye Trackers

When first introduced, the cross-ratio (CR) based remote eye tracking method offered many attractive features for natural human gaze-based interaction, such as simple camera setup, no user calibration, and invariance to head motion. However, due to many simplification assumptions, current CR-based methods are still sensitive to head movements. In this paper, we revisit the CR-based method and introduce two new extensions to improve the robustness of the method to head motion. The first method dynamically compensates for scale changes in the corneal reflection pattern, and the second method estimates true coplanar eye features so that the cross-ratio can be applied. We present real-time implementations of both systems, and compare the performance of these new methods using simulations and user experiments. Our results show a significant improvement in robustness to head motion and, for the user experiments in particular, an average reduction of up to 40 % in gaze estimation error was observed.     

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.     

FINE: A Fully Informed aNd Efficient communication-induced checkpointing protocol for distributed systems

Communication-Induced Checkpointing (CIC) protocols are classified into two categories in the literature: Index-based and Model-based. In this paper, we discuss two data structures being used in these two kinds of CIC protocols, and their different roles in helping the checkpointing algorithms to enforce Z-cycle Free (ZCF) property. Then, we present our Fully Informed aNd Efficient (FINE) communication-induced checkpointing algorithm, which not only has less checkpointing overhead than the well-known Fully Informed (FI) CIC protocol proposed by Helary et al. but also has less message overhead. Performance evaluation indicates that our protocol performs better than many of the other existing CIC protocols.