Anushka Jain supervised by Suryajith Chillara received his Master of Science – Dual Degree in Computer Science and Engineering (CSD) by Research. Here’s a summary of her research work on Average Case Hardness of #HC: Limits of the Second Moment Method

We study the average-case complexity of counting directed Hamiltonian cycles in the Erd˝os–R´enyi random digraph D(n, p). Using the planted-distribution framework, we exhibit a phase transition governed by the second moment R(p) → e 1/p−1 : when p → 1 the distributions are statistically indistinguishable and a trivial fixed estimator succeeds, while for constant p or p near the Hamiltonicity threshold the planted framework provably cannot establish hardness, because efficient distinguishing tests already exist. As an alternative route to hardness, we propose two computational pseudorandomness hypotheses asserting that #HC(G) mod q is computationally indistinguishable from a uniform residue, motivated by information-theoretic equidistribution evidence and an analogous open conjecture of Ghasemi, Gross, and Kopparty on the permanent over finite fields. Under these hypotheses, no polynomial-time algorithm computes #HC(G) mod q better than random guessing, and no polynomial-time algorithm computes #HC(G) exactly on more than a negligible fraction of inputs. We do not establish unconditional hardness in any regime; the conditional results act as a program for future work.

September 2026