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