Hard constraint satisfaction problems have hard gaps at location 1

An instance of the maximum constraint satisfaction problem (Max CSP) is a finite collection of constraints on a set of variables, and the goal is to assign values to the variables that maximises the number of satisfied constraints. Max CSP captures many well-known problems (such as Maxk-SAT and Max Cut) and is consequently NP-hard. Thus, it is natural to study how restrictions on the allowed constraint types (or constraint language) affect the complexity and approximability of Max CSP. The PCP theorem is equivalent to the existence of a constraint language for which Max CSP has a hard gap at location 1; i.e. it is NP-hard to distinguish between satisfiable instances and instances where at most some constant fraction of the constraints are satisfiable. All constraint languages, for which the CSP problem (i.e., the problem of deciding whether all constraints can be satisfied) is currently known to be NP-hard, have a certain algebraic property. We prove that any constraint language with this algebraic property makes Max CSP have a hard gap at location 1 which, in particular, implies that such problems cannot have a PTAS unless P=NP. We then apply this result to Max CSP restricted to a single constraint type; this class of problems contains, for instance, Max Cut and Max DiCut. Assuming P≠NP, we show that such problems do not admit PTAS except in some trivial cases. Our results hold even if the number of occurrences of each variable is bounded by a constant. Finally, we give some applications of our results.     

Quantum Error Correction of Time-correlated Errors

The complexity of the error correction circuitry forces us to design quantum error correction codes capable of correcting a single error per error correction cycle. Yet, time-correlated error are common for physical implementations of quantum systems; an error corrected during the previous cycle may reoccur later due to physical processes specific for each physical implementation of the qubits. In this paper, we study quantum error correction for a restricted class of time-correlated errors in a spin-boson model. The algorithm we propose allows the correction of two errors per error correction cycle, provided that one of them is time-correlated. The algorithm can be applied to any stabilizer code when the two logical qubits and are entangled states of 2 ⁿ basis states in .      

Adaptation of an automotive dialogue system to users’ expertise and evaluation of the system

Spoken dialogue systems (SDSs) can be used to operate devices, e.g. in the automotive environment. People using these systems usually have different levels of experience. However, most systems do not take this into account. In this paper, we present a method to build a dialogue system in an automotive environment that automatically adapts to the user’s experience with the system. We implemented the adaptation in a prototype and carried out exhaustive tests. Our usability tests show that adaptation increases both user performance and user satisfaction. We describe the tests that were performed, and the methods used to assess the test results. One of these methods is a modification of PARADISE, a framework for evaluating the performance of SDSs [Walker MA, Litman DJ, Kamm CA, Abella A (Comput Speech Lang 12(3):317–347, 1998)]. We discuss its drawbacks for the evaluation of SDSs like ours, the modifications we have carried out, and the test results.

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.     

Interactive transmission processing for large images in a resource-constraint mobile wireless network

In the state-of-the-art methods for (large) image transmission, no user interaction behaviors (e.g., user tapping) can be actively involved to affect the transmission performance (e.g., higher image transmission efficiency with relatively poor image quality). So, to effectively and efficiently reduce the large image transmission costs in resource-constraint mobile wireless networks (MWN), we design a content-based and bandwidth-aware Interactive large Image Transmission method in MWN, called the I it. To the best of our knowledge, this is the first study on the interactive image transmission. The whole transmission processing of the I it works as follows: before transmission, a preprocessing step computes the optimal and initial image block (IB) replicas based on the image content and the current network bandwidth at the sender node. During transmission, in case of unsatisfied transmission efficiency, the user’s anxiety to preview the image can be implicitly indicated by the frequency of tapping the screen. In response, the transmission resolutions of the candidate IB replicas can be dynamically adjusted based on the user anxiety degree (UAD). Finally, the candidate IB replicas are transmitted with different priorities to the receiver for reconstruction and display. The experimental results show that the performance of our approach is both efficient and effective, minimizing the response time by decreasing the network transmission cost while improving user experiences.     

Parallel algorithms for some functions of two convex polygons

