8 papers · 1 filter
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…
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…
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…
Pandora with Inaccurate Priors
Kiarash Banihashem, Xiang Chen, MohammadTaghi Hajiaghayi +4
We investigate the role of inaccurate priors for the classical Pandora's box problem. In the classical Pandora's box problem we are given a set of boxes each with a known cost and…
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…
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…