Research Page for Iyad Kanj

Research Interests: Parameterized and exact computation; combinatorial optimization; graph theory/algorithms; computational geometry; robotic motion planning; computational biology.

Current Students

Jiahao Deng (Ph.D. student)	Brandon Meng (Ph.D. student)	Atul Ponda (M.S. student)

Current Research Projects

Matrix Completion & Clustering

• Matrix Completion Modulo Constraints: Matrix completion is a fundamental problem in Machine Learning. Given a matrix with missing entries, the goal is to complete the matrix so as to minimize a certain objective measure, such as the rank of the matrix, or the number of subspaces of bounded dimension into which the matrix can be partitioned. A richer setting is when the completion is subject to constraints imposed on the complete matrix.

           The goal of this project is to investigate the complexity and design parameterized/exact algorithms for matrix completion problems.

• Clustering Incomplete Data: Clustering is a fundamental problem in data analytics, where the objective is to cluster the data points so that the intra-cluster similarity is high. In this setting, given a matrix, some of whose entries might be missing, the objective is to complete the missing entries in order to enable a partitioning of the matrix vectors/rows into clusters, such that all elements in the same cluster are ``similar.'' Several measures of intra-cluster similarity are studied, including the radius and diameter of the clusters.
  
  The goal of this project is to design parameterized algorithms with respect to natural clustering parameters such as: the radius/diameter of the clusters, the number of clusters, the rank of the clusters, among others.  

Robotic Motion Planning

• Path Planning in the Presence of Obstacles: Path planning is the problem of computing a path between two points that satisfies some desirable properties. Properties of interest include: shortest (w.r.t. Euclidean length or some weight function), obstacle-free, or if the latter is not possible, a path that overlaps with the fewest number of obstacles. Such problems shave applications in robotics, and lead to interesting computational geometry and/or graph problems.

           In certain applications, the robot is equipped with a devise with a coverage range (e.g., a camera, or a paint spray), and an additional requirement on the sought path is that it covers a certain area/volume (i.e., every point in the
          area/volume is within the range of some point on the path).  Examples of such applications include covering a terrain by a sweeping robot or by a robot equipped with a camera, or painting a 3-D object.

           The goal of this project is to study parameterized/exact and approximation algorithms for such coverage problems, which, in most cases, turn out to be computationally hard.

• Reliable & Efficient Motion Planning for Continuum-Arm Robots: Continuum-arm robots are bio-inspired devices that seek a middle ground between rigid and soft robots. They are made of multiple sections, where each section is a bundle of pneumatic muscle actuators. This results in high compliance, payload, inherent safety, and dexterous manipulability, making them perfectly suited to serve as co-robots. However, their high level of compliance comes at the price of high redundancy in their spatial shapes, making motion planning for such robots a big challenge, especially in environments clattered with obstacles.

           The goal of this project is to design efficient, reliable, and stable motion planning algorithms for continuum-arm robots.

Recent Editorial and PC Service

• Program committee member of the 36th International Symposium on Computational Geometry  (SoCG), 2020.

• Program committee member of the 34th AAAI Conference on Artificial Intelligence (AAAI), 2020.

• Program committee member of the 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), 2020.

• Program committee member of the International Joint Conference on Artificial Intelligence (IJCAI), 2019, 2018.

• Program committee member  of the Annual International Computing and Combinatorics Conference (COCOON), 2019, 2018, 2017, 2015, 2014, 2013, 2011, 2001.

• Program committee member of the Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), 2018.

• Program committee member of the International Frontiers of Algorithmics Workshop (FAW), 2018, 2015, 2014.

• Steering committee member of the International Symposium on Parameterized and Exact Computation (IPEC), 2014-2017.

• Guest editor (with Thore Husfeldt) of the special issue of Algorithmica on Parameterized and Exact Computation, 2017.

• Program committee member of the International Workshop on Graph-Theoretic Concepts in Computer Science (WG), 2017, 2014.

• Co-chair (and proceedings guest editor) of the 10th International Symposium on Parameterized and Exact Computation (IPEC), 2015.

• Program committee member of the International Symposium on BioInformatics Research and Applications (ISBRA), 2014, 2013, 2012, 2011.

• Program committee member of the 21st Annual European Symposium on Algorithms (ESA), 2013.

• Program committee member of the Annual International Conference on Combinatorial Optimization and Applications (COCOA), 2013, 2012.

• Program committee member of the International Symposium on Parameterized and Exact Computation (IPEC), 2011, 2009, 2008.

• Program committee member of the 6th Annual Conference on Theory and Applications of Models of Computation (TAMC), 2009.

• Guest editor (with Jianer Chen), Algorithmica, special issue on parameterized and exact algorithms, 2008.