About

Alina Ene is an Associate Professor in the Department of Computer Science at Boston University. Her research interests include the design and analysis of algorithms, with a focus on the mathematical aspects of combinatorial optimization topics such as submodularity and graphs, and their applications to machine learning. Prior to her current position, she was an Assistant Professor at the University of Warwick, a Faculty Fellow at the Alan Turing Institute for Data Science, and completed a postdoctoral fellowship at the Center for Computational Intractability at Princeton University. Alina Ene obtained her PhD in Computer Science from the University of Illinois at Urbana-Champaign in 2013 under the supervision of Chandra Chekuri. She earned her BSE degree in Computer Science from Princeton University in 2008, graduating with High Honors. Her academic and research work has contributed to the development of new frameworks and algorithms in the field of submodular maximization, graph algorithms, and machine learning applications.

Research topics

• Computer Science
• Mathematical optimization
• Mathematics
• Artificial Intelligence
• Algorithm
• Machine Learning
• Discrete mathematics

Selected publications

• Solving Positive Linear Programs with Differential Privacy

  arXiv (Cornell University) · 2026-04-29

  preprintOpen access1st authorCorresponding

  We study differentially private approximation algorithms for positive linear programs (LPs with nonnegative coefficients and variables), focusing on the fundamental families of packing, covering, and mixed packing-covering formulations. We focus on the high-sensitivity, constraint-private regime of Hsu-Roth-Roughgarden-Ullman (ICALP 2014), where neighboring instances may differ by an arbitrary single constraint, so one cannot hope to approximately satisfy every constraint under privacy. We give private solvers that return approximate solutions while violating only a controlled number of constraints. Our algorithms improve the prior instance-dependent guarantees, and also yield new data-independent bounds that depend only on the dimension. Our techniques involve a dense multiplicative weights update method developed from a regularized dual viewpoint, which we analyze in a way that exploits structure specific to positive LPs.

  PublisherDOI

• Adaptive Power Iteration Method for Differentially Private PCA

  Open MIND · 2026-02-12

  preprint

  We study $\left(ε,δ\right)$-differentially private algorithms for the problem of approximately computing the top singular vector of a matrix $A\in\mathbb{R}^{n\times d}$ where each row of $A$ is a data point in $\mathbb{R}^{d}$. Following Dwork-Talwar-Thakurta-Zhang (STOC 2014), we consider the privacy model where neighboring inputs differ by one single row. We give a novel algorithm that achieves beyond-worst-case guarantees for input matrices with low coherence, which is a structural property of matrices in many applications, including but not limited to i.i.d. data. Our algorithm contributes to the extensive literature on private power iteration methods, where we introduce a new filtering technique which adapts to this coherence parameter. Our work departs from and complements the work by Hardt-Roth (STOC 2013) which achieves beyond-worst-case guarantees for the more restrictive privacy model where neighboring inputs differ in one single entry by at most 1.

  DOI

• Adaptive Power Iteration Method for Differentially Private PCA

  ArXiv.org · 2026-01-01

  articleOpen access

  We study $(ε,δ)$-differentially private algorithms for the problem of approximately computing the top singular vector of a matrix $A\in\mathbb{R}^{n\times d}$ where each row of $A$ is a datapoint in $\mathbb{R}^{d}$. In our privacy model, neighboring inputs differ by one single row/datapoint. We study the private variant of the power iteration method, which is widely adopted in practice. Our algorithm is based on a filtering technique which adapts to the coherence parameter of the input matrix. This technique provides a utility that goes beyond the worst-case guarantees for matrices with low coherence parameter. Our work departs from and complements the work by Hardt-Roth (STOC 2013) which designed a private power iteration method for the privacy model where neighboring inputs differ in one single entry by at most 1.

  PublisherOA PDF

