Kyriakos Axiotis

For more recent publications, see my Google Scholar page.

IHT with Adaptive Regularization: Sparser Solutions Without Sacrificing Runtime (ICML 2022)

We propose a simple modification to the iterative hard thresholding (IHT) algorithm that leads to improving the sparsity of the solution by a factor of $O($condition number$)$. Our technical tool is a new adaptive regularization framework, in which the algorithm progressively learns the weights of an $\ell_2$ regularization term.

with Maxim Sviridenko

Faster Sparse Minimum Cost Flow by Electrical Flow Localization (FOCS 2021)

We give the first minimum cost flow algorithm that improves over the longstanding $\widetilde{O}\left(m^{3/2}\right)$ runtime bound for sparse graphs with general capacities.

with Aleksander Mądry and Adrian Vladu

Decomposable Submodular Function Minimization via Maximum Flow (ICML 2021)

We minimize the sum of $O(1)$-sized submodular functions using $\widetilde{O}(1)$ calls to a maximum flow oracle.

with Adam Karczmarz, Anish Mukherjee, Piotr Sankowski, and Adrian Vladu

Local Search Algorithms for Rank-Constrained Convex Optimization (ICLR 2021)

We give the best known rank bounds for minimizing a convex function under a rank constraint, based on the condition number. We also propose efficient practical implementations and test them on a variety of problems such as matrix completion and robust PCA.

with Maxim Sviridenko

Fast and Simple Modular Subset Sum (SOSA 2021)

We present an extremely simple $\widetilde{O}\left(m\right)$ algorithm for the modular subset sum problem that uses rolling hash.

with Arturs Backurs, Karl Bringmann, Ce Jin, Vasileios Nakos, Christos Tzamos, and Hongxun Wu

Circulation Control for Faster Minimum Cost Flow in Unit-Capacity Graphs (FOCS 2020)

We improve the runtime of minimum cost flow for unit-capacity graphs to $\widetilde{O}\left(m^{4/3} \log W\right)$. This also implies faster runtimes for shortest path with negative weights and minimum cost bipartite $b$-matching with $\|b\|_1\leq O(m)$.

with Aleksander Mądry and Adrian Vladu

Sparse Convex Optimization via Adaptively Regularized Hard Thresholding (JMLR 2021, ICML 2020)

We give the best known sparsity bounds for minimizing a convex function under a sparsity constraint, based on the condition number. We achieve this with an adaptive regularization technique which can be used to escape local minima.

with Maxim Sviridenko

Fast Modular Subset Sum Using Linear Sketching (SODA 2019)

We provide a tight $\widetilde{O}\left(m\right)$-time algorithm for the modular subset sum problem using linear sketching and data structures for storing sums.

with Arturs Backurs, Ce Jin, Christos Tzamos, and Hongxun Wu

Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms (ICALP 2019)

We provide the fastest known algorithms for the knapsack problem with bounded item weights or values, using $(\min,+)$-convolutions.

with Christos Tzamos

On the Size and the Approximability of Minimum Temporally Connected Subgraphs (ICALP 2016)

We show that sparsifying a temporal graph while preserving temporal connectivity is impossible in general, and study algorithms for approximately computing such a sparsifier in various restricted graph families.

with Dimitris Fotakis

Kyriakos Axiotis

Publications

Awards

Other