Structure vs Combinatorics in Computational Complexity
Boaz Barak · Bulletin of the European Association for Theoretical Computer Science · 2013
Some computational problems seem to have a certain \structure that is manifested in non-trivial algorithmic properties, while others are more \unstructured in the sense that they are either \very easy or \very hard. I survey some of the known results and open questions about this classication and its connections to phase transitions, average-case complexity, quantum computing and cryptography.