What is the proof of lemma 4.3 in this paper?


That is, how does it follow from 4.1 and 4.2?

Also, why is the constant 8 necessary? How is it used in a way that 1 wouldn't be enough?

There's an LNCS version too, but it also doesn't spell out the proof. There are slides, but they don't seem to be stand-alone:


  • 1
    $\begingroup$ This is perhaps something you should ask the authors about, not us. Luckily, they are alive and very active researchers! $\endgroup$ – Mahdi Cheraghchi Feb 27 '13 at 15:32
  • 1
    $\begingroup$ @MCH, why do you say that? Authors would have a lot more correspondence to deal with if people emailed them over all confusions in reading their papers :). This seems to me like a well-suited question for this site (or maybe cs.stackexchange.com?). user13959, maybe consider adding some background details or reproducing the lemma? $\endgroup$ – usul Feb 27 '13 at 16:20
  • 1
    $\begingroup$ Well, when you publish a paper, you are advertising your work to the public. As such, you will indeed become responsible to answer any questions or confusions that the readers of your paper may have (in a timely manner). This responsibility also gives you a good motivation to write clearly in the first place. Such questions should be asked here only if the authors fail to respond in a timely manner, which I do not expect to be the case regarding this question. I'm sure if the poster contacts the author, they will respond really fast and much better than any of us would do. $\endgroup$ – Mahdi Cheraghchi Feb 27 '13 at 18:31
  • $\begingroup$ @MCH, interesting perspective! I think I would agree if the authors omit a proof and the proof is not "straightforward". But for me, it's hard to tell if there is an unclear omission or I am just being dense, so I'd be too nervous to email usually. (anyway I guess we can move to chat to discuss further.) $\endgroup$ – usul Feb 27 '13 at 19:15
  • $\begingroup$ I think the question can be suitable if you make it self-contained. Please copy the relevant parts from the paper into the question so it can be read without looking at the paper. $\endgroup$ – Kaveh Mar 2 '13 at 7:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.