• Solving Positive Linear Programs with Differential Privacy

  arXiv (Cornell University) · 2026-04-29

  articleOpen access1st authorCorresponding

  We study differentially private approximation algorithms for positive linear programs (LPs with nonnegative coefficients and variables), focusing on the fundamental families of packing, covering, and mixed packing-covering formulations. We focus on the high-sensitivity, constraint-private regime of Hsu-Roth-Roughgarden-Ullman (ICALP 2014), where neighboring instances may differ by an arbitrary single constraint, so one cannot hope to approximately satisfy every constraint under privacy. We give private solvers that return approximate solutions while violating only a controlled number of constraints. Our algorithms improve the prior instance-dependent guarantees, and also yield new data-independent bounds that depend only on the dimension. Our techniques involve a dense multiplicative weights update method developed from a regularized dual viewpoint, which we analyze in a way that exploits structure specific to positive LPs.

  PublisherOA PDF

• Introduction: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2021 Special Issue

  ACM Transactions on Algorithms · 2025-06-27

  articleOpen access1st authorCorresponding
  PublisherOA PDFDOI

• Solving Linear Programs with Differential Privacy

  ArXiv.org · 2025-07-15

  preprintOpen access1st authorCorresponding

  We study the problem of solving linear programs of the form $Ax\le b$, $x\ge0$ with differential privacy. For homogeneous LPs $Ax\ge0$, we give an efficient $(ε,δ)$-differentially private algorithm which with probability at least $1-β$ finds in polynomial time a solution that satisfies all but $O(\frac{d^{2}}ε\log^{2}\frac{d}{δβ}\sqrt{\log\frac{1}{ρ_{0}}})$ constraints, for problems with margin $ρ_{0}>0$. This improves the bound of $O(\frac{d^{5}}ε\log^{1.5}\frac{1}{ρ_{0}}\mathrm{poly}\log(d,\frac{1}δ,\frac{1}β))$ by [Kaplan-Mansour-Moran-Stemmer-Tur, STOC '25]. For general LPs $Ax\le b$, $x\ge0$ with potentially zero margin, we give an efficient $(ε,δ)$-differentially private algorithm that w.h.p drops $O(\frac{d^{4}}ε\log^{2.5}\frac{d}δ\sqrt{\log dU})$ constraints, where $U$ is an upper bound for the entries of $A$ and $b$ in absolute value. This improves the result by Kaplan et al. by at least a factor of $d^{5}$. Our techniques build upon privatizing a rescaling perceptron algorithm by [Hoberg-Rothvoss, IPCO '17] and a more refined iterative procedure for identifying equality constraints by Kaplan et al.

  PublisherOA PDFDOI

• Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures

  ArXiv.org · 2025-04-25

  preprintOpen access1st authorCorresponding

  In the maximum coverage problem we are given $d$ subsets from a universe $[n]$, and the goal is to output $k$ subsets such that their union covers the largest possible number of distinct items. We present the first algorithm for maximum coverage in the turnstile streaming model, where updates which insert or delete an item from a subset come one-by-one. Notably our algorithm only uses $poly\log n$ update time. We also present turnstile streaming algorithms for targeted and general fingerprinting for risk management where the goal is to determine which features pose the greatest re-identification risk in a dataset. As part of our work, we give a result of independent interest: an algorithm to estimate the complement of the $p^{\text{th}}$ frequency moment of a vector for $p \geq 2$. Empirical evaluation confirms the practicality of our fingerprinting algorithms demonstrating a speedup of up to $210$x over prior work.

  PublisherOA PDFDOI

