24 citations · 62 across the 5 of their papers we have counts for
7 papers
Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds
Santosh Vempala, John Wilmes
We study the complexity of training neural network models with one hidden nonlinear activation layer and an output weighted sum layer. We analyze Gradient Descent applied to learni…
On Counting Perfect Matchings in General Graphs
Daniel Štefankovič, Eric Vigoda, John Wilmes
Counting perfect matchings has played a central role in the theory of counting problems. The permanent, corresponding to bipartite graphs, was shown to be #P-complete to compute ex…
On the Complexity of Learning Neural Networks
Le Song, Santosh Vempala, John Wilmes +1
The stunning empirical successes of neural networks currently lack rigorous theoretical explanation. What form would such an explanation take, in the face of existing complexity-th…
Structure and automorphisms of primitive coherent configurations
Xiaorui Sun, John Wilmes
Coherent configurations (CCs) are highly regular colorings of the set of ordered pairs of a "vertex set"; each color represents a "constituent digraph." CCs arise in the study of p…
Asymptotic Delsarte cliques in distance-regular graphs
László Babai, John Wilmes
We give a new bound on the parameter (number of common neighbors of a pair of adjacent vertices) in a distance-regular graph , improving and generalizing bounds for strongly…
Minimal Free Resolutions of the -parking Function Ideal and the Toppling Ideal
Madhusudan Manjunath, Frank-Olaf Schreyer, John Wilmes
The -parking function ideal of a directed multigraph is a monomial ideal which encodes some of the combinatorial information of . It is an initial ideal of the topp…