Research

Below is a detailed description of some of the research that I have worked on. Google scholar should have a regularly updated list, found here.

Bayes DistNet - A Robust Neural Network for Algorithm Runtime Distribution Predictions (AAAI-21)

Many of the algorithmic solvers for NP-complete problems rely on backtrack methods with added randomness/restarts (to help alleviate some of the heavy-tail nature that the runtimes exhibit when they traverse down eventual dead-ends in the search tree). Introducing randomness into the solvers means that a given algorithm ran on the same input problem follows some unknown distribution. Portfolio solvers use a collection of different algorithms, and tries to assign the algorithm technique which would solve the given input the fastest. Knowing the RTDs of each algorithm in the portfolio allows such solvers to choose the best algorithm for a given problem instance.

The tradition state-of-the-art model DistNet jointly learns the parameters of the RTD by using a neural network, with one output for each parameter of the distribution. For example, if we assume the RTD follows a Normal distribution $\mathcal{N}(\mu, \sigma^2)$, then the network would have one output for $\mu$, and another for $\sigma^2$. These standard neural networks tend to overfit when the amount of training data is small.

We extend DistNet into the Bayesian setting using Bayesian neural networks (BNN), calling it Bayes DistNet. Instead of using pointwise weights in the network, BNNs have a prior distribution over its weights and uses posterior inference. Sinces the posterior is an intractible calculation, variational methods are used to construct an approximation to the distribution. Finally, our model has a single output which is the predicted runtime. By using the same input to our mdoel multiple times, different runtimes will be predicted and combining them will produce a predicted runtime distribution.

We show that our model Bayes DistNet is able to predict distributions that more closely resemble the true runtime distribution when the number of training samples are small, or when there are censored examples (only lower bounds on the actual runtime are known, as the algorithm took too long and had to prematurely stop). Our model is also able to give its uncertainty on its predictions.

Chromatic Symmetric Functions and H-free Graphs (Graphs and Combinatorics - Springer)

A symmetric polynomial on $n$ variables is a polynomial such that if any of the variables are interchanged, one obtains the same polynomial. Symmetric polynomials have many basis, one of which being the elementary symmetric polynomials (denoted $e$). The chromatic polynomial $\chi_{G}(k)$ gives the number of proper colourings for a graph $G$, with $k$ colours. The chromatic symmetric function $X(G)$ of a graph $G$ is a symmetric polynomial which is a formal power series over all proper colourings of the graph $G$, which is a generalization of the chromatic polynomial.

A long standing conjecture by Stanley is that if $G$ is an incomparability graph of a $(3+1)$-free poset, then $X(G)$ is $e$-positive (positive linear combination of elementary basis terms). Another basis of symmetric functions is the Schur basis. It is well known that $e$-positivity implies Schur-positivity. Stanley’s conjecture has been well studied, as the proof of $e$-positivity would allow the use of well known properties that comes from Schur-positivity.

The claw graph ($K_{1,3}$) is known to not be $e$-positive. A subset of Stanley’s conjecture has to do with finding the whether H-free graphs, where H = {claw, F} and F is some graph, is $e$-positive. In our work, we settle the question for all cases, except H = {claw, co-diamond}, and we provide some partial results in that case.