Vasileios Nakos

activity

20242026

collaborators

6 papers

cs.DS2026

Robustifying Sparse Matrix Multiplication

Karl Bringmann, Nick Fischer, Vasileios Nakos

In the seminal sparse matrix multiplication problem the goal is to compute the product of two $n \times n$ matrices when the matrices are sparse, i.e., when the number of nonzeros…

cs.DB2026

Listing Even Cycles Faster than the Submodular-Width Barrier

Vasileios Nakos, Hung Q. Ngo, Andreas Panayi

A classic result of Alon, Yuster, and Zwick (AYZ, Algorithmica 1997) shows that all $2 k$ -cycles in an $m$ -edge graph can be listed in $O ~ (m^{2 - 1/ k} + t)$ time, where $t$ is the…

cs.DS2025

$ℓ_{2} / ℓ_{2}$ Sparse Recovery via Weighted Hypergraph Peeling

Nick Fischer, Vasileios Nakos

We demonstrate that the best $k$ -sparse approximation of a length- $n$ vector can be recovered within a $(1 + I^µ)$ -factor approximation in $O ((k / I^µ) lo g n)$ time using a non-adaptive…

cs.DB2025

Information Theory Strikes Back: New Development in the Theory of Cardinality Estimation

Mahmoud Abo Khamis, Vasileios Nakos, Dan Olteanu +1

Estimating the cardinality of the output of a query is a fundamental problem in database query processing. In this article, we overview a recently published contribution that casts…

cs.DS2024

Beating Bellman's Algorithm for Subset Sum

Karl Bringmann, Nick Fischer, Vasileios Nakos

Bellman's algorithm for Subset Sum is one of the earliest and simplest examples of dynamic programming, dating back to 1957. For a given set of $n$ integers $X$ and a target $t$ , i…

cs.DB2024

Targeted Least Cardinality Candidate Key for Relational Databases

Vasileios Nakos, Hung Q. Ngo, Charalampos E. Tsourakakis

Functional dependencies (FDs) are a central theme in databases, playing a major role in the design of database schemas and the optimization of queries. In this work, we introduce t…