Publications and Pre-prints:
Max Dabagia, Manuel Fernandez V. The smallest singular value of inhomogenous random rectangular matrices.
Description: In this paper we obtain lower tail estimates for the smallest singular value of random rectangular matrices with inhomogenous entries. Of particular note, we show that a tail estimate previously known for random matrices with i.i.d subgaussian entries holds for inhomogenous matrices whose entries have bounded 2+beta moments.
Manuel Fernandez V. A distance theorem for inhomogeneous random rectangular matrices.
Description: In this paper we obtain a small ball probability estimate for the distance between an inhomogenous random vector and a subspace spanned by an inhomogenous random rectangular matrix. An important ingredient in our proof is the new notion of Randomized Logarithmic Least Common Denominator, a quantity that captures the lack of arithmetic structure of the unit normals to such subspaces.
Manuel Fernandez V. On the $\ell_0$-isoperimetric coefficient of measurable sets. Submitted.
Description: In this paper we determine the order of the \ell_0 isoperimetric coefficient of a hypercube and a tight upper bound for the \ell_0 isoperimetric coefficient of any measurable set. Ingredients in our proofs include an isoperimetric inequality due to Lawrence Harper and a randomized construction for large subsets with small \ell_0 boundary.
Manuel Fernandez V, Lutz Warnke. The clique chromatic number of sparse random graphs. Submitted.
Description: In this paper we determine the the asymptotics for the typical value of the clique chromatic number of binomial random graphs G(n,p) for n^{-2/5 + o(1)} << p << 1. This resolves a problem of Lichev, Mitsche, and Warnke and a conjecture of Alon and Krivelevich.
Manuel Fernandez V, David P. Woodruff, Taisuke Yasuda. The Query complexity of mastermind with $\ell_p$ distances. APPROX/RANDOM 2019, volume 145 of LIPIcs, pages 1:1-1:11
Description: In this paper we consider a generalization of the Mastermind game: Recovering a hidden vector in [k]^n from distance measurements between the hidden vector and queried vectors. We provide an algorithm with the optimal query complexity (up to leading constants) for \ell_p distances in the exact recovery case.
Manuel Fernandez V, David P. Woodruff, Taisuke Yasuda. Graph Spanners in the message-passing model. 11th Innovations in Theoretical Computer Science, volume 151 of LIPIcs, pages 77:1-77:18
Description: In this paper we analyze the communication complexity of computing a graph spanners in the message passing model, where edges are held in different sites and all sites communicate with a single coordinator. We provide communication efficient algorithms for multiplicative and additive graph spanners in both the with and without duplication version of the message passing model.
Manuel Fernandez V, David P. Woodruff, Taisuke Yasuda. Tight Kernel Query Complexity of Kernel Ridge Regression and Kernel. Proceedings of the 36th Internal Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 7055-7063
Description: In this paper we study the complexity of kernel k-means clustering and kernel k-ridge regression in terms of the minimum number of kernel samples needed to obtain an approximately optimal solution. We obtain nearly tight (up to logarithmic) lowerbounds on the query complexity in both cases.
Manuel Fernandez V, Nicholas Seiger, Michael Tait. Maximal Planar Subgraphs of Fixed Girth in Random Graphs. Electron. J. Comb., 25(2): P2.45, 2018.
Description: In this paper we determine, for every k >= 1 fixed, a logarithmic sized interval [p_{1,k},p_{2,k}] so that a binomial random graph G(n,p) contains a maximal planar subgraph of girth 2k-1 with high probability whenever p >> p_{2,k}, and doesn't contain such a subgraph when p << p_{1,k}. This generalizes a result of Frieze and Krivelevich, who proved such a result in the case where k = 2.
*Authors are listed in alphabetical order