Let P andQ be two convex,n-vertex polygons. We consider the problem of computing, in parallel, some functions ofP andQ whenP andQ are disjoint. The model of parallel computation we consider is the CREW-PRAM, i.e., it is the synchronous shared-memory model where concurrent reads are allowed but no two processors can simultaneously attempt to write in the same memory location (even if they are trying to write the same thing). We show that a CREW-PRAM havingn ^1/k processors can compute the following functions in O(k¹⁺) time: (i) the common tangents betweenP andQ, and (ii) the distance betweenP andQ (and hence a straight line separating them). The positive constant can be made arbitrarily close to zero. Even with a linear number of processors, it was not previously known how to achieve constant time performance for computing these functions. The algorithm for problem (ii) is easily modified to detect the case of zero distance as well.This research was supported by the Office of Naval Research under Grants N00014-84-K-0502 and N00014-86-K-0689, and the National Science Foundation under Grant DCR-8451393, with matching funds from AT&T.     

Smooth Gaze: a framework for recovering tasks across devices using eye tracking

A user task is often distributed across devices, e.g., a student listening to a lecture in a classroom while watching slides on a projected screen and making notes on her laptop, and sometimes checking Twitter for comments on her smartphone. In scenarios like this, users move between heterogeneous devices and have to deal with task resumption overhead from both physical and mental perspectives. To address this problem, we created Smooth Gaze, a framework for recording the user’s work state and resuming it seamlessly across devices by leveraging implicit gaze input. In particular, we propose two novel and intuitive techniques, smart watching and smart posting, for detecting which display and target region the user is looking at, and transferring and integrating content across devices respectively. In addition, we designed and implemented a cross-device reading system SmoothReading that captures content from secondary devices and generates annotations based on eye tracking, to be displayed on the primary device. We conducted a study that showed that the system supported information seeking and task resumption, and improved users’ overall reading experience.     

Complete sets and closeness to complexity classes

We consider two setsA andB to be close to each other if the census of their symmetric difference,A B, is a slowly increasing function (e.g. a polynomial.) The classes of sets which are polynomially close to some set in a complexity classC (likeP) are studied and characterized. We investigate the question whether complete sets forNP or EXPTIME can be polynomially close to a set inP. Some of the obtained results strengthen or generalize results by Yesha [24], e.g. it is shown that no EXPTIME-hard set can be polynomially close to any set inP.     

Preface: Volume 68, Issue 5

A large class of systems can be specified and verified by abstracting away from the temporal aspects. In time-critical systems, instead, time issues become essential. Their correctness depends not only on which actions a system can perform but also on their execution time. Due to their importance, time-critical systems have attracted the attention of a considerable number of computer scientists from various research areas.This volume contains the Proceedings of the 3rd International Workshop on Models for Time-Critical Systems (MTCS 2002); MTCS 2002 was held on August 24, 2002 as one of seven satellite workshops co-located with the 13th International Conference on Concurrency Theory (CONCUR 2002), held in Brno (Czech Republic) August 20-23, 2002.The first workshop, MTCS 2000, was held in State College (Pennsylvania, USA) on August 26 2000, co-chaired by Flavio Corradini and Paola Inverardi. while the second workshop, MTCS 2001, was held in Aalborg (Denmark) on August 25, 2001, co-chaired by Flavio Corradini and Walter Vogler. As for the first two workshops, the objectives of MTCS 2002 were (i) to present and discuss promising new proposals on models for time-critical systems, ranging from theory to practice and (ii) to promote interaction between different research areas in the field of time-critical systems. Despite its focus on time-critical systems, MTCS 2002 was also open for time-related issues in general, e.g. performance in systems where time is not critical for the functional behaviour.The papers in this volume were selected for presentation by the Program Committee from submissions received in response to a Call for Papers. Many thanks are due to the members of the Program Committee as well as their sub-referees for their accurate work, and also to the invited speakers P. S. Thiagarajan (Chennai Mathematical Institute) and Walter Vogler (University of Augsburg). We would also like to thank Michael Mislove for his help during the proceedings editorial process and BRICS for the publication of the preliminary proceedings. Finally, our thanks go to Petr Jancar and Mojmir Kretinsky (CONCUR 2002 Conference Chairs) and Antonin Kucera (Workshops Coordinator) for the opportunity they gave us to organize MTCS 2002 and for their support.The papers in this volume were reviewed by the program committee consisting of

