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}
}

Reliable visual reasoning requires composing multiple visual observations and returning consistent answers to logically equivalent questions. We introduce Hob-VL, a benchmark for visually grounded Boolean reasoning. Hob-VL comprises two tasks: (1) evaluating whether a Boolean rule holds in an image, and (2) identifying the (unique) object satisfying a Boolean description. Hob-VL contains 6,000 human-verified balanced Yes/No questions, each defined by a Boolean combination of ten visual statements, across 1,000 generated scenes and 46 diverse labeled photographs, along with 1,000 object-identification questions over the same photographs. Our question families are deliberately constructed to challenge reasoning through misleading local cues and nested logical operations, and include symbolic and structured natural-language presentations. Across eight model configurations with thinking disabled or minimized, Boolean accuracy ranges from 48.52% to 50.57%, while the identification accuracy reaches at most 43.0%. A thinking-enabled GLM configuration achieves uneven gains while retaining substantial errors and inconsistencies. Hob-VL exposes these failures through executable reference answers and matched evaluations.

@article{WangAnandNarang2026hobVL,
  title = {{Hob-VL}: A Benchmark for Visually Grounded Boolean Reasoning},
  author = {Wang, Yuzhou and Anand, Emile and Narang, Ijay},
  journal = {arXiv preprint arXiv:2610.01605},
  year = {2026}
}

Motivated by recent work of Kocurek, Oveis Gharan, and Tjowasi, which gives an efficient sampling algorithm for the hard-core model on random regular bipartite graphs by decomposing into fixed-size slices, we study the worst-case tractability of approximate counting and sampling of fixed-size slices for bipartite independent set problems. Let \(G=(L\sqcup R,E)\) be a bipartite graph with \(|L|=|R|=n\) and maximum degree \(\Delta\). The fixed-slice problem asks to sample uniformly from independent sets satisfying \(|I\cap L|=\alpha_L n\) and \(|I\cap R|=\alpha_R n\). We show that if the overall density \(\alpha\) lies in the interval \((\frac{1}{\Delta}, \tfrac{1}{2})\), and the densities on the two sides are more balanced than the typical phase densities of a random \(\Delta\)-regular bipartite graph, then there is no FPRAS or efficient sampling scheme unless \(\mathbf{NP}=\mathbf{RP}\). We then study a related fugacity model in which the densities are not fixed, but the independent set is required to be balanced between the two sides of the bipartition. For \(\lambda>0\), the balanced hard-core model is the ordinary hard-core model with fugacity \(\lambda\), conditioned on the event \(|I\cap L|=|I\cap R|\). We prove that this model has the same computational threshold as the hard-core model on general bounded-degree graphs. That is, for every fixed \(\Delta\geq 3\), if \(\lambda<\lambda_c(\Delta)\), then the balanced partition function admits an FPTAS and the balanced hard-core distribution admits an efficient sampling scheme. Conversely, if \(\lambda>\lambda_c(\Delta)\), then no FPRAS or efficient sampler exists on this graph class unless \(\mathbf{NP}=\mathbf{RP}\).

@article{NarangPerkinsWangWee2026bipartiteIndependentSets,
  title = {Computational Thresholds for Balanced and Fixed-Slice Independent Sets in Bipartite Graphs},
  author = {Narang, Ijay and Perkins, Will and Wang, Yuzhou and Wee, Timothy L. H.},
  journal = {arXiv preprint arXiv:2608.02503},
  year = {2026}
}

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}
}

