6 papers
DaDaDa: A Dataset for Data Pricing in Data Marketplaces
Qiheng Sun, Hongwei Zhang, Junxu Liu +4
High-quality data drives machine learning advances across industries. Recognizing the value of data, data transactions are increasingly common, giving rise to many data marketplace…
Feature Attribution in Directed Acyclic Graphs Using Edge Intervention
Qiheng Sun, Junxu Liu, Xiaokai Mao +4
Shapley value-based feature attribution methods face challenges in scenarios involving complex feature interactions and causal relationships, even when a causal structure is provid…
Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time
Xiao Mao, Aviad Rubinstein
We present novel randomized approximation schemes for the Edit Distance (ED) problem and the Longest Common Subsequence (LCS) problem that, for any constant , compute a $(1+Î…
Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection
BartÅomiej Dudek, Nick Fischer, Geri Gokaj +4
We revisit the complexity of verifying basic identities, such as associativity and distributivity, on a given finite algebraic structure. In particular, while Rajagopalan and Schul…
A Faster Directed Single-Source Shortest Path Algorithm
Ran Duan, Xiao Mao, Xinkai Shu +1
This paper presents a new deterministic algorithm for single-source shortest paths (SSSP) on real non-negative edge-weighted directed graphs, with running time $O(m\sqrt{\log n}+\s…
Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
Ran Duan, Jiayi Mao, Xiao Mao +2
We give a deterministic -time algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weights in the comparison-addition m…