1 citations · 1 across the 27 of their papers we have counts for
31 papers
Optimally Curating an Event
MohammadTaghi Hajiaghayi, Sebastien Lahaie, Mohammad Mahdavi +1
We study the optimal design of a self-financing event, a problem that requires balancing the recruitment of costly, positive-value participants with revenue-generating agents who m…
Breaking the Exponential Barrier: The First Polynomial-Time Algorithm for the Győri-Lovász Theorem
Mohammad T. Hajiaghayi, Mahdi JafariRaviz, Alireza Kaviani +1
We give the first polynomial-time algorithm, after half a century, for the celebrated Győri-Lovász theorem, which resolved a conjecture of Frank (1975). The theorem, one of the sim…
Can Watermarking Techniques Help Prevent LLM Model Stealing?
Elette Boyle, MohammadTaghi Hajiaghayi, Keivan Rezaei +2
Model stealing attacks have recently been introduced, enabling the extraction of precise information from black-box commercial language models. In this work, we propose defense met…
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…
Beyond the Library: An Agentic Framework for Autoformalizing Research Mathematics
Arshia Soltani Moakhar, Iman Gholami, Max Springer +2
While Large Language Models (LLMs) have demonstrated exceptional capabilities in mathematical reasoning, they frequently produce subtle errors that evade human detection. Formal ma…
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 Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi +2
We present the first dynamic algorithms for Dyck and tree edit distances with subpolynomial update times. Dyck edit distance measures how far a parenthesis string is from a well-pa…
Algorithmic Delegated Choice: An Annotated Reading List
Mohammad T. Hajiaghayi, Suho Shin
The problem of delegated choice has been of long interest in economics and recently on computer science. We overview a list of papers on delegated choice problem, from classic work…
Delegation with Costly Inspection
Mohammad T. Hajiaghayi, Piotr Krysta, Mohammad Mahdavi +1
We study the problem of delegated choice with inspection cost (DCIC), which is a variant of the delegated choice problem by Kleinberg and Kleinberg (EC'18) as well as an extension…
Tokenized Bandit for LLM Decoding and Alignment
Suho Shin, Chenghao Yang, Haifeng Xu +1
We introduce the tokenized linear bandit (TLB) and multi-armed bandit (TMAB), variants of linear and stochastic multi-armed bandit problems inspired by LLM decoding and alignment.…
Prize-Collecting Forest with Submodular Penalties: Improved Approximation
Ali Ahmadi, Iman Gholami, MohammadTaghi Hajiaghayi +2
Constrained forest problems form a class of graph problems where specific connectivity requirements for certain cuts within the graph must be satisfied by selecting the minimum-cos…
Breaking a Long-Standing Barrier: 2- Approximation for Steiner Forest
Ali Ahmadi, Iman Gholami, MohammadTaghi Hajiaghayi +2
The Steiner Forest problem, also known as the Generalized Steiner Tree problem, is a fundamental optimization problem on edge-weighted graphs where, given a set of vertex pairs, th…
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…
Fairness and Efficiency in Online Class Matching
MohammadTaghi Hajiaghayi, Shayan Chashm Jahan, Mohammad Sharifi +2
The online bipartite matching problem, extensively studied in the literature, deals with the allocation of online arriving vertices (items) to a predetermined set of offline vertic…
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…
Ad Auctions for LLMs via Retrieval Augmented Generation
MohammadTaghi Hajiaghayi, Sébastien Lahaie, Keivan Rezaei +1
In the field of computational advertising, the integration of ads into the outputs of large language models (LLMs) presents an opportunity to support these services without comprom…
Nearly-Optimal Consensus Tolerating Adaptive Omissions: Why is a Lot of Randomness Needed?
Mohammad T. Hajiaghayi, Dariusz R. Kowalski, Jan Olkowski
We study the problem of reaching agreement in a synchronous distributed system by autonomous parties, when the communication links from/to faulty parties can omit messages. The…
Dueling Over Dessert, Mastering the Art of Repeated Cake Cutting
Simina Brânzei, MohammadTaghi Hajiaghayi, Reed Phillips +2
We consider the setting of repeated fair division between two players, denoted Alice and Bob, with private valuations over a cake. In each round, a new cake arrives, which is ident…
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…