The intrinsic complexity of computational problems will be studied, with an emphasis on communication questions and quantum computing. Topics to be explored include complexity theories for multiparty communications, probabilistic communications, quantum communications, quantum circuits, etc. Other subjects to be investigated include various complexity questions for algebraic decision trees. It is expected that techniques from combinatorics, probability theory, and topology will provide the main mathematical tools for this project.
