# Huy L. Nguyen

## Contact Details

NameHuy L. Nguyen |
||

Affiliation |
||

Location |
||

## Pubs By Year |
||

## Pub CategoriesComputer Science - Data Structures and Algorithms (18) Computer Science - Learning (8) Mathematics - Analysis of PDEs (7) Physics - Mesoscopic Systems and Quantum Hall Effect (7) Mathematics - Differential Geometry (7) Mathematics - Information Theory (5) Computer Science - Information Theory (5) Computer Science - Artificial Intelligence (5) Computer Science - Computational Geometry (4) Mathematics - Probability (2) Physics - Physics and Society (2) Computer Science - Distributed; Parallel; and Cluster Computing (2) Physics - Materials Science (2) Computer Science - Computational Complexity (2) Mathematics - Numerical Analysis (2) Mathematics - Statistics (1) Computer Science - Architecture (1) Computer Science - Computation and Language (1) Statistics - Theory (1) Nonlinear Sciences - Adaptation and Self-Organizing Systems (1) Computer Science - Networking and Internet Architecture (1) Computer Science - Discrete Mathematics (1) Mathematics - Mathematical Physics (1) Computer Science - Computer Vision and Pattern Recognition (1) Computer Science - Information Retrieval (1) Statistics - Machine Learning (1) Computer Science - Databases (1) Computer Science - Multimedia (1) Mathematical Physics (1) Physics - Strongly Correlated Electrons (1) |

## Publications Authored By Huy L. Nguyen

We prove local well-posedness for the inviscid surface quasigeostrophic (SQG) equation in bounded domains of $\mathbb{R}^2$. When fractional Dirichlet Laplacian dissipation is added, global existence of strong solutions is obtained for small data for critical and supercritical cases. Global existence of strong solutions with arbitrary data is obtained in the subcritical cases. Read More

We prove the existence of global $L^2$ weak solutions for a family of generalized inviscid surface-quasi geostrophic (SQG) equations in bounded domains of the plane. In these equations, the active scalar is transported by a velocity field which is determined by the scalar through a more singular nonlocal operator compared to the SQG equation. The result is obtained by establishing appropriate commutator representations for the weak formulation together with good bounds for them in bounded domains. Read More

In a previous article, we generalised the classical four-dimensional Chern-Gauss-Bonnet formula to a class of manifolds with finitely many conformally flat ends and singular points, in particular obtaining the first such formula in a dimension higher than two which allows the underlying manifold to have isolated conical singularities. In the present article, we extend this result to all even dimensions $n\geq 4$ in the case of a class of conformally flat manifolds. Read More

This paper presents a study of employing Ranking SVM and Convolutional Neural Network for two missions: legal information retrieval and question answering in the Competition on Legal Information Extraction/Entailment. For the first task, our proposed model used a triple of features (LSI, Manhattan, Jaccard), and is based on paragraph level instead of article level as in previous studies. In fact, each single-paragraph article corresponds to a particular paragraph in a huge multiple-paragraph article. Read More

This paper investigates connections between discrete and continuous approaches for decomposable submodular function minimization. We provide improved running time estimates for the state-of-the-art continuous algorithms for the problem using combinatorial arguments. We also provide a systematic experimental comparison of the two types of methods, based on a clear distinction between level-0 and level-1 algorithms. Read More

We prove existence of global weak $L^2$ solutions of the inviscid SQG equation in bounded domains. Read More

We present a novel architecture for sparse pattern processing, using flash storage with embedded accelerators. Sparse pattern processing on large data sets is the essence of applications such as document search, natural language processing, bioinformatics, subgraph matching, machine learning, and graph processing. One slice of our prototype accelerator is capable of handling up to 1TB of data, and experiments show that it can outperform C/C++ software solutions on a 16-core system at a fraction of the power and cost; an optimized version of the accelerator can match the performance of a 48-core server. Read More

In this paper we study the extraction of representative elements in the data stream model in the form of submodular maximization. Different from the previous work on streaming submodular maximization, we are interested only in the recent data, and study the maximization problem over sliding windows. We provide a general reduction from the sliding window model to the standard streaming model, and thus our approach works for general constraints as long as there is a corresponding streaming algorithm in the standard streaming model. Read More

In this work, we present a new algorithm for maximizing a non-monotone submodular function subject to a general constraint. Our algorithm finds an approximate fractional solution for maximizing the multilinear extension of the function over a down-closed polytope. The approximation guarantee is 0. Read More