Rajeev Alur	(USA)
Jos Baeten	(Netherlands)
Frank de Boer	(Netherlands)
Flavio Corradini	(Italy)
Kim Larsen	(Denmark)
Gerald Lüttgen	(United Kingdom)
Jeff Magee	(United Kingdom)
Andrea Maggiolo-Schettini	(Italy)
Paul Pettersson	(Sweden)
Steve Schneider	(United Kingdom)
Bran Selic	(USA)
Joseph Sifakis	(France)
P. S. Thiagarajan	(India)
Walter Vogler	(Germany)

Full-size table

A printed version of the current volume was distributed to the participants at the workshop in Brno.April 24, 2003 Walter Vogler, Kim Larsen     

Optimizing top-<Emphasis Type="Italic">k</Emphasis> retrieval: submodularity analysis and search strategies

The key issue in top-k retrieval, finding a set of k documents (from a large document collection) that can best answer a user’s query, is to strike the optimal balance between relevance and diversity. In this paper, we study the top-k retrieval problem in the framework of facility location analysis and prove the submodularity of that objective function which provides a theoretical approximation guarantee of factor 1?\(\frac{1}{e}\) for the (best-first) greedy search algorithm. Furthermore, we propose a two-stage hybrid search strategy which first obtains a high-quality initial set of top-k documents via greedy search, and then refines that result set iteratively via local search. Experiments on two large TREC benchmark datasets show that our two-stage hybrid search strategy approach can supersede the existing ones effectively and efficiently.     

OnP-subset structures

Given a setA, we investigate the lattice structure formed by those of its subsets that belong to the complexity classP, taken modulo finite variations and ordered by inclusion. We show that up to isomorphism, only three structures are possible for this lattice. IfA isP-immune, itsP-subset structure degenerates to the trivial one-element lattice. IfA is almostP-immune but notP-immune (for instance, ifA is inP), itsP-subset structure is isomorphic to the countable atomless Boolean lattice. In all other cases theP-subset structure is isomorphic to ⁽⁾ , the weak countable power of. All natural intractable sets appear to fall in the third category. The results generalize to many other complexity classes, and similar characterizations hold for, e.g., the structures formed by recursive complexity cores.This research was supported in part by the Emil Aaltonen Foundation, the Academy of Finland, and the National Science Foundation under Grant No. MCS83-14272. Part of the work was carried out while the second author was visiting the Department of Mathematics, University of California at Santa Barbara.     

On route planning by inferring visiting time,modeling user preferences,and mining representative trip patterns

Location-based services allow users to perform check-in actions, which record the geo-spatial activities and provide a plentiful source to do more accurate and useful geographical recommendation. In this paper, we present a novel Preferred Time-aware Route Planning (PTRP) problem, which aims to recommend routes whose locations are not only representative but also need to satisfy users’ preference. The central idea is that the goodness of visiting locations along a route is significantly affected by the visiting time and user preference, and each location has its own proper visiting time due to its category and population. We develop a four-stage preference-based time-aware route planning framework. First, since there is usually either noise time on existing locations or no visiting information on new locations, we devise an inference method, LocTimeInf, to predict the location visiting time on routes. Second, considering the geographical, social, and temporal information of users, we propose the GST-Clus method to group users with similar location visiting preferences. Third, we find the representative and popular time-aware location-transition behaviors by proposing Time-aware Transit Pattern Mining (TTPM) algorithm. Finally, based on the mined time-aware transit patterns, we develop a Preferred Route Search (PR-Search) algorithm to construct the final time-aware routes. Experiments on Gowalla and Foursquare check-in data exhibit the promising effectiveness and efficiency of the proposed methods, comparing to a series of competitors.     

Empirically building and evaluating a probabilistic model of user affect

We present a probabilistic model of user affect designed to allow an intelligent agent to recognise multiple user emotions during the interaction with an educational computer game. Our model is based on a probabilistic framework that deals with the high level of uncertainty involved in recognizing a variety of user emotions by combining in a Dynamic Bayesian Network information on both the causes and effects of emotional reactions. The part of the framework that reasons from causes to emotions (diagnostic model) implements a theoretical model of affect, the OCC model, which accounts for how emotions are caused by one’s appraisal of the current context in terms of one’s goals and preferences. The advantage of using the OCC model is that it provides an affective agent with explicit information not only on which emotions a user feels but also why, thus increasing the agent’s capability to effectively respond to the users’ emotions. The challenge is that building the model requires having mechanisms to assess user goals and how the environment fits them, a form of plan recognition. In this paper, we illustrate how we built the predictive part of the affective model by combining general theories with empirical studies to adapt the theories to our target application domain. We then present results on the model’s accuracy, showing that the model achieves good accuracy on several of the target emotions. We also discuss the model’s limitations, to open the ground for the next stage of the work, i.e., complementing the model with diagnostic information.

