6 papers
Barely Monotone (min,+)-Convolution in Truly Subquadratic Time
MohammadTaghi Hajiaghayi, Danny Mittal, Saeed Seddighin
The (min,+)-convolution of two sequences A and B of length n is the sequence C with C[k] = min_{i+j=k} (A[i]+B[j]). For bounded inputs, whose entries are integers in {0,...,O(n)},…
Efficient Dynamic Algorithms for Graph Neural Networks with Non-Linear Propagation
Kiarash Banihashem, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz +2
Graph Neural Networks (GNNs) are widely used for representation learning on graphs, but most methods assume static topologies, making them inefficient on evolving networks where ed…
Computing All Optimal Partial -Wasserstein Matchings on the Line
Sebastian Angrick, Jacobus Conradi, Mónika Csikós +5
For , the -Wasserstein distance measures the minimum cost of transporting probability mass between distributions, where moving unit mass between two points costs the $p…
Matroid Algorithms Under Size-Sensitive Independence Oracles
Kiarash Banihashem, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz +1
The standard oracle model for matroid algorithms assumes that each independence query can be answered in constant time, regardless of the size of the queried set. While this abstra…
How Bad Is Forming Your Own Multidimensional Opinion?
Kiarash Banihashem, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz +2
Understanding the formation of opinions on interconnected topics within social networks is of significant importance. It offers insights into collective behavior and decision-makin…
Beating Competitive Ratio 4 for Graphic Matroid Secretary
Kiarash Banihashem, MohammadTaghi Hajiaghayi, Dariusz R. Kowalski +3
One of the classic problems in online decision-making is the *secretary problem* where to goal is to maximize the probability of choosing the largest number from a randomly ordered…