Inferring (Biological) Signal Transduction Networks via Transitive Reductions of Directed Graphs

In this paper we consider the p-ary transitive reduction (TR _p ) problem where p>0 is an integer; for p=2 this problem arises in inferring a sparsest possible (biological) signal transduction network consistent with a set of experimental observations with a goal to minimize false positive inferences even if risking false negatives. Special cases of TR _p have been investigated before in different contexts; the best previous results are as follows:

Haptic two-finger contact with textiles

Real-time cloth simulation involves many computational challenges to be solved, particularly in the context of haptic applications, where high frame rates are necessary for obtaining a satisfying experience. In this paper, we present an interactive cloth simulation system that offers a compromise between a realistic physics-based simulation of fabrics and a haptic application meeting high requirements in terms of computation speed. Our system allows the user to interact with the fabric using two fingers. The required performance of the system is achieved by introducing an intermediate layer responsible for the simulation of the small part of the surface being in contact with the fingers. Additionally we separate the possible contact situations into different cases, each being individually handled by a specialised contact algorithm.

Low-latency atomic broadcast in the presence of contention

The Atomic Broadcast algorithm described in this paper can deliver messages in two communication steps, even if multiple processes broadcast at the same time. It tags all broadcast messages with the local real time, and delivers all messages in the order of these timestamps. Both positive and negative statements are used: “m broadcast at time 51” vs. “no messages broadcast between times 31 and 51”. To prevent crashed processes from blocking the system, the -elected leader broadcasts negative statements on behalf of the processes it suspects () to have crashed. A new cheap Generic Broadcast algorithm is used to ensure consistency between conflicting statements. It requires only a majority of correct processes (n > 2f) and, in failure-free runs, delivers all non-conflicting messages in two steps. The main algorithm satisfies several new lower bounds, which are proved in this paper.     

Compact separator decompositions in dynamic trees and applications to labeling schemes

This paper presents an efficient scheme maintaining a separator decomposition representation in dynamic trees using asymptotically optimal labels. In order to maintain the short labels, the scheme uses relatively low message complexity. In particular, if the initial dynamic tree contains only the root, then the scheme incurs an O(log⁴ n) amortized message complexity per topology change, where n is the current number of vertices in the tree. As a separator decomposition is a fundamental decomposition of trees used extensively as a component in many static graph algorithms, our dynamic scheme for separator decomposition may be used for constructing dynamic versions to these algorithms. The paper then shows how to use our dynamic separator decomposition to construct efficient labeling schemes on dynamic trees, using the same message complexity as our dynamic separator scheme. Specifically, we construct efficient routing schemes on dynamic trees, for both the designer and the adversary port models, which maintain optimal labels, up to a multiplicative factor of O(log log n). In addition, it is shown how to use our dynamic separator decomposition scheme to construct dynamic labeling schemes supporting the ancestry and NCA relations using asymptotically optimal labels, as well as to extend a known result on dynamic distance labeling schemes. Supported in part at the Technion by an Aly Kaufman fellowship. Supported in part by a grant from the Israel Science Foundation.     

Towards interactive simulation in automotive design

One of the important tasks in Mechanical Engineering is to increase the safety of the vehicle and decrease its production costs. This task is typically solved by means of Multiobjective Optimization, which formulates the problem as a mapping from the space of design variables to the space of target criteria and tries to find an optimal region in these multidimensional spaces. Due to high computational costs of numerical simulations, the sampling of this mapping is usually very sparse and scattered. Combining design of experiments methods, metamodeling, new interpolation schemes and innovative graphics methods, we enable the user to interact with simulation parameters, optimization criteria, and come to a new interpolated crash result within seconds. We denote this approach as Simulated Reality, a new concept for the interplay between simulation, optimization and interactive visualization. In this paper we show the application of Simulated Reality for solution of real life car design optimization problems.

Link Prediction based on Structural Properties of Online Social Networks

Question-Answering Bulletin Boards (QABB), such as Yahoo! Answers and Windows Live QnA, are gaining popularity recently. Questions are submitted on QABB and let somebody in the internet answer them. Communications on QABB connect users, and the overall connections can be regarded as a social network. If the evolution of social networks can be predicted, it is quite useful for encouraging communications among users. Link prediction on QABB can be used for recommendation to potential answerers. Previous approaches for link prediction based on structural properties do not take weights of links into account. This paper describes an improved method for predicting links based on weighted proximity measures of social networks. The method is based on an assumption that proximities between nodes can be estimated better by using both graph proximity measures and the weights of existing links in a social network. In order to show the effectiveness of our method, the data of Yahoo! Chiebukuro (Japanese Yahoo! Answers) are used for our experiments. The results show that our method outperforms previous approaches, especially when target social networks are sufficiently dense.