The longest common subsequence problem revisited

This paper re-examines, in a unified framework, two classic approaches to the problem of finding a longest common subsequence (LCS) of two strings, and proposes faster implementations for both. Letl be the length of an LCS between two strings of lengthm andn m, respectively, and let s be the alphabet size. The first revised strategy follows the paradigm of a previousO(ln) time algorithm by Hirschberg. The new version can be implemented in timeO(lm · min logs, logm, log(2n/m)), which is profitable when the input strings differ considerably in size (a looser bound for both versions isO(mn)). The second strategy improves on the Hunt-Szymanski algorithm. This latter takes timeO((r +n) logn), wherermn is the total number of matches between the two input strings. Such a performance is quite good (O(n logn)) whenrn, but it degrades to (mn logn) in the worst case. On the other hand the variation presented here is never worse than linear-time in the productmn. The exact time bound derived for this second algorithm isO(m logn +d log(2mn/d)), whered r is the number ofdominant matches (elsewhere referred to asminimal candidates) between the two strings. Both algorithms require anO(n logs) preprocessing that is nearly standard for the LCS problem, and they make use of simple and handy auxiliary data structures.     

Preface: Volume 23, Issue 2

This volume contains the proceedings of the First International Workshop on Symbolic Model Checking (SMC'99), held in Trento, Italy, on July 6, 1999, as part of the Second Federated Logic Conference (FLoC'99).Symbolic model checking is a formal technique for the verification of finite-state concurrent systems. Symbolic model checkers (e.g. SMV, VIS) have been used to verify industrial systems, ranging from hardware to communication protocols to safety critical plants and procedures. Symbolic model checking is the core technique for several industrial verification tools, and is applied in technology transfer projects. The aim of the SMC'99 workshop is to bring together active developers and users of symbolic model checkers, compare state of the art model checking techniques (e.g. compositional reasoning, abstraction, partitioning), discuss experimental results and experience reports, and promising directions for future research.Nine contributions (out of twenty-two submissions) were selected for presentation by the program committee. The workshop program is completed by two keynote invited lectures, given by Ken McMillan (Cadence Labs, USA) on Compositional Reasoning and Abstraction, and Fabio Somenzi (University of Colorado, USA) on Symbolic State ExplorationThanks are due to a number of people who helped to organize and plan the workshop. Among this group are the Program Committee members:

Adnan Aziz	(University of Texas at Austin, USA)
Armin Biere	(Verysys)
Sergio Campos	(Federal University of Minas Gerais, Brazil)
Alessandro Cimatti	(IRST, Italy)
Edmund Clarke	(Carnegie Mellon University, USA)
Danny Geist	(IBM Haifa, Israel)
Fausto Giunchiglia	(IRST, Italy)
Orna Grumberg	(Technion, Israel)
Markus Kaltenbach	(Siemens, Germany)
Carl Pixley	(Motorola, USA)

Full-size table

The following people helped in the evaluation of the submissions: Yael Abarbanel-Vinov, Neta Aizenbud-Reshef, Shoham Ben-David, Doron Bustan, Jorge Cuellar, David Deharbe, Cindy Eisner, Ranan Fraer, Edelweis Garcez, Leonid Gluhovsky, Marcelo Glusman, Jae-Young Jang, Shmuel Katz, Sharon Keidar, Monika Maidl, Robi Malik, Anamaria Martins Moreira, Shiri Moran, Peter Päppinghaus, Marco Roveri, Peter Warkentin, Karen Yorav, Jun Yuan, Yunshan Zhu.We would like to thank IBM Haifa Research Laboratory for the financial support to SMC'99. Carola Dori, Morena Carli, Marco Roveri and Adolfo Villafiorita helped in several matters related to the local organization. Finally, we are grateful to Michael Mislove for his constat support during the preparation of this electronic volume.Alessandro Cimatti and Orna Grumberg, Guest Editors     

Learning-theoretic perspectives of acceptable numberings

