research
∙
09/03/2023
(min,+) Matrix and Vector Products for Inputs Decomposable into Few Monotone Subsequences
We study the time complexity of computing the (min,+) matrix product o...
share
research
∙
08/22/2023
Finding Small Complete Subgraphs Efficiently
(I) We revisit the algorithmic problem of finding all triangles in a gra...
research
∙
05/17/2023
Convex Hulls and Triangulations of Planar Point Sets on the Congested Clique
We consider geometric problems on planar n^2-point sets in the congested...
research
∙
05/12/2023
Improved Lower Bounds for Monotone q-Multilinear Boolean Circuits
A monotone Boolean circuit is composed of OR gates, AND gates and input ...
research
∙
02/03/2022
Perpetual maintenance of machines with different urgency requirements
A garden G is populated by n≥ 1 bamboos b_1, b_2, ..., b_n with the resp...
research
∙
09/30/2021
Breaking the hegemony of the triangle method in clique detection
We consider the fundamental problem of detecting/counting copies of a fi...
research
∙
08/26/2021
On Truly Parallel Time in Population Protocols
The parallel time of a population protocol is defined as the average num...
research
∙
08/07/2021
An output-sensitive algorithm for all-pairs shortest paths in directed acyclic graphs
A straightforward dynamic programming method for the single-source short...
research
∙
05/25/2021
Efficient Assignment of Identities in Anonymous Populations
We consider the fundamental problem of assigning distinct labels to agen...
research
∙
11/04/2020
Consequences of APSP, triangle detection, and 3SUM hardness for separation between determinism and non-determinism
We present implications from the known conjectures like APSP, 3SUM and E...
research
∙
04/29/2020
Quantum and approximation algorithms for maximum witnesses of Boolean matrix products
The problem of finding maximum (or minimum) witnesses of the Boolean pro...
research
∙
04/27/2020
Computing the Boolean product of two n× n Boolean matrices using O(n^2) mechanical operation
We study the problem of determining the Boolean product of two n× n Bool...
research
∙
12/01/2017