11 papers
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…