Complexity class | EPFL Graph Search

In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of a type of computational problem, a model of computation, and a bounded resource like time or memory. In particular, most complexity classes consist of decision problems that are solvable with a Turing machine, and are differentiated by their time or space (memory) requirements. For instance, the class P is the set of decision problems solvable by a deterministic Turing machine in polynomial time. There are, however, many complexity classes defined in terms of other types of problems (e.g. counting problems and function problems) and using other models of computation (e.g. probabilistic Turing machines, interactive proof systems, Boolean circuits, and quantum computers). The study of the relationships between complexity classes is a major ar

Incremental View Maintenance for Collection Programming

Christoph Koch, Daniel Lupei, Val Tannen

In the context of incremental view maintenance (IVM), delta query derivation is an essential technique for speeding up the processing of large, dynamic datasets. The goal is to generate delta queries that, given a small change in the input, can update the materialized view more efficiently than via recomputation. In this work we propose the first solution for the efficient incrementalization of positive nested relational calculus (NRC+) on bags (with integer multiplicities). More precisely, we model the cost of NRC+ operators and classify queries as efficiently incrementalizable if their delta has a strictly lower cost than full re-evaluation. Then, we identify NRC+, a large fragment of NRC+ that is efficiently incrementalizable and we provide a semantics-preserving translation that takes any NRC+ query to a collection of IncNRC+ queries. Furthermore, we prove that incremental maintenance for NRC+ is within the complexity class NC0 and we showcase how recursive IVM, a technique that has provided significant speedups over traditional IVM in the case of flat queries, can also be applied to IncNRC+.

ACM2016

Compilation Techniques for Incremental Collection Processing

Daniel Lupei

Many map-reduce frameworks as well as NoSQL systems rely on collection programming as their interface of choice due to its rich semantics along with an easily parallelizable set of primitives. Unfortunately, the potential of collection programming is not entirely fulfilled by current systems as they lack efficient incremental view maintenance (IVM) techniques for queries producing large nested results. This comes as a consequence of the fact that the nesting of collections does not enjoy the same algebraic properties underscoring the optimization potential of typical collection processing constructs. We propose the first solution for the efficient incrementalization of collection programming in terms of its core constructs as captured by the positive nested relational calculus (NRC+) on bags (with integer multiplicities). We take an approach based on delta query derivation, whose goal is to generate delta queries which, given a small change in the input, can update the materialized view more efficiently than via recomputation. More precisely, we model the cost of NRC+ operators and classify queries as efficiently incrementalizable if their delta has a strictly lower cost than full re-evaluation. Then, we identify IncNRC+, a large fragment of NRC+ that is efficiently incrementalizable and we provide a semantics-preserving translation that takes any NRC+ query to a collection of IncNRC+ queries. Furthermore, we prove that incrementalmaintenance for NRC+ is within the complexity class NC0 and we showcase how Recursive IVM, a technique that has provided significant speedups over traditional IVM in the case of flat queries, can also be applied to IncNRC+ . Existing systems are also limited wrt. the size of inner collections that they can effectively handle before running into severe performance bottlenecks. In particular, in the face of nested collections with skewed cardinalities developers typically have to undergo a painful process of manual query re-writes in order to ensure that the largest inner collections in their workloads are not impacted by these limitations. To address these issues we developed SLeNDer, a compilation framework that given a nested query generates a set of semantically equivalent (partially) shredded queries that can be efficiently evaluated and incrementalized using state of the art techniques for handling skew and applying delta changes, respectively. The derived queries expose nested collections to the same opportunities for distributing their processing and incrementally updating their contents as those enjoyed by top-level collections, leading on our benchmark to up to 16.8x and 21.9x speedups in terms of offline and online processing, respectively. In order to enable efficient IVM for the increasingly common case of collection programming with functional values as in Links, we also discuss the efficient incrementalization of simplytyped lambda calculi, under the constraint that their primitives are themselves efficiently incrementalizable.

EPFL2017

Dynamic Grasp Adaptation

Miao Li

The human hand is an amazing tool, demonstrated by its incredible motor capability and remarkable sense of touch. To enable robots to work in a human-centric environment, it is desirable to endow robotic hands with human-like capabilities for grasping and object manipulation. However, due to its inherent complexity and inevitable model uncertainty, robotic grasping and manipulation remains a challenge. This thesis focuses on grasp adaptation in the face of model and sensing uncertainties: Given an object whose properties are not known with certainty (e.g., shape, weight and external perturbation), and a multifingered robotic hand, we aim at determining where to put the fingers and how the fingers should adaptively interact with the object using tactile sensing, in order to achieve either a stable grasp or a desired dynamic behaviour. A central idea in this thesis is the object-centric dynamics: namely, that we express all control constraints into an object-centric representation. This simplifies computa- tion and makes the control versatile to the type of hands. This is an essential feature that distinguishes our work from other robust grasping work in the literature, where generating a static stable grasp for a given hand is usually the primary goal. In this thesis, grasp adaptation is a dynamic process that flexibly adapts the grasp to fit some purpose from the objectâs perspective, in the presence of a variety of uncertainties and/or perturbations. When building a grasp adaptation for a given situation, there are two key problems that must be addressed: 1) the problem of choosing an initial grasp that is suitable for future adaptation, and more importantly 2) the problem of design- ing an adaptation strategy that can react adequately to achieve desired behaviour of the grasped object. To address challenge 1 (planning a grasp under shape uncertainty), we propose an approach to parameterizing the uncertainty in object shape using Gaussian Processes (GPs) and incorporate it as a constraint into contact-level grasp planning. To realize the planned contacts using different hands interchangeably, we further develop a prob- abilistic model to predict the feasible hand configurations, including hand pose and finger joints, given the desired contact points only. The model is built using the con- cept of Virtual Frame(VF), and it is independent from the choice of hand frame and object frame. The performance of the proposed approach is validated on two differ- ent robotic hands, an industrial gripper (4 DOF Barrett hand) and a humanoid hand (16 DOF Allegro hand) to manipulate objects of daily use with complex geometry and various texture (a spray bottle, a tea caddy, a jug and a bunny toy). In the second part of this thesis, we propose an approach to the design of adapta- tion strategy to ensure grasp stability in the presence of physical uncertainties of objects(object weight, friction at contacts and external perturbation). Based on an object-level impedance controller, we first design a grasp stability estimator in the object frame using the grasp experience and tactile sensing. Once a grasp is predicted to be unstable during online execution, the grasp adaptation strategy is triggered to improve the grasp stability, by either changing the stiffness at finger level or relocating the position of one fingertip to a better area.