25 citations · 70 across the 30 of their papers we have counts for
9 papers · 1 filter
Towards the linear arboricity conjecture
Asaf Ferber, Jacob Fox, Vishesh Jain
The linear arboricity of a graph , denoted by , is the minimum number of edge-disjoint linear forests (i.e. forests in which every connected component is a path) i…
Singularity of random symmetric matrices -- a combinatorial approach to improved bounds
Asaf Ferber, Vishesh Jain
Let denote a random symmetric matrix whose upper diagonal entries are independent and identically distributed Bernoulli random variables (which take values a…
Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective
Vishesh Jain, Frederic Koehler, Andrej Risteski
The free energy is a key quantity of interest in Ising models, but unfortunately, computing it in general is computationally intractable. Two popular (variational) approximation sc…
On the number of Hadamard matrices via anti-concentration
Asaf Ferber, Vishesh Jain, Yufei Zhao
Many problems in combinatorial linear algebra require upper bounds on the number of solutions to an underdetermined system of linear equations , where the coordinates of th…
On the k-planar local crossing number
John Asplund, Thao do, Arran Hamm +1
Given a fixed positive integer , the -planar local crossing number of a graph , denoted by , is the minimum positive integer such that can be deco…
1-factorizations of pseudorandom graphs
Asaf Ferber, Vishesh Jain
A -factorization of a graph is a collection of edge-disjoint perfect matchings whose union is . A trivial necessary condition for to admit a -factorization is t…
Number of 1-factorizations of regular high-degree graphs
Asaf Ferber, Vishesh Jain, Benny Sudakov
A -factor in an -vertex graph is a collection of vertex-disjoint edges and a -factorization of is a partition of its edges into edge-disjoint -fac…
The Vertex Sample Complexity of Free Energy is Polynomial
Vishesh Jain, Frederic Koehler, Elchanan Mossel
We study the following question: given a massive Markov random field on nodes, can a small sample from it provide a rough approximation to the free energy $\mathcal{F}_n = \log…
The Mean-Field Approximation: Information Inequalities, Algorithms, and Complexity
Vishesh Jain, Frederic Koehler, Elchanan Mossel
The mean field approximation to the Ising model is a canonical variational tool that is used for analysis and inference in Ising models. We provide a simple and optimal bound for t…