16 citations · 77 across the 28 of their papers we have counts for
20 papers · 1 filter
Gap-free Differentially Private PCA for Gaussian Data
Alina Ene, Huy L. Nguyen
We give a gap-free -differentially private algorithm for the principal component analysis (PCA) problem with Gaussian data. The algorithm is based on a private variant of th…
Efficient Algorithms for Influence Maximization in General Models and Observed Cascades
Fabian Spaeh, Themistoklis Haris, Alina Ene +1
We study influence maximization in general stochastic models, the observed cascades model, and the independent cascade (IC) model. For general stochastic models with only black-box…
Solving Positive Linear Programs with Differential Privacy
Alina Ene, Huy Le Nguyen, Ta Duy Nguyen +1
We study differentially private approximation algorithms for positive linear programs (LPs with nonnegative coefficients and variables), focusing on the fundamental families of pac…
Adaptive Power Iteration Method for Differentially Private PCA
Ta Duy Nguyen, Alina Ene, Huy Le Nguyen
We study -differentially private algorithms for the problem of approximately computing the top singular vector of a matrix where each…
Improved Regression via Iteratively Reweighted Least Squares
Alina Ene, Ta Duy Nguyen, Adrian Vladu
We introduce fast algorithms for solving regression problems using the iteratively reweighted least squares (IRLS) method. Our approach achieves state-of-the-art iterati…
Solving Linear Programs with Differential Privacy
Alina Ene, Huy Le Nguyen, Ta Duy Nguyen +1
We study the problem of solving linear programs of the form , with differential privacy. For homogeneous LPs , we give an efficient -differentially…
Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures
Alina Ene, Alessandro Epasto, Vahab Mirrokni +4
In the maximum coverage problem we are given subsets from a universe , and the goal is to output subsets such that their union covers the largest possible number of di…
Multiplicative Weights Update, Area Convexity and Random Coordinate Descent for Densest Subgraph Problems
Ta Duy Nguyen, Alina Ene
We study the densest subgraph problem and give algorithms via multiplicative weights update and area convexity that converge in and $O\left(\fr…
Online and Streaming Algorithms for Constrained -Submodular Maximization
Fabian Spaeh, Alina Ene, Huy L. Nguyen
Constrained -submodular maximization is a general framework that captures many discrete optimization problems such as ad allocation, influence maximization, personalized recomme…
Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints
Naor Alaluf, Alina Ene, Moran Feldman +2
We study the problem of maximizing a non-monotone submodular function subject to a cardinality constraint in the streaming model. Our main contribution is a single-pass (semi-)stre…
Parallel Algorithm for Non-Monotone DR-Submodular Maximization
Alina Ene, Huy L. Nguyen
In this work, we give a new parallel algorithm for the problem of maximizing a non-monotone diminishing returns submodular function subject to a cardinality constraint. For any des…
Improved Convergence for and Regression via Iteratively Reweighted Least Squares
Alina Ene, Adrian Vladu
The iteratively reweighted least squares method (IRLS) is a popular technique used in practice for solving regression problems. Various versions of this method have been proposed,…
A Parallel Double Greedy Algorithm for Submodular Maximization
Alina Ene, Huy L. Nguyen, Adrian Vladu
We study parallel algorithms for the problem of maximizing a non-negative submodular function. Our main result is an algorithm that achieves a nearly-optimal approximation…
Towards Nearly-linear Time Algorithms for Submodular Maximization with a Matroid Constraint
Alina Ene, Huy L. Nguyen
We consider fast algorithms for monotone submodular maximization subject to a matroid constraint. We assume that the matroid is given as input in an explicit form, and the goal is…
Submodular Maximization with Matroid and Packing Constraints in Parallel
Alina Ene, Huy L. Nguyen, Adrian Vladu
We consider the problem of maximizing the multilinear extension of a submodular function subject a single matroid constraint or multiple packing constraints with a small number of…
Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
Alina Ene, Huy L. Nguyen
In this paper, we study the tradeoff between the approximation guarantee and adaptivity for the problem of maximizing a monotone submodular function subject to a cardinality constr…
A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
Alina Ene, Huy L. Nguyen
We consider the problem of maximizing a monotone submodular function subject to a knapsack constraint. Our main contribution is an algorithm that achieves a nearly-optimal, $1 - 1/…
Constrained Submodular Maximization: Beyond 1/e
Alina Ene, Huy L. Nguyen
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 f…
A Reduction for Optimizing Lattice Submodular Functions with Diminishing Returns
Alina Ene, Huy L. Nguyen
A function is DR-submodular if it satisfies for all ${\bf x}\le {\bf…
A New Framework for Distributed Submodular Maximization
Rafael da Ponte Barbosa, Alina Ene, Huy L. Nguyen +1
A wide variety of problems in machine learning, including exemplar clustering, document summarization, and sensor placement, can be cast as constrained submodular maximization prob…