We study deterministic approximation algorithms for the permanent of a nonnegative matrix through the Bethe permanent, an approximation computable in polynomial time. The tight analysis of Anari and Rezaei gives a universal comparison between the permanent and the Bethe permanent within a factor \((\sqrt 2)^n\). The simple example of the unweighted \(4\)-cycle \(C_4\) (or a union of disjoint \(C_4\)'s) shows that this bound is tight. We show that such \(4\)-cycle obstructions can be identified and exploited algorithmically. Given a Bethe optimizer, our algorithm identifies nearly isolated weighted \(2\times2\) blocks and peels off a vertex-disjoint family of them. If the total weighted correction is large, we can improve the Bethe approximation; if it is small, we show that the Bethe permanent is within a factor of \((\sqrt2 - \varepsilon)^n\) of the truth. Combining these facts, we obtain a deterministic polynomial time \((\sqrt2-\varepsilon)^n\)-approximation algorithm for the permanent of an arbitrary nonnegative \(n\times n\) matrix, where \(\varepsilon>0\) is some absolute constant.

@article{NarangPerkins2026structuralCorrectionsBethe,
  title = {Structural Corrections to the Bethe Approximation of the Permanent},
  author = {Narang, Ijay and Perkins, Will},
  journal = {arXiv preprint arXiv:2608.31061},
  year = {2026}
}

We give approximate counting and sampling algorithms for spin models on graphs of low threshold rank or high girth. Given any \(n\)-vertex graph \(G\), let \(k_\eta = k_\eta(G)\) count normalized-Laplacian eigenvalues strictly below \(\eta\). For \(\varepsilon > 0\), an \(\varepsilon\)-approximate counting algorithm outputs an estimate \(\widehat Z\) of the partition function \(Z\) satisfying \((1-\varepsilon)Z\le\widehat Z\le(1+\varepsilon)Z\) with probability at least \(3/4\). An \(\varepsilon\)-approximate sampling algorithm outputs a configuration whose distribution is within total variation distance \(\varepsilon\) of the target distribution. We give the following results:

(a) Ferromagnetic Potts. Fix \(q\ge2\) and \(\eta\in(0,1]\). There exists \(\beta_0(q,\eta)\) such that, for every inverse temperature \(\beta\ge\beta_0\), the zero-field \(q\)-state Potts model admits approximate counting and sampling algorithms: (i) On arbitrary graphs in time \(\exp(O(k_\eta))\operatorname{poly}(n,1/\varepsilon).\) (ii) Fix \(\Delta \ge 3\). On \(\Delta\)-regular graphs of girth \(g\) in time \(\exp(O(n e^{-g})) \operatorname{poly}(n,1/\varepsilon).\)

(b) Bipartite hard-core. Fix \(\Delta\ge3\) and \(\eta\in(0,1]\). There exists \(\lambda_0(\Delta,\eta)\) such that, for every fugacity \(\lambda\ge\lambda_0\), the hard-core model admits approximate counting and sampling: (i) On \(\Delta\)-regular vertex-transitive bipartite graphs in time \(\exp(O (k_\eta))\operatorname{poly}(n,1/\varepsilon).\) (ii) On \(\Delta\)-regular bipartite graphs of girth \(g\) in \(\exp(O(n e^{- g}))\operatorname{poly}(n,1/\varepsilon).\)

All four results follow from verifying the hypotheses of a new framework we call C-3PO. At a high level, the C-3PO algorithm proceeds by enumerating small cuts and reconstructing the original measure through cluster expansions. Underlying the algorithm is an improvement of subspace enumeration methods via active regression.

@article{Narang2026c3po,
  title = {The {C-3PO} Framework: Algorithms for {$\#\mathrm{BIS}$}-Hard Problems on Graphs with Low Threshold Rank or High Girth},
  author = {Narang, Ijay},
  journal = {arXiv preprint arXiv:2610.42011},
  year = {2026}
}

We give complexity-theoretic separations between \(\#\mathrm{BIS}\) and \(\#\mathrm{IS}\). Given a graph \(G\), and a fugacity \(\lambda>0\), the hard-core model is given by \(Z_G(\lambda)=\sum_{I\in\mathcal I(G)}\lambda^{|I|}\), where \(\mathcal I(G)\) denotes the independent sets of \(G\). For \(F\ge1\), an \(F\)-factor approximation to \(Z_G(\lambda)\) is an estimate \(\widehat Z\) satisfying \(F^{-1}Z_G(\lambda)\le\widehat Z\le FZ_G(\lambda)\). Let \(\mathcal G_\Delta\) denote the class of \(\Delta\)-regular graphs and \(\mathcal G_{\Delta,\Delta}\) the class of \(\Delta\)-regular bipartite graphs. We give two separation results.

(1) There exist an integer \(\Delta\ge3\), a sufficiently large fugacity \(\lambda\), and a constant \(c>0\) so that the following hold: (a) For every \(\delta\in(0,1)\), deterministic \((1+\delta)\)-factor approximation on \(\mathcal G_{\Delta,\Delta}\) is possible in time \(\exp(cn)\operatorname{poly}(n,1/\delta)\). (b) Under the Gap-Exponential Time Hypothesis, there exists no deterministic algorithm running in time \(\exp(2cn)\operatorname{poly}(n)\) on \(\mathcal G_\Delta\) that gives an \(\frac{11}{10}\)-factor approximation.

(2) For every fixed \(\Delta\ge3\) and \(\varepsilon\in(0,1)\), for all sufficiently large fugacities \(\lambda\), the following hold: (a) There exists an algorithm which outputs a deterministic \((1+\varepsilon)^n\)-factor approximation to \(Z_G(\lambda)\) on \(\mathcal G_{\Delta,\Delta}\) in polynomial time. (b) Under the assumption \(\mathrm P\ne\mathrm{NP}\), there exists no deterministic polynomial-time algorithm on \(\mathcal G_\Delta\) that gives a \((1+\varepsilon)^n\)-factor approximation.

Both our algorithmic results follow from a new spanning-tree encoding of independent sets that enables an efficient representation of large independent sets.

@article{Narang2026bisIsSeparations,
  title = {Separations between {$\#\mathrm{BIS}$} and {$\#\mathrm{IS}$}},
  author = {Narang, Ijay},
  journal = {arXiv preprint arXiv:2610.38164},
  year = {2026}
}

We study approximate counting and sampling algorithms for the hard-core model on \(\Delta\)-regular bipartite graphs under a spectral expansion condition. Let \(M_G\) be the biadjacency matrix of \(G\). For every fixed \(\xi\in(0,1)\), we give an FPRAS for the hard-core partition function and an efficient approximate sampler whenever \(\lambda\leq \frac{1-\xi}{\sigma_2(M_G)}\). The main idea is to introduce a family of quadratic tilts in the left-right occupation imbalance and show that each tilted measure can be sampled efficiently using Glauber dynamics. A discrete Gaussian identity expresses the original hard-core model as an exact positive mixture of these tilted measures; truncation and simulated annealing then yield efficient counting and sampling algorithms. For the complementary high-fugacity regime, we refine the polymer-model approach and show that the required phase-dominance and cluster expansion conditions follow from the singular-spectrum bound alone. Combining the two regimes, we obtain efficient approximate counting and sampling at every fugacity \(\lambda>0\) whenever \(\sigma_2(M_G)\leq c\left(\frac{\Delta^2}{\log(\mathrm e\Delta)}\right)^{1/3}\) for an absolute constant \(c>0\). In particular, this recovers all-fugacity algorithms for random \(\Delta\)-regular bipartite graphs for all sufficiently large \(\Delta\), while providing an efficiently verifiable certificate of their success on a given instance.

@article{NarangPerkins2026hardCoreSpectralExpanders,
  title = {The Hard-Core Model on Bipartite Spectral Expanders: Counting and Sampling at All Fugacities},
  author = {Narang, Ijay and Perkins, Will},
  journal = {arXiv preprint arXiv:2608.03848},
  year = {2026}
}

We give a randomized polynomial-time algorithm that, for every fixed \(\varepsilon > 0\), colors every \(3\)-colorable \(n\)-vertex graph using \(O\bigl(n^{(13-\sqrt{97})/18+\varepsilon}\bigr) \approx O\bigl(n^{0.17506+\varepsilon}\bigr)\) colors, improving upon the previous best bound of \(O(n^{0.19539})\) from Bansal, Huang, and Lee. Our improvement comes from analyzing higher-level neighborhoods through a recursive description of failure in Gaussian SDP rounding. If the rounding returns too small an independent set, it produces local Gaussian certificates at every vertex of a nonempty induced subgraph. We propagate these certificates along walks to higher-level neighborhoods by defining a recursive certificate structure and proving a strengthened cover-composition lemma, which refines the one of Arora, Chlamtáč, and Charikar. We then construct a bounded potential function that increases by a fixed positive amount at every propagation step, yielding a contradiction. Consequently, the rounding must produce a sufficiently large independent set.

@article{NarangTang2026improvedSDPColoring,
  title = {Improved {SDP} Coloring of 3-Colorable Graphs from Recursive Gaussian Certificates},
  author = {Narang, Ijay and Tang, Yukai},
  journal = {arXiv preprint arXiv:2609.33684},
  year = {2026}
}

We show that unless P = NP, there cannot be a polynomial-time (or even pseudo-polynomial-time) algorithm for output feedback stabilization of a linear dynamical system with a linear controller. This settles one of the best-known open problems in control theory. The result holds in both continuous and discrete time. We also present a family of stabilizable linear dynamical systems for which no polynomial-time algorithm can write down a stabilizing controller in its standard representation.

@article{AhmadiChaudhryNarangTang2026outputFeedback,
  title = {Complexity Of Output Feedback Stabilization},
  author = {Ahmadi, Amir Ali and Chaudhry, Abraar and Narang, Ijay and Tang, Yukai},
  journal = {arXiv preprint arXiv:2609.20636},
  year = {2026}
}

We introduce a robust OR polynomial framework for composing positive semidefinite certificates across OR constraints. We demonstrate the power of this method in two applications. The first is on acute-free families. A set \(\mathcal F=\{(x_i^{(1)},\ldots,x_i^{(r)})\}_{i=1}^M \subseteq (S^{n-1})^r\) is \(r\)-way acute-free if, for every \(i\neq j\), there is a coordinate \(t\in[r]\) such that \(\langle x_i^{(t)},x_j^{(t)}\rangle\leq 0\). We write \(M_r(n)\) for the maximum size of such a set, and \(M_r^{\pm}(n)\) for the hypercube restriction. On the hypercube, \(r\)-way acute-free sets are independent sets for some strong power graph \(G_n^{\boxtimes r}\). The Lovász theta number \(\vartheta(G_n)\) is multiplicative but exponentially loose, whereas the Schrijver number \(\vartheta'(G_n)\) gives the correct order, but is not multiplicative. We bypass this obstruction by proving a general quasi-tensorization result for the Schrijver number. That is, for every collection of graphs \(G_1,\ldots,G_r\) satisfying \(\vartheta'(G_i)\geq 2\), there is an absolute constant \(C\) such that \(\vartheta'(G_1\boxtimes\cdots\boxtimes G_r)\leq\prod_{i=1}^r\vartheta'(G_i)^{C\log r\log\vartheta'(G_i)}\). Applying this result gives that \(M_r^{\pm}(n)\leq M_r(n)\leq(2n)^{C_0r\log r\log(2n)}\) for some absolute constant \(C_0\). The second application is on multicolor Ramsey numbers. The \(r\)-color Ramsey number \(R_r(k)\) is the minimum \(n\) such that every \(r\)-coloring of the edges of the complete graph on \(n\) vertices contains a monochromatic copy of \(K_k\). In a breakthrough result, Balister et al. showed that \(R_r(k)\leq\exp(-\Omega(k/r^{12}))r^{rk}\) via a geometric lemma. By improving the \(r\) dependency in their geometric lemma via the OR polynomial framework, we prove that \(R_r(k)\leq\exp(-\Omega(k/(r^9(\log r)^6)))r^{rk}\).

@article{NarangTang2026schrijverQuasiTensorization,
  title = {Schrijver Number Quasi-Tensorization and Multicolor Ramsey Bounds via Robust {OR} Polynomials},
  author = {Narang, Ijay and Tang, Yukai},
  journal = {arXiv preprint arXiv:2607.25023},
  year = {2026}
}

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}
}

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}
}

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}
}