Exploiting User Interests to Characterize Navigational Patterns in Web Browsing Assistance

In order to be capable of exploiting context for pro-active information recommendation, agents need to extract and understand user activities based on their knowledge of the user interests. In this paper, we propose a novel approach for context-aware recommendation in browsing assistants based on the integration of user profiles, navigational patterns and contextual elements. In this approach, user profiles built using an unsupervised Web page clustering algorithm are used to characterize user ongoing activities and behavior patterns. Experimental evidence show that using longer-term interests to explain active browsing goals user assistance is effectively enhanced.

A Level-Set Method for Computing the Eigenvalues of Elliptic Operators Defined on Compact Hypersurfaces

We demonstrate, through separation of variables and estimates from the semi-classical analysis of the Schrödinger operator, that the eigenvalues of an elliptic operator defined on a compact hypersurface in ? ⁿ can be found by solving an elliptic eigenvalue problem in a bounded domain Ω?? ⁿ . The latter problem is solved using standard finite element methods on the Cartesian grid. We also discuss the application of these ideas to solving evolution equations on surfaces, including a new proof of a result due to Greer (J. Sci. Comput. 29(3):321–351, 2006).     

A Numerical Study of Diagonally Split Runge–Kutta Methods for PDEs with Discontinuities

Diagonally split Runge–Kutta (DSRK) time discretization methods are a class of implicit time-stepping schemes which offer both high-order convergence and a form of nonlinear stability known as unconditional contractivity. This combination is not possible within the classes of Runge–Kutta or linear multistep methods and therefore appears promising for the strong stability preserving (SSP) time-stepping community which is generally concerned with computing oscillation-free numerical solutions of PDEs. Using a variety of numerical test problems, we show that although second- and third-order unconditionally contractive DSRK methods do preserve the strong stability property for all time step-sizes, they suffer from order reduction at large step-sizes. Indeed, for time-steps larger than those typically chosen for explicit methods, these DSRK methods behave like first-order implicit methods. This is unfortunate, because it is precisely to allow a large time-step that we choose to use implicit methods. These results suggest that unconditionally contractive DSRK methods are limited in usefulness as they are unable to compete with either the first-order backward Euler method for large step-sizes or with Crank–Nicolson or high-order explicit SSP Runge–Kutta methods for smaller step-sizes. We also present stage order conditions for DSRK methods and show that the observed order reduction is associated with the necessarily low stage order of the unconditionally contractive DSRK methods. The work of C.B. Macdonald was partially supported by an NSERC Canada PGS-D scholarship, a grant from NSERC Canada, and a scholarship from the Pacific Institute for the Mathematical Sciences (PIMS). The work of S. Gottlieb was supported by AFOSR grant number FA9550-06-1-0255. The work of S.J. Ruuth was partially supported by a grant from NSERC Canada.     

Feature selection via sensitivity analysis of SVM probabilistic outputs

Feature selection is an important aspect of solving data-mining and machine-learning problems. This paper proposes a feature-selection method for the Support Vector Machine (SVM) learning. Like most feature-selection methods, the proposed method ranks all features in decreasing order of importance so that more relevant features can be identified. It uses a novel criterion based on the probabilistic outputs of SVM. This criterion, termed Feature-based Sensitivity of Posterior Probabilities (FSPP), evaluates the importance of a specific feature by computing the aggregate value, over the feature space, of the absolute difference of the probabilistic outputs of SVM with and without the feature. The exact form of this criterion is not easily computable and approximation is needed. Four approximations, FSPP1-FSPP4, are proposed for this purpose. The first two approximations evaluate the criterion by randomly permuting the values of the feature among samples of the training data. They differ in their choices of the mapping function from standard SVM output to its probabilistic output: FSPP1 uses a simple threshold function while FSPP2 uses a sigmoid function. The second two directly approximate the criterion but differ in the smoothness assumptions of criterion with respect to the features. The performance of these approximations, used in an overall feature-selection scheme, is then evaluated on various artificial problems and real-world problems, including datasets from the recent Neural Information Processing Systems (NIPS) feature selection competition. FSPP1-3 show good performance consistently with FSPP2 being the best overall by a slight margin. The performance of FSPP2 is competitive with some of the best performing feature-selection methods in the literature on the datasets that we have tested. Its associated computations are modest and hence it is suitable as a feature-selection method for SVM applications. Editor: Risto Miikkulainen.