@InProceedings{APR08,
  author = 	 { Javed Aslam and Raluca A. Popa and Ronald L. Rivest },
  title = 	 { On Auditing Elections When Precincts Have Different Sizes },
  url =          { http://www.usenix.org/events/evt08/tech/full_papers/aslam/aslam.pdf },
  urla =         { <a href="http://www.usenix.org/events/evt08/">EVT'08</a> },                  
  booktitle =    { Proceedings 2008 USENIX/ACCURATE Electronic Voting Technology Workshop },
  OPTyear = 	 { 2008 },
  OPTmonth = 	 { July 28--August 1, },
  date =         { 2008 },                  
  editor = 	 { David Dill and Tadayoshi Kohno },
  eventtitle =   { EVT'08 },
  eventdate =    { 2008-07-28/2008-08-01 },                                    
  venue =        { San Jose, California },                  
  organization = { USENIX/ACCURATE },
  OPTpublisher = {},
  abstract =     {
        We address the problem of auditing an election when
        precincts may have different sizes. Prior work in this
        field has emphasized the simpler case when all precincts
        have the same size. Using auditing methods developed
        for use with equal-sized precincts can, however, be inefficient
        or result in loss of statistical confidence when
        applied to elections with variable-sized precincts.
        \par                  
        We survey, evaluate, and compare a variety of approaches
        to the variable-sized precinct auditing problem,
        including the SAFE method [11] which is based on theory
        developed for equal-sized precincts. We introduce
        new methods such as the negative-exponential method
        ``NEGEXP'' that select precincts independently for auditing
        with predetermined probabilities, and the ``PPEBWR''
        method that uses a sequence of rounds to select precincts
        with replacement according to some predetermined probability
        distribution that may depend on error bounds for
        each precinct (hence the name PPEBWR: probability proportional
        to error bounds, with replacement), where the
        error bounds may depend on the sizes of the precincts, or
        on how the votes were cast in each precinct.
        \par
        We give experimental results showing that NEGEXP
        and PPEBWR can dramatically reduce (by a factor or two
        or three) the cost of auditing compared to methods such
        as SAFE that depend on the use of uniform sampling.
        Sampling so that larger precincts are audited with appropriately
        larger probability can yield large reductions in
        expected number of votes counted in an audit.
        \par                  
        We also present the optimal auditing strategy, which
        is nicely representable as a linear programming problem
        but only efficiently computable for small elections (fewer
        than a dozen precincts). We conclude with some recommendations
        for practice.                  
                 },  
}