Author: Stan Eisenstat
Subject: Re: [Cs223] adversary
Date: Sunday, 01 Mar 2020, 11:51:55

    > Message Posted By: Unknown
    >
    > what is the point of an adversary argument? is it essentially listing out
    > all possible combinations, minimizing the number of combinations deleted
    > each round (ie. making the algorithm take as many steps as possible), and
    > then calculating the number of steps required?

The point of an adversary argument is to establish a
lower bound on the complexity of a problem; that is,
a lower bound on the complexity of any algorithm that
solves it.

The form of adversary argument that we discussed in
class uses a set S of possible problem instances to
answer questions posed by the algorithm.  The lower
bound follows from an analysis of how many questions
are needed to reduce the size of S to a point where
the solution to the problem is known.
=====

    > why does an adversary argument imply that an algorithm is optimal?

If an algorithm can solve the problem by asking the
smallest possible number of questions, then no other
algorithm can be better.
=====

    > i also don't get the point of the three examples in lecture 9. under the
    > element uniqueness problem, there is equality testing, inequality testing
    > and anything goes. for inequality testing, we are told to sort the items
    > first. but then the procedure compares each possible pair. so what is the
    > algorithm and what is the procedure? i'm very confused about what the
    > actual algorithm is, what the adversary is, and how the adversary proves
    > that the algorithm is optimal.

The three examples are one problem (element uniqueness)
with three different models of computation (what kinds
of operations are permitted):  With equality testing,
an algiorithm can only ask if two photographs are
pictures of the same person.  With inequality testing,
an algorithm can ask whether one weight is lighter than,
of equal weight to, or heavier than another weight.  In
anything goes, the algorithm can use the integers in
any manner it chooses.

In each case we derived an algorithm, and in the first
two we showed that that algorithm achieved the lower
bound in that model of computation and thus was optimal.
=====

    > for anything goes, there was no complexity analysis or adversary provided.
    > what is the point of anything goes? also, what does anything goes mean?

The algorithm runs in time linear in the number of
items.  Since any algorithm must look every item in the
worst case, no algorithm can run more than a constant
times faster.

--Stan-