Beyond the Worst-Case Analysis of Algorithms

Title Page
Contents
Preface
Contributors
CHAPTER ONE Introduction
PART ONE Refinements of Worse-Case Analysis
	CHAPTER TWO Parameterized Algorithms
	CHAPTER THREE From Adaptive Analysis to Instance Optimality
	CHAPTER FOUR Resource Augmentation
PART TWO Deterministic Models of Data
	CHAPTER FIVE Perturbation Resilience
	CHAPTER SIX Approximation Stability and Proxy Objectives
	CHAPTER SEVEN Sparse Recovery
PART THREE Semirandom Models
	CHAPTER EIGHT Distributional Analysis
	CHAPTER NINE Introduction to Semirandom Models
	CHAPTER TEN Semirandom Stochastic Block Models
	CHAPTER ELEVEN Random-Order Models
	CHAPTER TWELVE Self-Improving Algorithms
PART FOUR Smoothed Analysis
	CHAPTER THIRTEEN Smoothed Analysis of Local Search
	CHAPTER FOURTEEN Smoothed Analysis of the Simplex Method
	CHAPTER FIFTEEN Smoothed Analysis of Pareto Curves in Multiobjective Optimization
PART FIVE Applications in Machine Learning and Statistics
	CHAPTER SIXTEEN Noise in Classification
	CHAPTER SEVENTEEN Robust High-Dimensional Statistics
	CHAPTER EIGHTEEN Nearest Neighbor Classification and Search
	CHAPTER NINETEEN Efficient Tensor Decomposition
	CHAPTER TWENTY Topic Models and Nonnegative Matrix Factorization
	CHAPTER TWENTY ONE Why Do Local Methods Solve Nonconvex Problems?
	CHAPTER TWENTY TWO Generalization in Overparameterized Models
	CHAPTER TWENTY THREE Instance Optimal Distribution Testing and Learning
PART SIX Further Applications
	CHAPTER TWENTY FOUR Beyond Competitive Analysis
	CHAPTER TWENTY FIVE On the Unreasonable Effectiveness of SAT Solvers
	CHAPTER TWENTY SIX When Simple Hash Functions Suffice
	CHAPTER TWENTY SEVEN Prior-Independent Auctions
	CHAPTER TWENTY EIGHT Distribution-Free Models of Social Networks
	CHAPTER TWENTY NINE Data-Driven Algorithm Design
	CHAPTER THIRTY Algorithms with Predictions
Index