Computationally hard search and optimization problems are ubiquitous in science, engineering andbusiness. Examples include drug design, protein folding, phylogeny reconstruction, hardware andsoftware design, test generation and verification, planning, timetabling, scheduling and on and on. Inrare cases, practical application-specific software exists, but most often development of successfulmethods requires hiring specialists, and often significant time and expense, […]

We are interested in understanding the power and limitations of families of algorithms for solving combinatorial search problems, in particular those whose decision versions are NP-complete.   In some application areas involving such problems, the state of the art involves representing a problem instance as a formula of propositional logic (or a natural extension, typical examples […]

I’ve started a new research project with the goal of implementing a new algorithm which interpolates a polynomial F of degree D in N variables with T non-zero terms. It has long been known how to interpolate a polynomial F(x) in one variable of degree D from D+1 values of F in O( D log […]

With the fast growth in the Micro-Electromechanical System (MEMS) market, there is also growing need for miniaturized power sources. MEMS devices are beginning to make significant contributions in new subjects, including Lab-on-Chips (LOC) and other micro-fluidic devices, wireless communications, sensors, and optics. In all these technologies, electric power is a vital issue for the further […]

Determining the properties of materials has always been one of the primary goals of research in materials science. Computational models for materials’ property determination are hindered by their high computational cost; it can take weeks (even years) to develop and evaluate a computational model for a single property of a single material. The current approach […]

During the past two decades, the primal-dual scheme has been a major tool for the design of algorithms with very good approximation factors for NP-hard problems. This method is based on the duality theorems of Linear Programming (LP): Strong duality ensures that satisfaction of complementary slackness conditions implies optimality of a (fractional) solution. “Good” relaxation […]

In this project, we will explore the capability to produce meaningful amounts of electricity by thermoelectric generation from waste heat in industrial applications.  We will derive theory to evaluate the capability of thermoelectric power generators and design and build simple thermoelectric generation devices to test the theory.  We will compare metal and semiconductor thermoelectric materials.  […]

The primary vision of my group’s research is implementing light as the principal physical medium for quantum information processing. Light is an ideal communication agent: because the energy of the photon is normally much higher than the average temperature of the environment, it can propagate many miles without losing the information it carries. Therefore, no […]

Recent studies have shown that many licensed spectrum bands are under-utilized, which formspectrum holes [1]. The concept of cognitive radio was introduced in order to increase theusage of the spectrum [2]. In cognitive radio systems [3], unlicensed users (which are alsocalled secondary users) can perform sensing over a wide range of spectrum bands. Thesecondary users […]

To perform changes to large software systems correctly, software developers must communicate efficiently and effectively about the intended change and must perform the technical work associated with the change precisely and completely. Currently, as developers collaborate with each other and interact with the many artifacts involved in a software change task, they must work frequently […]

The Curious George project aims to construct a spatial-semantic modeling system featuring automated learning of object appearance and object-place relations from online annotated database, and the application of these relations to a variety of real-world tasks. The physical system currently developed at UBC, a visually guided mobile robot, can recognize objects in an environment based […]

The accurate recording of EEG (electro-encephalographic) signals from the scalp provides an important source of information for many research topics focused on analyzing the correlation between brain dynamics and specific states of the body for patients or healthy subjects. The recording of clean EEG signals becomes nevertheless a daunting task when attempting to quantify the […]