The convergence of the restarted GMRES method can be significantly improved, for some problems, by using a weighted inner product that changes at each restart. How does this weighting affect convergence, and when is it useful? We show that weighted inner products can help in two distinct ways: when the coefficient matrix has localized eigenvectors, weighting can allow restarted GMRES to focus on eigenvalues that otherwise slow convergence; for general problems, weighting can break the cyclic convergence pattern into which restarted GMRES often settles. The eigenvectors of matrices derived from differential equations are often not localized, thus limiting the impact of weighting. Read More

A function $f: \mathbb{Z}_+^E \rightarrow \mathbb{R}_+$ is DR-submodular if it satisfies $f(\bx + \chi_i) -f (\bx) \ge f(\by + \chi_i) - f(\by)$ for all $\bx\le \by, i\in E$. Recently, the problem of maximizing a DR-submodular function $f: \mathbb{Z}_+^E \rightarrow \mathbb{R}_+$ subject to a budget constraint $\|\bx\|_1 \leq B$ as well as additional constraints has received significant attention \cite{SKIK14,SY15,MYK15,SY16}. In this note, we give a generic reduction from the DR-submodular setting to the submodular setting. Read More

Zhang et al. reported in [Phys. Rev. Read More

We prove that codimension two surfaces satisfying a nonlinear curvature condition depending on normal curvature are smoothly deformed by mean curvature flow to round points. Read More

We propose a novel hashing-based matching scheme, called Locally Optimized Hashing (LOH), based on a state-of-the-art quantization algorithm that can be used for efficient, large-scale search, recommendation, clustering, and deduplication. We show that matching with LOH only requires set intersections and summations to compute and so is easily implemented in generic distributed computing systems. We further show application of LOH to: a) large-scale search tasks where performance is on par with other state-of-the-art hashing approaches; b) large-scale recommendation where queries consisting of thousands of images can be used to generate accurate recommendations from collections of hundreds of millions of images; and c) efficient clustering with a graph-based algorithm that can be scaled to massive collections in a distributed environment or can be used for deduplication for small collections, like search results, performing better than traditional hashing approaches while only requiring a few milliseconds to run. Read More

In turnstile $\ell_p$ $\varepsilon$-heavy hitters, one maintains a high-dimensional $x\in\mathbb{R}^n$ subject to $\texttt{update}(i,\Delta)$ causing $x_i\leftarrow x_i + \Delta$, where $i\in[n]$, $\Delta\in\mathbb{R}$. Upon receiving a query, the goal is to report a small list $L\subset[n]$, $|L| = O(1/\varepsilon^p)$, containing every "heavy hitter" $i\in[n]$ with $|x_i| \ge \varepsilon \|x_{\overline{1/\varepsilon^p}}\|_p$, where $x_{\overline{k}}$ denotes the vector obtained by zeroing out the largest $k$ entries of $x$ in magnitude. For any $p\in(0,2]$ the CountSketch solves $\ell_p$ heavy hitters using $O(\varepsilon^{-p}\log n)$ words of space with $O(\log n)$ update time, $O(n\log n)$ query time to output $L$, and whose output after any query is correct with high probability (whp) $1 - 1/poly(n)$. Read More

A wide variety of problems in machine learning, including exemplar clustering, document summarization, and sensor placement, can be cast as constrained submodular maximization problems. A lot of recent effort has been devoted to developing distributed algorithms for these problems. However, these results suffer from high number of rounds, suboptimal approximation ratios, or both. Read More

We study the tradeoff between the statistical error and communication cost of distributed statistical estimation problems in high dimensions. In the distributed sparse Gaussian mean estimation problem, each of the $m$ machines receives $n$ data points from a $d$-dimensional Gaussian distribution with unknown mean $\theta$ which is promised to be $k$-sparse. The machines communicate by message passing and aim to estimate the mean $\theta$. Read More

In this work, we investigate the possibility of enhancing the thermoelectric power (Seebeck coefficient) in graphene devices by strain and doping engineering. While a local strain can result in the misalignment of Dirac cones of different graphene sections in the k-space, doping engineering leads to their displacement in energy. By combining these two effects, we demonstrate that a conduction gap as large as a few hundreds meV can be achieved and hence the enhanced Seebeck coefficient can reach a value higher than 1. Read More

