19 citations · 57 across the 10 of their papers we have counts for
5 papers · 1 filter
High dimensional Hoffman bound and applications in extremal combinatorics
Yuval Filmus, Konstantin Golubev, Noam Lifshitz
One powerful method for upper-bounding the largest independent set in a graph is the Hoffman bound, which gives an upper bound on the largest independent set of a graph in terms of…
Graphical Designs and Extremal Combinatorics
Konstantin Golubev
A graphical design is a proper subset of vertices of a graph on which many eigenfunctions of the Laplacian operator have mean value zero. In this paper, we show that extremal indep…
On the support of a non-autocorrelated function on a hyperbolic surface
Konstantin Golubev
Let be a non-negative square-integrable function on a finite volume hyperbolic surface , and assume that is non-autocorrelated, that is, perpendicula…
Cutoff on Graphs and the Sarnak-Xue Density of Eigenvalues
Konstantin Golubev, Amitay Kamber
It was recently shown by Lubetzky and Peres (2016) and by Sardari (2018) that Ramanujan graphs, i.e., graphs with the optimal spectrum, exhibit cutoff of the simple random walk in…
Direct Sum Testing: The General Case
Irit Dinur, Konstantin Golubev
A function is a direct sum if it is of the form for some fu…