Special Topics Course: Computational Complexity Theory

BK: Conclusion and future directions.

DC (DD): Descriptive complexity conclusion.

CC (GV): Data structure lower bounds from communication complexity.

AC (BK): Brent's formula depth reduction.

AC (BK): VF-completeness of Narayana's cows polynomials.

AC (RN): VP0 and VNP0. Connections to integer computation.

AC (GS): Shamir's O(log(n)) computation of factorial using arithmetic operations with integer divide.

DC (DD): FO queries, "reduction" from connected-ness to reachability using FO.

AC (RN): Computing numbers, complexity upper and lower bounds. Factorial.

CC (GV): Asymmetric communication complexity. k-subsets vs all subsets disjointedness.

BK: Ryser's formula for permanent.

AC (GS): Baur-Strassen Theorem.

AC (GS): Division elimination, computing partial derivatives.

DC (SN): Interpretation, free variables, validity of formulas under interpretations.

CC (GV): Lower bound methods for deterministic cc: Fooling sets.

SC (BK): NC and AC classes. Addition in AC0. Regular languages in NC1.

AC (RN): Homogenization lemma, division elimination using truncated series.

DC (DD): Vocabulary for strings. FO formulas for addition.

CC (GV): Balancing protocol trees to log(number of leaves)-depth. Protocol from matrix decomposition that is not a protocol.

SC (BK): Non-uniform models, Boolean circuits, Does SAT have small circuits? Karp-Lipton theorem.

CC (GV): Definition of deterministic communication complexity, protocol trees, matrix decompositions, combinatorial rectangles, and f-monochromatic rectangles. Lower bound for equality using combinatorial rectangles.

AC (RN): Definitions of determinant, permanent, circuits, formulas, ABPs and IMM. Poly-size circuits and ABPs (via IMM) for elementary symmetric polynomials (recurrence).

DC (DD): Vocabulary, structures, first-order formulas. Example: Vocabulary for directed graphs with designated source and sink. FO formula for undirected graphs and no loops.

We discussed interactive proofs and saw one for the "Graph Non-Isomorphism" problem. We decided on the topics split for future discussions. Also, a 6-hour per-week work schedule is set for each student.

We discussed the implications of SAT is in P. A poly-time algorithm for SAT would imply poly-time algorithms for, given any fixed number of alternating quantifiers, checking whether a given quantified Boolean formula with that many alternating quantifiers is true or false. Notice that this problem is much more general than SAT. The class of problems poly-time, many-one reducible to any of these generalizations of SAT is called PH.

I presented an overview of various specialized topics in computational complexity theory.