We generalise the classical Chern-Gauss-Bonnet formula to a class of 4-dimensional manifolds with finitely many conformally flat ends and singular points. This extends results of Chen-Qing-Yang in the smooth case. Under the assumptions of finite total Q curvature and positive scalar curvature at the ends and at the singularities, we obtain a new Chern-Gauss-Bonnet formula with error terms that can be expressed as isoperimetric deficits. Read More

A wide variety of problems in machine learning, including exemplar clustering, document summarization, and sensor placement, can be cast as constrained submodular maximization problems. Unfortunately, the resulting submodular optimization problems are often too large to be solved on a single machine. We develop a simple distributed algorithm that is embarrassingly parallel and it achieves provable, constant factor, worst-case approximation guarantees. Read More

Submodular function minimization is a fundamental optimization problem that arises in several applications in machine learning and computer vision. The problem is known to be solvable in polynomial time, but general purpose algorithms have high running times and are unsuitable for large-scale problems. Recent work have used convex optimization techniques to obtain very practical algorithms for minimizing functions that are sums of ``simple" functions. Read More

The goal of the present paper is to investigate the algebraic structure of global conformal invariants of submanifolds. These are defined to be conformally invariant integrals of geometric scalars of the tangent and normal bundle. A famous example of a global conformal invariant is the Willmore energy of a surface. Read More

We investigate the electron-transport properties of ethyne-bridged diphenyl zinc-porphyrin molecules suspended between gold (111) electrodes by first-principles calculations within the framework of density functional theory. It is found that the conductance of a molecular junction in which phenyl and porphyrin rings are perpendicular is reduced by three orders of magnitude compared with that of a junction in which the phenyl and porphyrin rings are coplanar. In the coplanar configuration, electrons are transmitted through $\pi$ states, which extend over the whole molecule. Read More

We investigate the effects of uniaxial strain on the transport properties of vertical devices made of two twisted graphene layers, which partially overlap each other. We find that because of the different orientations of the two graphene lattices, their Dirac points can be displaced and separated in the $k-$space by the effects of strain. Hence, a finite conduction gap as large as a few hundred meV can be obtained in the device with a small strain of only a few percent. Read More

Let $k$ be a nonnegative integer. In the approximate $k$-flat nearest neighbor ($k$-ANN) problem, we are given a set $P \subset \mathbb{R}^d$ of $n$ points in $d$-dimensional space and a fixed approximation factor $c > 1$. Our goal is to preprocess $P$ so that we can efficiently answer approximate $k$-flat nearest neighbor queries: given a $k$-flat $F$, find a point in $P$ whose distance to $F$ is within a factor $c$ of the distance between $F$ and the closest point in $P$. Read More

We study a weighted online bipartite matching problem: $G(V_1, V_2, E)$ is a weighted bipartite graph where $V_1$ is known beforehand and the vertices of $V_2$ arrive online. The goal is to match vertices of $V_2$ as they arrive to vertices in $V_1$, so as to maximize the sum of weights of edges in the matching. If assignments to $V_1$ cannot be changed, no bounded competitive ratio is achievable. Read More

In this work, we investigate thermoelectric properties of junctions consisting of two partially overlapped graphene sheets coupled to each other in the cross-plane direction. It is shown that because of the weak van-der Waals interactions between graphene layers, the phonon conductance in these junctions is strongly reduced, compared to that of single graphene layer structures, while their electrical performance is weakly affected. By exploiting this effect, we demonstrate that the thermoelectric figure of merit can reach values higher than 1 at room temperature in junctions made of gapped graphene materials, for instance, graphene nanoribbons and graphene nanomeshes. Read More

In this paper, we rigorously investigate the truncation method for the Cauchy problem of Helmholtz equations which is widely used to model propagation phenomena in physical applications. The method is a well-known approach to the regularization of several types of ill-posed problems, including the model postulated by Regi\' nska and Regi\' nski \cite{RR06}. Under certain specific assumptions, we examine the ill-posedness of the non-homogeneous problem by exploring the representation of solutions based on Fourier mode. Read More

We describe CPMC-Lab, a Matlab program for the constrained-path and phaseless auxiliary-field Monte Carlo methods. These methods have allowed applications ranging from the study of strongly correlated models, such as the Hubbard model, to ab initio calculations in molecules and solids. The present package implements the full ground-state constrained-path Monte Carlo (CPMC) method in Matlab with a graphical interface, using the Hubbard model as an example. Read More

