13 citations · 35 across the 15 of their papers we have counts for
20 papers
Adversarially Robust Approximate Furthest Neighbor
Kiarash Banihashem, Jeff Giliberti, Prashant Gokhale +5
We work in the adaptive query model, where one is given a point set and seeks to construct a data structure that can answer correctly and efficiently a seq…
Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond
Kiarash Banihashem, Jeff Giliberti, Samira Goudarzi +3
In this paper, we study the fundamental problems of maintaining the diameter and a -center clustering of a dynamic point set , where points may be insert…
Range Counting Oracles for Geometric Problems
Anne Driemel, Morteza Monemizadeh, Eunjin Oh +2
In this paper, we study estimators for geometric optimization problems in the sublinear geometric model. In this model, we have oracle access to a point set with size in a disc…
A Dynamic Algorithm for Weighted Submodular Cover Problem
Kiarash Banihashem, Samira Goudarzi, MohammadTaghi Hajiaghayi +2
We initiate the study of the submodular cover problem in dynamic setting where the elements of the ground set are inserted and deleted. In the classical submodular cover problem, w…
Dynamic Non-monotone Submodular Maximization
Kiarash Banihashem, Leyla Biabani, Samira Goudarzi +3
Maximizing submodular functions has been increasingly used in many applications of machine learning, such as data summarization, recommendation systems, and feature selection. More…
Dynamic Algorithms for Matroid Submodular Maximization
Kiarash Banihashem, Leyla Biabani, Samira Goudarzi +3
Submodular maximization under matroid and cardinality constraints are classical problems with a wide range of applications in machine learning, auction theory, and combinatorial op…
Dynamic Constrained Submodular Optimization with Polylogarithmic Update Time
Kiarash Banihashem, Leyla Biabani, Samira Goudarzi +3
Maximizing a monotone submodular function under cardinality constraint is a core problem in machine learning and database with many basic applications, including video and data…
-Center Clustering with Outliers in the MPC and Streaming Model
Mark de Berg, Leyla Biabani, Morteza Monemizadeh
Given a point set of size in a metric space of doubling dimension and two parameters and , the -center problem with out…
-Center Clustering with Outliers in the Sliding-Window Model
Mark de Berg, Morteza Monemizadeh, Yu Zhong
The -center problem for a point set~ asks for a collection of congruent balls (that is, balls of equal radius) that together cover all the points in and whose radius…
Clique-Based Separators for Geometric Intersection Graphs
Mark de Berg, Sándor Kisfaludi-Bak, Morteza Monemizadeh +1
Let be a set of objects in the plane and let be its intersection graph. A balanced clique-based separator of is a set consisting of cliques whose removal…
Dynamic Maximal Independent Set
Morteza Monemizadeh
Given a stream of insertions and deletions of edges of an underlying graph (with fixed vertex set where is the number of vertices of ), we propose…
Testable Bounded Degree Graph Properties Are Random Order Streamable
Morteza Monemizadeh, S. Muthukrishnan, Pan Peng +1
We study which property testing and sublinear time algorithms can be transformed into graph streaming algorithms for random order streams. Our main result is that for bounded degre…
The Sparse Awakens: Streaming Algorithms for Matching Size Estimation in Sparse Graphs
Graham Cormode, Hossein Jowhari, Morteza Monemizadeh +1
Estimating the size of the maximum matching is a canonical problem in graph algorithms, and one that has attracted extensive study over a range of different computational models. W…
Streaming Weighted Matchings: Optimal Meets Greedy
Elena Grigorescu, Morteza Monemizadeh, Samson Zhou
We consider the problem of approximating a maximum weighted matching, when the edges of an underlying weighted graph are revealed in a streaming fashion. We analyze a vari…
Estimating Weighted Matchings in Space
Elena Grigorescu, Morteza Monemizadeh, Samson Zhou
We consider the problem of estimating the weight of a maximum weighted matching of a weighted graph whose edges are revealed in a streaming fashion. We develop a reduction…
Prophet Secretary
Hossein Esfandiari, MohammadTaghi Hajiaghayi, Vahid Liaghat +1
Optimal stopping theory is a powerful tool for analyzing scenarios such as online auctions in which we generally require optimizing an objective function over the space of stopping…
Kernelization via Sampling with Applications to Dynamic Graph Streams
Rajesh Chitnis, Graham Cormode, Hossein Esfandiari +4
In this paper we present a simple but powerful subgraph sampling primitive that is applicable in a variety of computational models including dynamic graph streams (where the input…
A Unified Approach for Clustering Problems on Sliding Windows
Vladimir Braverman, Harry Lang, Keith Levin +1
We explore clustering problems in the streaming sliding window model in both general metric spaces and Euclidean space. We present the first polylogarithmic space -approximat…
Planar Graphs: Random Walks and Bipartiteness Testing
Artur Czumaj, Morteza Monemizadeh, Krzysztof Onak +1
We initiate the study of property testing in arbitrary planar graphs. We prove that bipartiteness can be tested in constant time, improving on the previous bound of $\tilde{O}(\sqr…
Parameterized Streaming Algorithms for Vertex Cover
Rajesh Chitnis, Graham Cormode, MohammadTaghi Hajiaghayi +1
As graphs continue to grow in size, we seek ways to effectively process such data at scale. The model of streaming graph processing, in which a compact summary is maintained as eac…