CS Papers (1995 – 2004)

“A Personal View of Average-Case Complexity” by Russell Impagliazzo – The paper describes five possible worlds regarding the P versus NP problem: Algorithmica, Heuristica, Pessiland, Minicrypt, and Cryptomania. Problems in NP get harder in each successive world, and many believe we live in Cryptomania (where popular cryptosystems are secure), but the P versus NP problem is still open (as of March 2017). The paper then justifies Leonid Levin’s definition of average-case complexity and presents some variations. (1995 paper)

“Scheduling to Minimize Average Completion Time: Off-line and On-line Approximation Algorithms” by L. Hall, A. Schulz, D. Shmoys, and J. Wein – The paper describes LP-based approximations for minimizing total weighted completion time on a single machine, identical parallel machines, and unrelated parallel machines, while taking precedence constraints and preemption into account. The paper also introduces a general framework for online scheduling and uses it to establish first-known competitive ratios for 3 different settings. The online framework first partitions time into intervals of geometrically-increasing length and then uses an offline approximation at the start of each interval to schedule jobs within that interval. (1997 paper)