We say a turnstile streaming algorithm is "non-adaptive" if, during updates, the memory cells written and read depend only on the index being updated and random coins tossed at the beginning of the stream (and not on the memory contents of the algorithm). Memory cells read during queries may be decided upon adaptively. All known turnstile streaming algorithms in the literature are non-adaptive. Read More

In this paper we prove several quantitative rigidity results for conformal immersions of surfaces in $\mathbb{R}^n$ with bounded total curvature. We show that (branched) conformal immersions which are close in energy to either a round sphere, a conformal Clifford torus, an inverted catenoid, an inverted Enneper's minimal surface or an inverted Chen's minimal graph must be close to these surfaces in the $W^{2,2}$-norm. Moreover, we apply these results to prove a corresponding rigidity result for complete, connected and non-compact surfaces. Read More

We explore the connection between dimensionality and communication cost in distributed learning problems. Specifically we study the problem of estimating the mean $\vec{\theta}$ of an unknown $d$ dimensional gaussian distribution in the distributed setting. In this problem, the samples from the unknown distribution are distributed among $m$ different machines. Read More

It has been shown in a recent study [Nguyen et al., Nanotechnol. \textbf{25}, 165201 (2014)] that unstrained/strained graphene junctions are promising candidates to improve the performance of graphene transistors that is usually hindered by the gapless nature of graphene. Read More

By means of numerical simulation, we study in this work the effects of uniaxial strain on transport properties of strained graphene heterojunctions and explore the possibility to achieve good performance of graphene transistors using these hetero-channels. It is shown that a finite conduction-gap can open in the strain junctions due to the strain-induced deformation of graphene bandstructure. These hetero-channels are then demonstrated to improve significantly the operation of graphene field-effect-transistors (FETs). Read More

In 1965 Willmore conjectured that the integral of the square of the mean curvature of a torus immersed in $R^3$ is at least $2\pi^2$ and attains this minimal value if and only if the torus is a M\"obius transform of the Clifford torus. This was recently proved by Marques and Neves. In this paper, we show for tori there is a gap to the next critical point of the Willmore energy and we discuss an application to the Willmore flow. Read More

An oblivious subspace embedding (OSE) for some eps, delta in (0,1/3) and d <= m <= n is a distribution D over R^{m x n} such that for any linear subspace W of R^n of dimension d, Pr_{Pi ~ D}(for all x in W, (1-eps) |x|_2 <= |Pi x|_2 <= (1+eps)|x|_2) >= 1 - delta. We prove that any OSE with delta < 1/3 must have m = Omega((d + log(1/delta))/eps^2), which is optimal. Furthermore, if every Pi in the support of D is sparse, having at most s non-zero entries per column, then we show tradeoff lower bounds between m and s. Read More

This paper presents a quantitative study of Twitter, one of the most popular micro-blogging services, from the perspective of user influence. We crawl several datasets from the most active communities on Twitter and obtain 20.5 million user profiles, along with 420. Read More

The problem of estimating frequency moments of a data stream has attracted a lot of attention since the onset of streaming algorithms [AMS99]. While the space complexity for approximately computing the $p^{\rm th}$ moment, for $p\in(0,2]$ has been settled [KNW10], for $p>2$ the exact complexity remains open. For $p>2$ the current best algorithm uses $O(n^{1-2/p}\log n)$ words of space [AKO11,BO10], whereas the lower bound is of $\Omega(n^{1-2/p})$ [BJKS04]. Read More

We present a new locality sensitive hashing (LSH) algorithm for $c$-approximate nearest neighbor search in $\ell_p$ with $1

Read More

We present a new data structure for the c-approximate near neighbor problem (ANN) in the Euclidean space. For n points in R^d, our algorithm achieves O(n^{\rho} + d log n) query time and O(n^{1 + \rho} + d log n) space, where \rho <= 7/(8c^2) + O(1 / c^3) + o(1). This is the first improvement over the result by Andoni and Indyk (FOCS 2006) and the first data structure that bypasses a locality-sensitive hashing lower bound proved by O'Donnell, Wu and Zhou (ICS 2011). Read More

