Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR13-182 | 20th December 2013 16:22

Structure vs Combinatorics in Computational Complexity

RSS-Feed




TR13-182
Authors: Boaz Barak
Publication: 20th December 2013 16:23
Downloads: 4660
Keywords: 


Abstract:

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 classification and its connections to phase transitions, average-case complexity, quantum computing and cryptography.



ISSN 1433-8092 | Imprint