Summary
The paper studies the oracle-augmented sorting problem, in which, in addition to the array, an oracle is provided to return ‘reference answers’ for the sorting of the array. The oracle is presumably efficient – queries are assumed to take $O(1)$ time – but might be noisy, i.e., at times return incorrect answers. The key question is to design algorithms that 1). When the oracle is great, the number of comparisons is significantly smaller than the baseline algorithms; and 2). When the oracle is very bad, the number of comparisons is still comparable to the baseline algorithms.
To this end, the paper considered oracles under two settings: a). An oracle that gives ‘dirty comparisons’ – a list of ‘all-pair’ comparisons that may include some errors and b). An oracle that gives a positional list – a list of predicted positions for each element in the array. The paper then designs algorithms under both models. In particular, for the dirty comparison model, the proposed algorithm achieves $O(\sum_{i=1}^{n} \log \eta_{i})$ number of true comparisons and $O(n \log n)$ dirty comparisons, where $\eta_i$ is the number of ‘wrong comparisons’ based on element $a_i$. This demonstrates a smooth tradeoff between the number of true comparisons needed and the prediction error. The paper also obtained similar results for positional list predictions under different notions of error.
I read the dirty-clean comparison algorithm and proofs to some details, and they look correct as far as I can tell. I skimmed the claims for the positional list algorithms, but did not verify the proofs (these algorithms seem to have built on more recent ideas). For the dirty-clean comparison, I think a key observation here is that the binary comparison trees are fairly ‘robust’ against perturbations in the sense that 1). The error is consistent – if there is $R<L$ on level $t$, then the error also happens for all $t’>t$ and 2). Thanks to randomization, the probability of the mess-up of the upper and lower bounds becomes exponentially small when the level moves up. As such, the binary search tree should be able to travel sufficiently deep in the tree based only on the dirty comparisons unless a very large chunk of the comparisons is corrupted. These observations, although not technically novel, do seem to be neat and cute for this problem.
Overall I think the paper makes a significant contribution to a fundamental problem, and the setting is interesting and well-motivated. The paper is also well-written and easy to follow; the experiments also demonstrate competitive performance for the new algorithms. As such, I have a positive evaluation of the paper.
Strengths
As I mentioned in the general evaluation, I think the paper is in a nice shape both in terms of the contributions and the presentations. To elaborate a bit more:
- The paper follows a recent line of work on ‘learning-augmented algorithm’/’algorithm with advice’, and it tackles a very important and fundamental problem. It is surprising that previous work has not considered the problem.
- Although the techniques are not complicated, the algorithms are based on several neat observations. The upper bounds are also tight by matching the lower bounds (unfortunately deferred to the appendix).
- In addition to the theoretical results, the experimental performance is also quite competitive – one interesting observation is that the dirty-clean sort remains very competitive to baseline even when the corruption rate approaches 1. Furthermore, the experiments are run on large scales, which verifies the efficiency also from the practical time side (not necessarily captured by the theoretical time complexity).
Weaknesses
- One potential criticism of the work is that the techniques are not novel and perhaps easy to come up with. This is true for the dirty-clean sorting algorithm; and although I *personally* do *not* think this is an issue, this perspective is frequently flagged for theoretical work. The positional list with left-right errors seems to require more involved techniques, but I do not really like that definition of error.
- It seems the two settings of the oracles in this paper are very natural. However, there could still be other settings that your model does not capture. For instance, one can define a dirty comparison oracle with amortized error only (across ${n \choose 2}$ comparisons), and what will be the optimal bound therein? That being said, I don’t think it’s very fair to ask a paper to address all possible models, so I’m not letting this question affect my evaluation.
- Some (minor) presentation issues: In the binary tree search subroutines of algorithm 1, the use of tuples makes the text slightly confusing. I struggled for a minute to parse the value assignment of tuples. Maybe you can say we use tuples to represent (lower-bound, pivot, upper-bound) before pointing the readers to the algorithm. Also, what does it mean for ‘return inorder traversal of B’? (I know what it means, but is this the best way to say it?)
Questions
- In your clean-dirty comparison model, I think you have this ‘deterministic error’ that if the comparison between a and b is wrong, you cannot get the correct answer by querying it again. This crucially separates your model from the classical noisy comparison line of work (your ‘dirty perturbation’ is not random). If what I said is correct, I would suggest adding a discussion about this.
- In your experiments, the dirty-clean sorting seems extremely robust even when the damage ratio approaches $1$. Is this an artifact of your experiment setting/your implementation, or is there a reason that the algorithm performs in such a nice way? (Note that your proof shows only *asymptotically* competitive, but it seems even the constant is very competitive when the damage ratio is high.)
(More presentation-related)
- Does the term BST on page 4 stand for ‘binary search tree’? The abbreviation was never mentioned before.
- Line 185, it’s a bit weird to talk about ‘timestep’ here – I think you mean the recursion step.
Rating
8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
Confidence
5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.
Limitations
Most of the limitations are discussed in the ‘weakness’ section. From a broader societal perspective, since the work is of theoretical nature, there is no immediate negative impact, and I could not foresee any (take it with a grain of salt since I do not have experience in ethical/societal review).