Our main result is that the Steiner Point Removal (SPR) problem can always be solved with polylogarithmic distortion, which answers in the affirmative a question posed by Chan, Xia, Konjevod, and Richa (2006). Specifically, we prove that for every edge-weighted graph $G = (V,E,w)$ and a subset of terminals $T \subseteq V$, there is a graph $G'=(T,E',w')$ that is isomorphic to a minor of $G$, such that for every two terminals $u,v\in T$, the shortest-path distances between them in $G$ and in $G'$ satisfy $d_{G,w}(u,v) \le d_{G',w'}(u,v) \le O(\log^5|T|) \cdot d_{G,w}(u,v)$. Our existence proof actually gives a randomized polynomial-time algorithm. Read More

Passive monitoring utilizing distributed wireless sniffers is an effective technique to monitor activities in wireless infrastructure networks for fault diagnosis, resource management and critical path analysis. In this paper, we introduce a quality of monitoring (QoM) metric defined by the expected number of active users monitored, and investigate the problem of maximizing QoM by judiciously assigning sniffers to channels based on the knowledge of user activities in a multi-channel wireless network. Two types of capture models are considered. Read More

We study convergence of the following discrete-time non-linear dynamical system: n agents are located in R^d and at every time step, each moves synchronously to the average location of all agents within a unit distance of it. This popularly studied system was introduced by Krause to model the dynamics of opinion formation and is often referred to as the Hegselmann-Krause model. We prove the first polynomial time bound for the convergence of this system in arbitrary dimensions. Read More

We give near-tight lower bounds for the sparsity required in several dimensionality reducing linear maps. First, consider the JL lemma which states that for any set of n vectors in R there is a matrix A in R^{m x d} with m = O(eps^{-2}log n) such that mapping by A preserves pairwise Euclidean distances of these n vectors up to a 1 +/- eps factor. We show that there exists a set of n vectors such that any such matrix A with at most s non-zero entries per column must have s = Omega(eps^{-1}log n/log(1/eps)) as long as m < O(n/log(1/eps)). Read More

An "oblivious subspace embedding (OSE)" given some parameters eps,d is a distribution D over matrices B in R^{m x n} such that for any linear subspace W in R^n with dim(W) = d it holds that Pr_{B ~ D}(forall x in W ||B x||_2 in (1 +/- eps)||x||_2) > 2/3 We show an OSE exists with m = O(d^2/eps^2) and where every B in the support of D has exactly s=1 non-zero entries per column. This improves previously best known bound in [Clarkson-Woodruff, arXiv:1207.6365]. Read More

Using atomistic quantum simulation based on a tight binding model, we investigate the formation of energy gap Eg of graphene nanomesh (GNM) lattices and the transport characteristics of GNM-based electronic devices (single potential barrier structure and p-n junction) taking into account the atomic edge disorder of holes. We find that the sensitivity of Eg to the lattice symmetry (i.e. Read More

We study classic streaming and sparse recovery problems using deterministic linear sketches, including l1/l1 and linf/l1 sparse recovery problems (the latter also being known as l1-heavy hitters), norm estimation, and approximate inner product. We focus on devising a fixed matrix A in R^{m x n} and a deterministic recovery/estimation procedure which work for all possible input vectors simultaneously. Our results improve upon existing work, the following being our main contributions: * A proof that linf/l1 sparse recovery and inner product estimation are equivalent, and that incoherent matrices can be used to solve both problems. Read More

Given a budget and arbitrary cost for selecting each node, the budgeted influence maximization (BIM) problem concerns selecting a set of seed nodes to disseminate some information that maximizes the total number of nodes influenced (termed as influence spread) in social networks at a total cost no more than the budget. Our proposed seed selection algorithm for the BIM problem guarantees an approximation ratio of (1 - 1/sqrt(e)). The seed selection algorithm needs to calculate the influence spread of candidate seed sets, which is known to be #P-complex. Read More

In this paper we classify branched Willmore spheres with at most three branch points (including multiplicity), showing that they may be obtained from complete minimal surfaces in $\R ^ 3$ with ends of multiplicity at most three. This extends the classification result of Bryant. We then show that this may be applied to the analysis of singularities of the Willmore flow of non-Willmore spheres with Willmore energy $ \mc {W} (f) \leq 16\pi$. Read More

Partitioning oracles were introduced by Hassidim et al. (FOCS 2009) as a generic tool for constant-time algorithms. For any epsilon > 0, a partitioning oracle provides query access to a fixed partition of the input bounded-degree minor-free graph, in which every component has size poly(1/epsilon), and the number of edges removed is at most epsilon*n, where n is the number of vertices in the graph. Read More