[Cs5500] More questions - Homework 1

[Madhuvanthi Balasubramanian]

Hello All,

         Here are the answers to the first 3 questions, as discussed with
the Professor this morning.

1.      How is quality calculated in general ?

         In case of HSR, it is the ratio of the "claimed" highest rung to
the highest rung n.
         In CSP, it is the ratio of the number of variables assigned to the
maximum number of variables.
         I'm not sure how this compares to the MMG problem. Is the quality
measured by how close the claimed c is, to the maximum C
        ? In that case, the SCG court is supposed to
         have an idea of the maximum C, which cannot be possible. So how do
we measure quality then?


         In case of MMG, quality is measured by how close the solution
brings the inequality to the claimed K(C) value. In other words,

                     { Quality q =          0,               if f(x,y) < C
                                                 =             f(x,y)-C ,
  if (f (x,y ) > = C }

               where f(x,y) is the inequality (xy + (1-x)(1-y^2)), C is the
claim, x is the instance and y is the solution.


2.      What's the deal with computing reputation in case of an agreement?

         There are 3 conditions that both Alice and Bob would have to
meet,in order to win/defend the agreement.
         But we are not clear on how this works.(Why would Bob have to
defend C,against Alice, to agree with Alice on C ?? )
         Could someone clear this up for us?

         In case of an agreement, both Alice and Bob would have to defend C
against the other person and refute its negation.

         This brings up 4 scenerios:

               1. If Bob successfully defends and refutes and Alice doesn't,
Bob wins reputation and Alice loses her reputation.
               2. If Alice successfully defends and refutes C and Bob
doesn't, Alice wins reputation and Bob loses.
               3. If both Alice and Bob successfully defend and refute C and
agree, both win, the reputations remain unaffected, and the claim goes to
the claim repository.
               4. If neither is successful - this will be discussed in class
today.

3.      We have assumed that in case of a refute, an instance is provided,
and in case of a strengthen, the current claim is strengthened with a better
value (new claim ). Is our
         understanding right?

               Our protocol (ForAllExists) dictates that Bob would always
provide an instance when he refutes and Alice would provide a solution to
defend herself successfully. Other protocols may dictate otherwise. We'll
look into other protocols in class today.

On Mon, Sep 19, 2011 at 1:32 PM, Karl Lieberherr <lieber at ccs.neu.edu> wrote:

> Hi Madhu:
>
> excellent questions. I have time to answer only the first by email now and
> the rest we will answer in class tonight:
>
> quality(i,s) tells us how good solution s is for instance i.
> For HSR it is the depth of s divided by n, the number of rungs.
>
> Madhu will send a separate message answering some of the questions
> and the rest we will discuss tonight.
>
> -- Karl
>
> On Sun, Sep 18, 2011 at 10:56 PM, Madhuvanthi Balasubramanian
> <balasubramanian.m at husky.neu.edu> wrote:
> > Hello All,
> >          Could someone help us with the following issues?
> > 1.      How is quality calculated in general ?
> >          In case of HSR, it is the ratio of the "claimed" highest rung to
> > the highest rung n.
> >          In CSP, it is the ratio of the number of variables assigned to
> the
> > maximum number of variables.
> >          I'm not sure how this compares to the MMG problem. Is the
> quality
> > measured by how close the claimed c is, to the maximum C ? In that case,
> the
> > SCG court is supposed to
> >          have an idea of the maximum C, which cannot be possible. So how
> do
> > we measure quality then?
> > 2.      What's the deal with computing reputation in case of an
> agreement?
> >          There are 3 conditions that both Alice and Bob would have to
> > meet,in order to win/defend the agreement.
> >          But we are not clear on how this works.(Why would Bob have to
> > defend C,against Alice, to agree with Alice on C ?? )
> >          Could someone clear this up for us?
> > 3.      We have assumed that in case of a refute, an instance is
> provided,
> > and in case of a strengthen, the current claim is strengthened with a
> better
> > value (new claim ). Is our
> >          understanding right?
> > 4.       Let's say Alice makes a claim for C = 0.50, Bob strengthens it
> with
> > a value of 0.55. Now can Alice only defend her own claim, or strengthen
> > Bob's claim again? Even if she
> >          defends, how does she do it? Does she provide an instance for
> Bob,
> > for which he cannot provide a solution?
> > 5.       Is there a document that details the different use-cases
> possible,
> > in terms of proposing and opposing?
> > Any help would be appreciated.
> > --
> >  Thanks
> > - Madhu
> >
> > _______________________________________________
> > Cs5500 mailing list
> > Cs5500 at lists.ccs.neu.edu
> > https://lists.ccs.neu.edu/bin/listinfo/cs5500
> >
> >
>



-- 
 Thanks
- Madhu
-------------- next part --------------
HTML attachment scrubbed and removed