6 papers
The Hard-Core Model on Bipartite Spectral Expanders: Counting and Sampling at All Fugacities
Ijay Narang, Will Perkins
We study approximate counting and sampling algorithms for the hard-core model on -regular bipartite graphs under a spectral expansion condition. Let be the biadjacency mat…
Computational Thresholds for Balanced and Fixed-Slice Independent Sets in Bipartite Graphs
Ijay Narang, Will Perkins, Yuzhou Wang +1
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 decomposin…
Schrijver Number Quasi-Tensorization and Multicolor Ramsey Bounds via Robust OR Polynomials
Ijay Narang, Yukai Tang
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. T…
Sharp Inner Product Correlations for Hypercube Bijections
Ijay Narang, Muchen Ju
We resolve a conjecture of Rob Morris concerning bijections on the hypercube. Specifically, we show that for any bijection , \[ \Pr_{x,y \in \{-1,1\}…
Optimal detection of planted stars via a random energy model
Ijay Narang, Will Perkins, Timothy L. H. Wee
We study the problem of detecting a planted star in the Erd{Å}s--R{é}nyi random graph , formulated as a hypothesis test. We determine the scaling window for critical dete…
Steady-State Behavior of Constant-Stepsize Stochastic Approximation: Gaussian Approximation and Tail Bounds
Zedong Wang, Yuyang Wang, Ijay Narang +3
Constant-stepsize stochastic approximation (SA) is widely used in learning for computational efficiency. For a fixed stepsize, the iterates typically admit a stationary distributio…