2024 Cheriton Research Symposium

A set of vertices in a graph forms an independent set when no two vertices in the set are connected by an edge. The problem of determining whether a graph contains a large independent set is fundamental in computer science as it shows up in countless applications. It is also notoriously hard: not only is the problem itself NP-complete, but so are many of its natural approximation relaxations.

In 1998, however, Goldreich, Goldwasser, and Ron showed that the Independent Set Testing problem, one of the natural relaxations of the independent set problem, is surprisingly easy in one sense: for some range of parameters, the problem can even be solved by algorithms that examine only a tiny fraction of the graph itself. In this talk, I will briefly outline recent developments on this problem and other related problems in the study of sublinear-time algorithms.

Eric Blais is an Associate Professor in the Algorithms and Complexity Theory group at the Cheriton School of Computer Science. His research interests span theoretical computer science with special focus on sublinear-time algorithms, randomness in computation, and complexity theory.

His achievements include being the recipient of a prestigious best paper award at FOCS 2020 for work with his colleague Professor Shalev Ben-David that extended Yao’s minimax theorem. In 2021, Professor Blais received an Ontario Early Researcher Award to develop new theoretical foundations for sublinear-time algorithms.

He has a PhD from Carnegie Mellon University and was a Simons Foundation Postdoctoral Fellow at MIT from 2012–14.

Cheriton Fellow Semih Salihoğlu | DC 1302

Architectural Principles of Modern Graph DBMSs

Modern graph database management systems (GDBMSs) adopt the property graph data model, in which records are modeled as nodes and edges with key value properties, and SQL-like query languages that have elegant arrow-based syntaxes to draw the graph patterns that are searched in an input database. GDBMSs have become an important class of DBMSs that support a variety of applications that require finding paths and patterns across input records, such as fraud and threat detection and recommendation engines.

In this talk, I will overview several architectural principles of these systems, focusing on their query processors. I will argue that the core challenge in developing an efficient query processor for GDBMSs is the explosion of intermediate results that are generated when patterns are searched across the many-to-many relationships in graph-structured databases. I will then review two high-level techniques, worst-case optimal joins and factorization, that should be at the core of the query processors of modern GDBMSs that mitigate this intermediate results explosion in two different ways: (i) by reducing the searched space through novel join algorithms; or (ii) compressing the intermediate results during query processing. These techniques have been integrated into Kùzu, a new GDBMS that started as a research project in my group and is now being developed at a spinoff company in Waterloo.

Semih Salihoğlu is an Associate Professor at the Cheriton School of Computer Science. His research focuses on systems and theoretical research in data management and processing. His systems work focuses on developing systems for managing, querying, or doing analytics on graph-structured data. His main on-going systems project is Kùzu, which is a new embeddable GDBMS that is designed for high scalability and very fast querying.

He has served as the PC co-chair for SIGMOD’s demonstration track and co-chaired the GRADES-NDA workshop, the premier workshop on graph data management, and serves on its steering committee. He has a PhD from Stanford and is a recipient of several paper awards, among them a 2018 VLDB Best Paper Award, a 2022 ACM SIGMOD Research Highlight Award, and a Best Experiment, Analysis and Benchmark Paper Award at VLDB 2022.

Panel Discussion

The Future of Computer Science Education

A dynamic discussion on the future of computer science education in universities. Panelists will reflect on the evolution of CS education and explore its current landscape, with a spotlight how we must adapt in the era of online learning tools and generative AI to prepare the next generation.

Panelists: David R. Cheriton, Carmen Bruni, Gordon Cormack and Mei Nagappan

Moderator: Dave Tompkins

Lunch | DC 1301

By invitation