diff options
| -rw-r--r-- | tcc-2019-120.txt | 17 |
1 files changed, 9 insertions, 8 deletions
diff --git a/tcc-2019-120.txt b/tcc-2019-120.txt index 21bbd3d..58dfb72 100644 --- a/tcc-2019-120.txt +++ b/tcc-2019-120.txt @@ -47,7 +47,7 @@ authors establish the following: communication complexity. Using Hellman's algorithm, this connection leads to an improvement on the best known algorithm for this problem. -* a connection between the function inversion problem and data structure +* a connection between the function inversion problem and the data structure problem of substring search. Using the Fiat-Naor algorithm, this connection implies an algorithm which improves on the best-known algorithms for the substring search problem. @@ -57,6 +57,7 @@ Strengths The paper * sheds light on why improving the ST = Omega(N) lower bound is hard +* improves on state of the art algorithms * is very clear, well-written and a pleasure to read * contains many interesting observations and suggestions for future research @@ -69,7 +70,7 @@ Weaknesses * The paper is a juxtaposition of disparate facts, many of which are not particularly surprising and follow from fairly standard arguments. It would - be nice to have stronger conceptual message connecting the dots. + be nice to have a stronger conceptual message connecting the dots. Comments on the presentation @@ -77,11 +78,11 @@ Comments on the presentation * I think section 2 could make a better job at emphasizing that strongly non adaptive adversaries with oracle access to a function f are nothing but - circuits in the common-bits in disguise (the value table of f plays the role - of the circuit input, the preprocessed string are the common-bits and the - input to the adversary indexes into the output bits of the circuit). There is - a strict syntactic equivalence which is lost in the proof at the moment but - could maybe be abstracted away in a lemma? + circuits in the common-bits model in disguise (the value table of f plays the + role of the circuit input, the preprocessed string are the common-bits and + the input to the adversary indexes into the output bits of the circuit). + There is a strict syntactic equivalence which is a bit lost in the proof at + the moment but could maybe be factorized in a lemma? * The proof idea in section 2.2 is basically the same length as the full proof so I would suggest simply replacing it with the proof given in the appendix. @@ -106,5 +107,5 @@ Summary of recommendation I am leaning towards acceptance. While some of the contributions are not particularly surprising and the whole lacks a bit of coherence, the paper does improve on state of the art algorithms, sheds light on the important function -inversion problem and has the potential to draw attention to it and trigger +inversion problem and has the potential to draw attention to it and spawn interesting future research. |