CSE 719: Complexity Via Succinctness
This page refers to the Fall 2011 offering of CSE 719 only. The information on this page does not necessarily apply to every offering of CSE 719.
Fall 2011
33011
Theoretical computer science, computational complexity theory, Kolmogorov complexity, algorithms.
The distinctive point of this seminar will be to explore the role of limiting exponential-size objects to have polynomial-size descriptions, which is our particular notion of /succinctness/. This condition can be applied to a variety of complexity topics, and has driven some important recent work. For example: 1. Impagliazzo-Kabanets-Wigderson (2002) showed that EXP in P/poly implies that every succinct exp-sized satisfiable formula has a succinct satisfying assignment. This is an important step in Ryan Williams' recent breakthrough lower bounds for NEXP against ACC^0. 2. Maurice Jansen and Rahul Santhanam have an ICALP 2011 paper demonstrating that succinct constant-depth arithmetical circuits (with bounded coefficients) cannot compute the permanent function. 3. Quantum (pure) states on n qubits are 2^n-sized vectors, but many of them are succinct, and some substantial classes of quantum circuits preserve succinctness. The notion of succinctness can be applied more widely than this. S/U grading will be based on student participation, presentation of topical papers with some creative thought about succinctness, and some blogging/scribing.
CSE596, or an undergraduate theory course like CSE396 that included the basics of complexity theory. See instructor for queries.
Ph.D.: This course does not fulfill core area or core course requirements.
M.S.: This course does not fulfill core area or core course requirements.
