37 citations · 164 across the 32 of their papers we have counts for
41 papers
Tree Edit Distance: Near-Linear-Time Approximate, Sublinear, and Dynamic
Bingbing Hu, Tomasz Kociumaka, Jakob Nogler +1
Tree edit distance (TED), the analog of string edit distance (ED) for hierarchical data, is the minimum number of node insertions, deletions, and substitutions transforming one lab…
Fairness in Aggregation: Optimal Top- and Improved Full Ranking
Diptarka Chakraborty, Arya Mazumdar, Barna Saha +1
Ensuring fairness in algorithmic ranking systems is a critical challenge with significant societal implications for hiring, recommendations, web search, and data management. Standa…
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…
Actively Learning Halfspaces without Synthetic Data
Hadley Black, Kasper Green Larsen, Arya Mazumdar +2
In the classic point location problem, one is given an arbitrary dataset of points with query access to an unknown halfspace $f : \mathbb{R}^d \to \{0,…
Learning Partitions with Optimal Query and Round Complexities
Hadley Black, Arya Mazumdar, Barna Saha
We consider the basic problem of learning an unknown partition of elements into at most sets using simple queries that reveal information about a small subset of elements.…
Clustering with Non-adaptive Subset Queries
Hadley Black, Euiwoong Lee, Arya Mazumdar +1
Recovering the underlying -clustering of a set of points by asking pair-wise same-cluster queries has garnered significant interest in the past few years. Given a query…