Complexity Theory
CAS CS 535
- Credits:
- 4
- Offered:
- 1st sem.
- Undergraduate Prerequisites:
- CAS CS 332; or consent of instructor.
- Graduate Prerequisites:
- CAS CS 332.
Covers topics of current interest in the theory of computation chosen from computational models, games and hierarchies of problems, abstract complexity theory, informational complexity theory, time-space trade-offs, probabilistic computation, and recent work on particular combinatorial problems.
- Programs
- Departments
- Pardee School of Global Studies
-
Courses
- African American Studies
- African Studies: Culture (in English)
- African Studies: East African Languages: Kiswahili (Swahili)
- African Studies: East, West & South African Languages: Amharic, Igbo, Mandinka, isiZulu
- African Studies: South African Languages: isiXhosa
- African Studies: West African Languages: Hausa
- African Studies: West African Languages: Akan Twi, Wolof
- American Studies
- Anthropology
- Arabic: Language, Literature, Culture (including courses in English)
- Archaeology
- Astronomy
- Biochemistry & Molecular Biology
- Biology
- Chemistry
- Chinese: Language, Literature, Culture (including courses in English)
- Cinema & Media Studies
- Classical Studies: incl. Classical Civilization and Tradition (in English), Ancient Greek, and Latin
- Classical Studies: Modern Greek
- Comparative Literature
- Computer Science
- Core Curriculum
- Earth & Environment
- Economics
- Editorial Studies
- English
- First Year Experience
- French: Language, Literature, Linguistics, Culture (including courses in English)
- German: Language, Literature, Culture (including courses in English)
- Hebrew: Language, Literature, Culture (including courses in English)
- Hindi-Urdu: Language, Literature, Culture (including courses in English)
- History
- History of Art & Architecture
- Interdisciplinary Studies
- International Relations
- Internships
- Italian: Language, Literature, Culture (including courses in English)
- Japanese: Language, Literature, Culture (including courses in English)
- Jewish Studies
- Korean: Language, Literature, Culture (including courses in English)
- Linguistics
- Literary Translation
- Marine Science
- Mathematics & Statistics
- Natural Sciences
- Neuroscience
- Persian (Farsi): Language, Literature, Culture (including courses in English)
- Philosophy
- Physics
- Political Science
- Portuguese: Language, Literature, Culture (including courses in English)
- Psychological & Brain Sciences
- Religion
- Russian: Language, Literature, Culture (including courses in English)
- SEA Semester
- Senior Year Development
- Sociology
- Spanish: Language, Literature, Culture (including courses in English)
- Turkish: Language, Literature, Culture (including courses in English)
- Women’s, Gender & Sexuality Studies
- Writing
- Policies
- Academic and Student Resources
- Honor Societies
- Student Activities
Addendum
For programs that received approval after this Bulletin was published, please see the Addendum

