Faculty Recruiting Support CICS

Combinatorial Algorithms for Graph Discovery and Experimental Design

27 May
Friday, 05/27/2022 12:00pm to 2:00pm
CS 150/151 and Zoom
PhD Thesis Defense


In this thesis, we study the design and analysis of algorithms for discovering the structure and properties of an unknown graph, with applications in two different domains: causal inference and sublinear graph algorithms. In both these domains, graph discovery is possible using restricted forms of experiments and our objective is to design low cost experiments.  


First, we describe efficient experimental approaches to the causal discovery problem, which in its simplest form, asks us to identify the causal relations (edges of the unknown graph) between variables (vertices of the unknown graph) of a given system. For causal discovery, we study algorithms for the problem of learning the causal relationships between a set of observed variables, in the presence of hidden or unobserved variables,  while minimizing a suitable cost of interventions on the observed variables. An intervention on a set of variables helps learn the presence of causal relations adjacent to them. Under various cost models for interventions, we design combinatorial algorithms for causal discovery, by identifying new connections between discrete optimization, graph property testing, and efficient intervention design. 


Next, we investigate query efficient experimental approaches for estimating various graph properties, such as, the number of edges and graph connectivity. The access to the graph, or equivalently performing an experiment, is via a Bipartite Independent Set (BIS) oracle. The BIS oracle is related to the interventional access model used in our work for causal graph discovery, with other applications in group testing and fine-grained complexity. In this setting, we develop non-adaptive algorithms that lead to efficient implementations in highly parallelized and low-memory streaming settings. 

Advisors: Andrew McGregor and Cameron Musco

Join via Zoom