Source author record

Huy Tuan Pham

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.PR Data Structures and Algorithms math.NT Discrete Mathematics Machine Learning math.OC math.ST Statistics Theory

Catalog footprint

Research overview

7works

9topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2024arXiv

A multipartite analogue of Dilworth's Theorem

We prove that every partially ordered set on $n$ elements contains $k$ subsets $A_{1},A_{2},\dots,A_{k}$ such that either each of these subsets has size $Ω(n/k^{5})$ and, for every $i<j$ , every element in $A_{i}$ is less than or equal to every element in $A_{j}$ , or each of these subsets has size $Ω(n/(k^{2}\log n))$ and, for every $i \not = j$ , every element in $A_{i}$ is incomparable with every element in $A_{j}$ for $i\ne j$ . This answers a question of the first author from 2006. As a corollary, we prove for each positive integer $h$ there is $C_h$ such that for any $h$ partial orders $<_{1},<_{2},\dots,<_{h}$ on a set of $n$ elements, there exists $k$ subsets $A_{1},A_{2},\dots,A_{k}$ each of size at least $n/(k\log n)^{C_{h}}$ such that for each partial order $<_{\ell}$ , either $a_{1}<_{\ell}a_{2}<_{\ell}\dots<_{\ell}a_{k}$ for any tuple of elements $(a_1,a_2,\dots,a_k) \in A_1\times A_2\times \dots \times A_k$ , or $a_{1}>_{\ell}a_{2}>_{\ell}\dots>_{\ell}a_{k}$ for any $(a_1,a_2,\dots,a_k) \in A_1\times A_2\times \dots \times A_k$ , or $a_i$ is incomparable with $a_j$ for any $i\ne j$ , $a_i\in A_i$ and $a_j\in A_j$ . This improves on a 2009 result of Pach and the first author motivated by problems in discrete geometry.

preprint2022arXiv

Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain

Let $G = (V,E)$ be an undirected graph with maximum degree $Δ$ and vertex conductance $Ψ^*(G)$ . We show that there exists a symmetric, stochastic matrix $P$ , with off-diagonal entries supported on $E$ , whose spectral gap $γ^*(P)$ satisfies $Ψ^*(G)^{2}/\logΔ\lesssim γ^*(P) \lesssim Ψ^*(G).$ Our bound is optimal under the Small Set Expansion Hypothesis, and answers a question of Olesker-Taylor and Zanetti, who obtained such a result with $\logΔ$ replaced by $\log|V|$ . In order to obtain our result, we show how to embed a negative-type semi-metric $d$ defined on $V$ into a negative-type semi-metric $d'$ supported in $\mathbb{R}^{O(\logΔ)}$ , such that the (fractional) matching number of the weighted graph $(V,E,d)$ is approximately equal to that of $(V,E,d')$ .

preprint2022arXiv

On random irregular subgraphs

Let $G$ be a $d$ -regular graph on $n$ vertices. Frieze, Gould, Karoński and Pfender began the study of the following random spanning subgraph model $H=H(G)$ . Assign independently to each vertex $v$ of $G$ a uniform random number $x(v) \in [0,1]$ , and an edge $(u,v)$ of $G$ is an edge of $H$ if and only if $x(u)+x(v) \geq 1$ . Addressing a problem of Alon and Wei, we prove that if $d = o(n/(\log n)^{12})$ , then with high probability, for each nonnegative integer $k \leq d$ , there are $(1+o(1))n/(d+1)$ vertices of degree $k$ in $H$ .

preprint2022arXiv

Universality for low degree factors of random polynomials over finite fields

We show that the counts of low degree irreducible factors of a random polynomial $f$ over $\mathbb{F}_q$ with independent but non-uniform coefficients behave like that of a uniform random polynomial, exhibiting a form of universality for random polynomials over finite fields. Our strongest results require various assumptions on the parameters, but we are able to obtain results requiring only $q=p$ a prime with $p\leq \exp({n^{1/13}})$ where $n$ is the degree of the polynomial. Our proofs use Fourier analysis, and rely on tools recently applied by Breuillard and Varjú to study the $ax+b$ process, which show equidistribution for $f(α)$ at a single point. We extend this to handle multiple roots and the Hasse derivatives of $f$ , which allow us to study the irreducible factors with multiplicity.

