Ijay Narang

2026

  1. Mixing Time Analysis of Abandonment Queues: A Two-Pronged Attack Via Lyapunov Drift And Bakry-Émery

    Hoang Huy Nguyen, Ijay Narang, Aditya Lonkar, and Siva Theja Maguluri

    In Submission

    @misc{NguyenNarangLonkarMaguluri2026abandonmentQueues,
  title = {Mixing Time Analysis of Abandonment Queues: A Two-Pronged Attack Via Lyapunov Drift And Bakry-{\'{E}}mery},
  author = {Nguyen, Hoang Huy and Narang, Ijay and Lonkar, Aditya and Maguluri, Siva Theja},
  note = {In Submission},
  year = {2026}
}

  2. Optimal detection of planted stars via a random energy model

    Ijay Narang, Will Perkins, and Timothy Wee

    In submission, 2026

    arXiv
    We study the problem of detecting a planted star in the Erdős-Rényi random graph \(G(n,m)\), formulated as a hypothesis test. We determine the scaling window for critical detection in \(m\) in terms of the star size, and characterize the asymptotic total variation distance between the null and alternative hypotheses in this window. In the course of the proofs we show a condensation phase transition in the likelihood ratio that closely resembles that of the random energy model from spin glass theory.
    @article{NarangPerkinsWee2026plantedStar,
  title = {Optimal detection of planted stars via a random energy model},
  author = {Narang, Ijay and Perkins, Will and Wee, Timothy},
  journal = {arXiv preprint arXiv:2602.15585},
  year = {2026}
}

  3. Steady-State Behavior of Constant-Stepsize Stochastic Approximation: Gaussian Approximation and Tail Bounds

    Zedong Wang, Yuyang Wang, Ijay Narang, Felix Wang, Yuzhou Wang, and Siva Theja Maguluri

    ICML 2026

    arXiv
    Constant-stepsize stochastic approximation (SA) is widely used in learning for computational efficiency. For a fixed stepsize, the iterates typically admit a stationary distribution that is rarely tractable. Prior work shows that as the stepsize \(\alpha \downarrow 0\), the centered-and-scaled steady state converges weakly to a Gaussian random vector. However, for fixed \(\alpha\), this weak convergence offers no usable error bound for approximating the steady-state by its Gaussian limit. This paper provides explicit, non-asymptotic error bounds for fixed \(\alpha\). We first prove general-purpose theorems that bound the Wasserstein distance between the centered-scaled steady state and an appropriate Gaussian distribution, under regularity conditions for drift and moment conditions for noise. To ensure broad applicability, we cover both i.i.d. and Markovian noise models. We then instantiate these theorems for three representative SA settings: (1) stochastic gradient descent (SGD) for smooth strongly convex objectives, (2) linear SA, and (3) contractive nonlinear SA. We obtain dimension- and stepsize-dependent, explicit bounds in Wasserstein distance of order \(\alpha^{1/2}\log(1/\alpha)\) for small \(\alpha\). Building on the Wasserstein approximation error, we further derive non-uniform Berry--Esseen-type tail bounds that compare the steady-state tail probability to Gaussian tails. We achieve an explicit error term that decays in both the deviation level and stepsize \(\alpha\). We adapt the same analysis for SGD beyond strongly convexity and study general convex objectives. We identify a non-Gaussian (Gibbs) limiting law under the correct scaling, which is validated numerically, and provide a corresponding pre-limit Wasserstein error bound.
    @article{WangWangNarangWangWangMaguluri2026constantStepsize,
  title = {Steady-State Behavior of Constant-Stepsize Stochastic Approximation: Gaussian Approximation and Tail Bounds},
  author = {Wang, Zedong and Wang, Yuyang and Narang, Ijay and Wang, Felix and Wang, Yuzhou and Maguluri, Siva Theja},
  journal = {arXiv preprint arXiv:2602.13960},
  year = {2026}
}

2025

  1. Sharp Inner Product Correlations for Hypercube Bijections

    Ijay Narang and Muchen Ju

    In submission, 2025

    arXiv
    We resolve a conjecture of Rob Morris concerning bijections on the hypercube. Specifically, we show that for any bijection \(f : \{-1,1\}^n \to \{-1,1\}^n\), \(\Pr_{x,y \in \{-1,1\}^n}\big[ \langle x,y \rangle \ge 0 \;\text{and}\; \langle f(x),f(y) \rangle \ge 0 \big] \ge \tfrac{1}{4} - O(1/\sqrt{n})\), implying the same lower bound for the joint event under any two bijections. Our proof proceeds by applying the spectral decomposition of the Hamming association scheme, which allows us to reformulate the problem as a linear program over the Birkhoff polytope. This makes it possible to isolate the contribution of the nontrivial spectrum, which we show is asymptotically negligible, leaving the dominant contribution arising from the principal eigenvalue.
    @article{NarangJu2025hypercubeBijections,
  title = {Sharp Inner Product Correlations for Hypercube Bijections},
  author = {Narang, Ijay and Ju, Muchen},
  journal = {arXiv preprint arXiv:2509.00716},
  year = {2025}
}

Undergraduate Work

  1. On even-H-free Colorings

    Ijay Narang. Advised by Dr. Noga Alon

    PDF
    For a given graph \(H\), an edge-coloring \(C\) of the complete graph \(K_n\) is even-\(H\)-free if every copy of \(H\) intersects at least one color class with an odd number of edges. These colorings are motivated by the study of graph codes, which were introduced in earlier work. Even-\(H\)-free colorings exhibit interesting properties and are closely related to other problems in Ramsey Theory. The present short paper includes new results about the extremal properties of such colorings. Let \(g(n,H)\) be the minimum number of colors required in an even-\(H\)-free coloring of \(K_n\). Our main result is the identification of a class of graphs \(H\), namely forests of even stars satisfying appropriate size constraints, for which \(g(n,H)=\Theta(n^2)\).
    @misc{NarangEvenHFreeColorings,
  title = {On even-H-free Colorings},
  author = {Narang, Ijay},
  note = {Advised by Dr. Noga Alon}
}

  2. On Expansion, High-Dimensional Expanders, and Applications in Coding Theory

    Ijay Narang. Undergraduate Thesis. Advised by Dr. Pedro Paredes

    PDF
    Communication protocols and data storage necessitate the use of error-correcting codes, which inject redundancy into a bit-string to make it resilient against corruption. Desirable properties of such codes include distance, ensuring recoverability of the original message, and rate, capturing transmission efficiency. It is well known that expander graphs, sparse yet highly connected graphs, can be used to construct codes that achieve strong trade-offs between these parameters. Furthermore, the higher dimensional analog of expanders, high dimensional expanders, have also found useful applications in coding theory. Thus, this thesis studies this intersection of expanders, high dimensional expanders, and coding theory. Thematically, this paper can be viewed in two parts: the first is a survey of classical and recent ideas in this area, and the second presents new combinatorial constructions of expanding square and cubical complexes.
    @misc{Narang2024expandersCodingTheory,
  title = {On Expansion, High-Dimensional Expanders, and Applications in Coding Theory},
  author = {Narang, Ijay},
  note = {Undergraduate thesis, advised by Dr. Pedro Paredes}
}