16 papers
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…
Decision Tree Learning on Product Spaces
Arshia Soltani Moakhar, Faraz Ghahremani, Kiarash Banihashem +1
Decision tree learning has long been a central topic in theoretical computer science, driven by its practical importance. A fundamental and widely used method for decision tree con…
Quiet Planting for -SAT, Multiple Solutions of Arbitrary Geometry
Ali Ahmadi, Kiarash Banihashem, Iman Gholami +2
Recent work on "quiet planting" in combinatorial optimization aims to generate instances with a hidden solution that is hard to recover, typically by making the planted distributio…
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…
Replicable Composition
Kiarash Banihashem, MohammadHossein Bateni, Hossein Esfandiari +2
Replicability requires that algorithmic conclusions remain consistent when rerun on independently drawn data. A central structural question is composition: given problems each…
Active Learning for Decision Trees with Provable Guarantees
Arshia Soltani Moakhar, Tanapoom Laoaron, Faraz Ghahremani +2
This paper advances the theoretical understanding of active learning label complexity for decision trees as binary classifiers. We make two main contributions. First, we provide th…
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…
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…
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…
Bi-Criteria Metric Distortion
Kiarash Banihashem, Diptarka Chakraborty, Shayan Chashm Jahan +4
Selecting representatives based on voters' preferences is a fundamental problem in social choice theory. While cardinal utility functions offer a detailed representation of prefere…
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 Metric Embedding into Space
Kiarash Banihashem, MohammadTaghi Hajiaghayi, Dariusz R. Kowalski +2
We give the first non-trivial decremental dynamic embedding of a weighted, undirected graph into space. Given a weighted graph undergoing a sequence of edge weight…
An Improved Relaxation for Oracle-Efficient Adversarial Contextual Bandits
Kiarash Banihashem, MohammadTaghi Hajiaghayi, Suho Shin +1
We present an oracle-efficient relaxation for the adversarial contextual bandits problem, where the contexts are sequentially drawn i.i.d from a known distribution and the cost seq…
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…