preprint2021arXiv

On the sampling Lovász Local Lemma for atomic constraint satisfaction problems

We study the problem of sampling an approximately uniformly random satisfying assignment for atomic constraint satisfaction problems i.e. where each constraint is violated by only one assignment to its variables. Let $p$ denote the maximum probability of violation of any constraint and let $Δ$ denote the maximum degree of the line graph of the constraints. Our main result is a nearly-linear (in the number of variables) time algorithm for this problem, which is valid in a Lovász local lemma type regime that is considerably less restrictive compared to previous works. In particular, we provide sampling algorithms for the uniform distribution on: (1) $q$ -colorings of $k$ -uniform hypergraphs with $Δ\lesssim q^{(k-4)/3 + o_{q}(1)}.$ The exponent $1/3$ improves the previously best-known $1/7$ in the case $q, Δ= O(1)$ [Jain, Pham, Vuong; arXiv, 2020] and $1/9$ in the general case [Feng, He, Yin; STOC 2021]. (2) Satisfying assignments of Boolean $k$ -CNF formulas with $Δ\lesssim 2^{k/5.741}.$ The constant $5.741$ in the exponent improves the previously best-known $7$ in the case $k = O(1)$ [Jain, Pham, Vuong; arXiv, 2020] and $13$ in the general case [Feng, He, Yin; STOC 2021]. (3) Satisfying assignments of general atomic constraint satisfaction problems with $p\cdot Δ^{7.043} \lesssim 1.$ The constant $7.043$ improves upon the previously best-known constant of $350$ [Feng, He, Yin; STOC 2021]. At the heart of our analysis is a novel information-percolation type argument for showing the rapid mixing of the Glauber dynamics for a carefully constructed projection of the uniform distribution on satisfying assignments. Notably, there is no natural partial order on the space, and we believe that the techniques developed for the analysis may be of independent interest.

preprint2020arXiv

A Note on the Global Convergence of Multilayer Neural Networks in the Mean Field Regime

In a recent work, we introduced a rigorous framework to describe the mean field limit of the gradient-based learning dynamics of multilayer neural networks, based on the idea of a neuronal embedding. There we also proved a global convergence guarantee for three-layer (as well as two-layer) networks using this framework. In this companion note, we point out that the insights in our previous work can be readily extended to prove a global convergence guarantee for multilayer networks of any depths. Unlike our previous three-layer global convergence guarantee that assumes i.i.d. initializations, our present result applies to a type of correlated initialization. This initialization allows to, at any finite training time, propagate a certain universal approximation property through the depth of the neural network. To achieve this effect, we introduce a bidirectional diversity condition.

preprint2020arXiv

Tower-type bounds for Roth's theorem with popular differences

Green developed an arithmetic regularity lemma to prove a strengthening of Roth's theorem on arithmetic progressions in dense sets. It states that for every $ε> 0$ there is some $N_0(ε)$ such that for every $N \ge N_0(ε)$ and $A \subset [N]$ with $|A| = αN$ , there is some nonzero $d$ such that $A$ contains at least $(α^3 - ε) N$ three-term arithmetic progressions with common difference $d$ . We prove that the minimum $N_0(ε)$ in Green's theorem is an exponential tower of 2s of height on the order of $\log(1/ε)$ . Both the lower and upper bounds are new. It shows that the tower-type bounds that arise from the use of a regularity lemma in this application are quantitatively necessary.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Huy Tuan Pham

Research overview

Is this your work?

7 publications

A multipartite analogue of Dilworth's Theorem

Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain

On random irregular subgraphs

Universality for low degree factors of random polynomials over finite fields

On the sampling Lovász Local Lemma for atomic constraint satisfaction problems

A Note on the Global Convergence of Multilayer Neural Networks in the Mean Field Regime

Tower-type bounds for Roth's theorem with popular differences

See the researcher in context

Building this map preview