A class of recursive functionsC islimiting standardizable, in a programming system , iff there is an effective procedure which, given any -program (in the -system), synthesizes in the limit acanonical -program which is equivalent to the former. It can arguably be expected that notions similar to the above one would be relevant toGold-style function learning, which features, among other things, the effective limiting synthesis of programs for input recursive functions. Many learning classes have been characterized in terms of variants of the above notion. In this paper, we focus on the limiting standardizability of the entire class of recursive functions inEffective programming systems. To start with, we prove the independence of this notionvis-à-vis finitary recursion theorems. Secondly, we show that this motion does not entail acceptability, in the spirit of the results of Case, Riccardi and Royer on characterizations of the samevis-à-vis programming language control structures.     

The input/output complexity of transitive closure

Suppose a directed graph has its arcs stored in secondary memory, and we wish to compute its transitive closure, also storing the result in secondary memory. We assume that an amount of main memory capable of holdings values is available, and thats lies betweenn, the number of nodes of the graph, ande, the number of arcs. The cost measure we use for algorithms is theI/O complexity of Kung and Hong, where we count 1 every time a value is moved into main memory from secondary memory, or vice versa.In the dense case, wheree is close ton ², we show that I/O equal toO(n ³/s) is sufficient to compute the transitive closure of ann-node graph, using main memory of sizes. Moreover, it is necessary for any algorithm that is standard, in a sense to be defined precisely in the paper. Roughly, standard means that paths are constructed only by concatenating arcs and previously discovered paths. For the sparse case, we show that I/O equal toO(n ²e/s) is sufficient, although the algorithm we propose meets our definition of standard only if the underlying graph is acyclic. We also show that(n ²e/s) is necessary for any standard algorithm in the sparse case. That settles the I/O complexity of the sparse/acyclic case, for standard algorithms. It is unknown whether this complexity can be achieved in the sparse, cyclic case, by a standard algorithm, and it is unknown whether the bound can be beaten by nonstandard algorithms.We then consider a special kind of standard algorithm, in which paths are constructed only by concatenating arcs and old paths, never by concatenating two old paths. This restriction seems essential if we are to take advantage of sparseness. Unfortunately, we show that almost another factor ofn I/O is necessary. That is, there is an algorithm in this class using I/OO(n ³e/s) for arbitrary sparse graphs, including cyclic ones. Moreover, every algorithm in the restricted class must use(n ³e/s/log³ n) I/O, on some cyclic graphs.The work of this author was partially supported by NSF grant IRI-87-22886, IBM contract 476816, Air Force grant AFOSR-88-0266 and a Guggenheim fellowship.     

On the supervisory control of multi-agent product systems: Controllability properties

Multi-Agent (MA) product systems were defined in [I. Romanovski, P.E. Caines, On the supervisory control of multi-agent products systems, IEEE Trans. Automated Control 51(5) (2006)] where the notion of an MA controllable vector language specification was introduced and necessary and sufficient conditions for the existence of a supervisor for such a specification were derived. In this paper we present a set of results about the controllability of an MA product system and its components. In particular, we obtain an algorithm for finding the infimal MA-controllable superlanguage inf_MA(K) of a given vector (language) specification K w.r.t. an MA product system G and establish that in fact . It is proven that there is an algorithmic procedure for the recursive construction of MA supervisors when additional automata are added to a system via the MA product. Controllability properties of component structures (such as standard controllability and MA controllability of projections) are considered. Several examples are given to illustrate the results of the paper.     

Enhanced qualitative physical reasoning system: Qupras

There are many expert systems that use experimental knowledge for diagnostic analysis and design. However, there are two problems for systems using only experiential knowledge:

1. unexpected problems cannot be solved and
2. acquiring experiential knowledge from human experts is difficult.

To solve these problems, general principles or basic knowledge must be added to expert systems in addition to the experimental knowledge. In response, we previously proposed Qupras (Qualitative physical reasoning system) as a framework for basic knowledge. This system has two knowledge representations, one related to physical laws and the other to objects. By using this knowledge, Qupras reasons about the relations among physical objects, and predicts the next state of a physical phenomenon. Recently, we have improved some of Qupras’ features, and this pater desctibes the following main enhancements:

1. inheritance for representation of objects,
2. new primitive representations to describe discontinuous change, and
3. control features for effective reasoning.