6 ms·
Disclaimer: I have no clue of a complete learning path. But here are some suggestions you might find interesting. If you want to go heavy on complexity, you c
by eru 2y ago
Disclaimer: I have no clue of a complete learning path. But here are some suggestions you might find interesting.
If you want to go heavy on complexity, you could try 'Combinatorial Optimization: Polyhedra and Efficiency' by Alexander Schrijver. But it's basically the equivalent of Knuth's Art of Computer Programming for complexity (in terms of rigour and breadth of approach).
I have the three volumes of Schrijver's book on my desk, and even occasionally look into them. But I admit I never read the whole thing. I love the historical context he gives, eg explaining how maximum flow / minimum cut problems were first formally investigated in the Cold War when Western boffins wanted to work out how to most efficiently cut the Soviet rail network's ability to move stuff to Western Europe.
If you want something much lighter, you could check out some of Scott Aaronson's backlog. Eg https://www.scottaaronson.com/papers/philos.pdf https://www.scottaaronson.com/papers/philos.pdf 'Why Philosophers Should Care About Computational Complexity'. You can follow his bibliography for more background. Scott's blog backlog is also good.
If you like randomised algorithms, you might also like 'The Discrepancy Method
Randomness and Complexity' by Bernard Chazelle. It's available for free online. Eg at https://api.pageplace.de/preview/DT0400.9781316047804_A25932634/preview-9781316047804_A25932634.pdf https://api.pageplace.de/preview/DT0400.9781316047804_A25932...
Apropos Bernard Chazelle, I'm working on a little paper myself. It's about how to simulate the outcome of a series of heap operations (like insert and delete-minimum) in O(n) time, instead of the trivial to achieve O(n log n) you get from a naive implementation. I'm looking for some collaborators, if you are interested.