• Improved $\ell_{p}$ Regression via Iteratively Reweighted Least Squares

  ArXiv.org · 2025-10-02

  preprintOpen access1st authorCorresponding

  We introduce fast algorithms for solving $\ell_{p}$ regression problems using the iteratively reweighted least squares (IRLS) method. Our approach achieves state-of-the-art iteration complexity, outperforming the IRLS algorithm by Adil-Peng-Sachdeva (NeurIPS 2019) and matching the theoretical bounds established by the complex algorithm of Adil-Kyng-Peng-Sachdeva (SODA 2019, J. ACM 2024) via a simpler lightweight iterative scheme. This bridges the existing gap between theoretical and practical algorithms for $\ell_{p}$ regression. Our algorithms depart from prior approaches, using a primal-dual framework, in which the update rule can be naturally derived from an invariant maintained for the dual objective. Empirically, we show that our algorithms significantly outperform both the IRLS algorithm by Adil-Peng-Sachdeva and MATLAB/CVX implementations.

  PublisherOA PDFDOI

• Quasi-Self-Concordant Optimization with Lewis Weights

  ArXiv.org · 2025-10-24

  articleOpen access1st authorCorresponding

  In this paper, we study the problem $\min_{x\in \mathbb{R}^{d},Nx=v}\sum_{i=1}^{n}f((Ax-b)_{i})$ for a quasi-self-concordant function $f:\mathbb{R}\to\mathbb{R}$, where $A,N$ are $n\times d$ and $m\times d$ matrices, $b,v$ are vectors of length $n$ and $m$ with $n\ge d.$ We show an algorithm based on a trust-region method with an oracle that can be implemented using $\widetilde{O}(d^{1/3})$ linear system solves, improving the $\widetilde{O}(n^{1/3})$ oracle by {[}Adil-Bullins-Sachdeva, NeurIPS 2021{]}. Our implementation of the oracle relies on solving the overdetermined $\ell_{\infty}$-regression problem $\min_{x\in\mathbb{R}^{d},Nx=v}\|Ax-b\|_{\infty}$. We provide an algorithm that finds a $(1+ε)$-approximate solution to this problem using $O((d^{1/3}/ε+1/ε^{2})\log(n/ε))$ linear system solves. This algorithm leverages $\ell_{\infty}$ Lewis weight overestimates and achieves this iteration complexity via a simple lightweight IRLS approach, inspired by the work of {[}Ene-Vladu, ICML 2019{]}. Experimentally, we demonstrate that our algorithm significantly improves the runtime of the standard CVX solver.

  PublisherOA PDF

• Online and Streaming Algorithms for Constrained k-Submodular Maximization

  Proceedings of the AAAI Conference on Artificial Intelligence · 2025-04-11 · 1 citations

  articleOpen access

  Constrained k-submodular maximization is a general framework that captures many discrete optimization problems such as ad allocation, influence maximization, personalized recommendation, and many others. In many of these applications, datasets are large or decisions need to be made in an online manner, which motivates the development of efficient streaming and online algorithms. In this work, we develop single-pass streaming and online algorithms for constrained k-submodular maximization with both monotone and general (possibly non-monotone) objectives subject to cardinality and knapsack constraints. Our algorithms achieve provable constant-factor approximation guarantees which improve upon the state of the art in almost all settings. Moreover, they achieve the fastest known running times and have optimal space usage. We experimentally evaluate our algorithms on instances for ad allocation and other applications, where we observe that our algorithms are practical and scalable, and construct solutions that are comparable in value even to offline greedy algorithms.

  PublisherOA PDFDOI

Recent grants

• III: Small: A primal-dual framework for data-mining applications

  NSF · $500k · 2019–2024

• CAREER: New Algorithms for Submodular Optimization

  NSF · $507k · 2018–2025

Frequent coauthors

• Huy L. Nguyễn

  60 shared

• Chandra Chekuri

  22 shared

• Adrian Vladu

  Institut de Recherche en Informatique Fondamentale

  19 shared

• Ali Vakilian

  9 shared

• Ta Duy Nguyen

  7 shared

• Justin Ward

  6 shared

• Rafael da Ponte Barbosa

  Universidade Federal de Mato Grosso do Sul

  6 shared

• Marcin Pilipczuk

  University of Warsaw

  6 shared

Education

• Ph.D.

  University of Illinois at Urbana-Champaign

  2013

• B.S., Computer Science

  Princeton University

  2008