Surya Mathialagan

activity

20222026

collaborators

4 papers

cs.DS2026

Preprocessed 3SUM for Unknown Universes with Subquadratic Space

Yael Kirkpatrick, John Kuszmaul, Surya Mathialagan +1

We consider the classic 3SUM problem: given sets of integers $A, B, C$ , determine whether there is a tuple $(a, b, c) \in A \times B \times C$ satisfying $a + b + c = 0$ . The 3SUM…

cs.DS2024

A Note on the Conditional Optimality of Chiba and Nishizeki's Algorithms

Yael Kirkpatrick, Surya Mathialagan

In a seminal work, Chiba and Nishizeki [SIAM J. Comput. `85] developed subgraph listing algorithms for triangles, 4-cycle and $k$ -cliques, where $k \geq 3.$ The runtimes of their a…

cs.DS2023

Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques

Mina Dalirrooyfard, Surya Mathialagan, Virginia Vassilevska Williams +1

We study finding and listing $k$ -cliques in a graph, for constant $k \geq 3$ , a fundamental problem of both theoretical and practical importance. Our main contribution is a new outp…

cs.DS2022

Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds

Surya Mathialagan, Virginia Vassilevska Williams, Yinzhan Xu

The AP-LCA problem asks, given an $n$ -node directed acyclic graph (DAG), to compute for every pair of vertices $u$ and $v$ in the DAG a lowest common ancestor (LCA) of $u$ and $v$ …