- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies the computational complexity of compressing a single string via merges of pair-enconded rules. More precisely, a rule has the form X>YZ, where X is a new unused symbol (Y and Z are symbols too) and replaces at least one occurrence of YZ by X (not necessarily all). The goal is to minimize the total number L of tokens (total length of the resulting string) using at most k rules. The main results of the paper are as follows:
- If the budget k has to be respected exactly then unless P=NP, no deterministic polynomial-time algorithm can guarantee in the worst case a length that is more than a constant factor better than doing nothing. This result is shown by a reduction from cubic vertex cover.
- If more than k rules are allowed, then a simple hierarchy gets a O(log^2 n) approximation. Moreover, experiments on small stings are conducted.
JUDGMENT
The results are interesting, but did not check the proofs in detail. I only checked there main ideas which seem to be correct to me. My main concerns are the limited technical novelty and the limited interest for the ML community. Another downside is the current presentation which contains many undefined notation. Thus, I think the paper does not meet the bar for acceptance at ICLR.
Critical strengths
-
The paper uses nice connections between pair encodings and tools of grammar compression.
-
The positive algorithmic results is non-trivial
-
the provided lower bound is computable in polynomial time and is often tight in small instances
-
The shown hardness result holds in quite restricted settings
Critical weaknesses
-
The hardness result is very close to existing work. Moreover, the budget k is very large (linear) in the reduction, so the result has no implications for small k. In general many results are close to existing results.
-
The experiments do not verify any of the main results. Also the tested string length is very small.
-
I don't think the studied problem is broadly relevant for an ML audience. Also the citations show this: most of them are string-conferences and TCS conferences.
-
I think since the problem is quite related to the smallest grammar problem, more papers on this problem should be cited, for example: 'On the Complexity of Grammar-Based Compression over Fixed Alphabets' to name one. (i did a quick scholar search for this)
-
It was quote hard for me to follow this paper: Already the overview paragraph in Line 43 is hard to follow for someone outside of the area. Also, many notations are used, before they are defined (or are never defined). For me, Algorithm 1 was only understandable with the appendix. Also OPE is never explained and token is only explained in the appendix.
Questions for authors
-
What do OPE, OMS and WPF stand for?
-
Can you give an intuition for the values of q, \rho_n and \beta_n (line 211) and for the certificate quantities A_\partial(s) and LB_\partial(s,k) (line 337)?
-
Why did you not evaluate your algorithm? And why were only very small instances tested?
-
Can the hardness result be strengthened, for example to constant size alphabets or sublinear budgets?
Further Comments:
-
Some abbreviations are never expanded: OPE, OMS, WPF, BPE, SLP, EvenOdd, SLP, q-gram
-
the notion of a token is defined only in Appendix A, but the main text uses 'final tokens' (also applies to snapshot)
-
used before the definition: n, U, L*, WPF_\lambda, \lambda, \rho_n, \beta_n, p_m(s), m, A_\partial, LB_\partial
-
line 591: suf_a(.) and pre_{m-a}(.) are not defined
-
the paragraph starting in line 43 is hard to follow for me as a reader outside the area: it uses notions that are not yet defined (dependency-closed pruning, comparison grammar, rule/root pair, L*), and in the inequalities r <= O(log^2 n)k and L <= O(log^2 n)L*(s,k) it is not said to which object r and L refer
-
line 47: the 'trivial n-approximation' is not explained at this point
-
line 211: please give an intuition for q, \rho_n and \beta_n.
-
paragraph starting in line 296: instead of listing the normalization steps, it would be more helpful to explain the concrete correspondence between forests and vertex covers
-
line 337: please provide an intuition for A_\partial(s) and LB_\partial(s,k)
-
line 681: 'but not length membership in APX' is a strange formulation. Please reformulate, for example: 'but it does not show that the length version is in APX'
-
line 549 / Section 2: the model seems to allow a later rule X' -> ab with a fresh label but the same right-hand side as an earlier rule X -> ab. This is never beneficial and I think the paper uses this implicitly
Discussion summary
We thank the AC and all three reviewers for their time and careful reviews.
In short, the revision makes the paper easier to read, adds proof ideas for both main results, adds an experiment comparing our algorithm with BPE, explains why the hardness proof needs a growing alphabet and a linear budget, and credits earlier work more clearly. No theorem or proof changed in substance. The full list of changes is in our general comment of 7 Nov.
Thank you all again for your time and helpful comments.