7 papers
Structural Corrections to the Bethe Approximation of the Permanent
Ijay Narang, Will Perkins
We study deterministic approximation algorithms for the permanent of a nonnegative matrix through the Bethe permanent, an approximation computable in polynomial time. The tight ana…
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…
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 detect…
Constant-Stepsize Stochastic Approximation: Finite-Time Convergence, 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, yet the distribution of the iterates is typically intractable. Classical as…