Computational Complexity

Last update: 11 Dec 2024 10:00
First version: 23 November 2024

---

Yet Another Inadequate Placeholder

--- Or, rather, I've said most of what I have to say in the form of a review of a truly excellent book.

Things to learn: Finally get a handle on all the time complexity classes that are finer than the P/NP distinction. The space classes. Circuit complexity, and how it relates to time and space complexity. Information-based complexity. Connections to / analogies with sample complexity in statistical learning theory. "Phase transitions" between complexity classes, and the analogy to physical phase transitions.

See also:
• Computation, Automata, Languages
• Complexity Measures
• Learning Theory (Formal, Computational or Statistical)
• Optimization [Where I stash most references on the computational complexity of optimization algorithms, except for those which I arbitrarily decide have a broader scope and include here]
• Planned Economies

... though really there are many, many topics where computational-complexity considerations come into play (e.g., community discovery in networks)

Recommended, big picture:
• David Harel, The Science of Computing: Exploring the Nature and Power of Algorithms
• Cristopher Moore and Stephan Mertens, The Nature of Computation [Cris and Stephan were kind enough to let me read this in manuscript; it's magnificent. Review: Intellects Vast and Warm and Sympathetic]

Recommended, close ups: iScott Aaronson, "Why Philosophers Should Care About Computational Complexity", arxiv:1108.1791
• Christos H. Papadimitriou and Kenneth Steiglitz, Combinatorial Optimization: Algorithms and Complexity
• J. F. Traub and A. G. Werschulz, Complexity and Information
• J. F. Traub and H. Wozniakowski, "Persepctives on Information-Based Complexity," Bulletin of the American Mathematical Society 26 (1992): 29--52, math.NA/9201269

To read:
• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach
• David Gamarnik, Cristopher Moore, Lenka Zdeborová, "Disordered Systems Insights on Computational Hardness", arxiv:2210.08312
• Odd Goldreich, Computational Complexity: A Conceptual Perspective
• Raymond Greenlaw, H. James Hoover, Walter L. Ruzzo, Limits to Parallel Computation: P-Completeness Theory
• David Harel, Computers Ltd: What They Really Can't Do [Unless this is just a variant title for Science of Computing?]
• Dorit Hochbaum, Approximation Algorithms for NP-Hard Problems
• Johannes Kobler and Rainer Schuler, "Average-case intractability vs. worst-case intractability", Information and Computation 190 (2004): 1--17
• Eyal Kushilevitz and Noam Nisan, Communication Complexity
• Marc Mezard and Andrea Montanari, Information, Physics, and Computation
• István Miklós, Computational Complexity of Counting and Sampling
• Allon Percus, Gabriel Istrate and Cristopher Moore (eds.), Computational Complexity and Statistical Physics
• Leszek Plaskota, Noisy Information and Computational Complexity [PDF via Dr. Plaskota]
• Anup Rao and Amir Yehudayoff, Communication Complexity: and Applications
• Wojciech Szpankowski, Average Case Analysis of Algorithms on Sequences [Preprint version]
• Vijay V. Vazirani, Approximation Algorithms [PDF via Prof. Vazirani]
• Herbert S. Wilf, Algorithms and Complexity