CS359A: Research seminar on complexity theory

## General Information

## Seminar description

A research seminar on concrete complexity theory.

We will study powerful and versatile techniques for analyzing basic models of computation — decision trees, DNF formulas, halfspaces, and juntas — and see applications of these techniques to a variety of areas including circuit lower bounds, derandomization, quantum complexity, learning theory, and applied probability.

A major focus of the seminar will be on mapping out the research frontier and developing fruitful research directions. In the final few meetings of the quarter we will tackle research problems together.

We will study powerful and versatile techniques for analyzing basic models of computation — decision trees, DNF formulas, halfspaces, and juntas — and see applications of these techniques to a variety of areas including circuit lower bounds, derandomization, quantum complexity, learning theory, and applied probability.

A major focus of the seminar will be on mapping out the research frontier and developing fruitful research directions. In the final few meetings of the quarter we will tackle research problems together.

## Topics covered

- Decision trees
Query complexity and relationships among complexity measures

Every decision tree has an influential variable

The Aaronson-Ambainis conjecture and the power of quantum computation

P = NP ∩ coNP for decision trees

The sensitivity theorem

- DNF formulas
Random restrictions and switching lemmas

Linial-Mansour-Nisan: Fourier spectrum of DNF formulas

Mansour's conjecture and its implications

Razborov-Smolensky polynomial approximators

Bazzi's theorem: Bounded independence fools DNFs

Fredman-Khachiyan and the monotone dualization problem - Halfspaces
Noise sensitivity of halfspaces

Halfspaces and the Central Limit Theorem

Mossel-O'Donnell-Oleszkiewicz Invariance Principle

The Gotsman-Linial conjecture

Bounded independence fools halfspaces - Juntas
Learning in the presence of irrelevant information

Mossel-O'Donnell-Servedio

Valiant's light bulb problem

__this link__.

## Seminar format

• First few meetings: Li-Yang will give an overview of the topics listed above

• Bulk of the quarter: Student-led deep dives into specific topics and results

• Final few meetings: Research discussions

• Bulk of the quarter: Student-led deep dives into specific topics and results

• Final few meetings: Research discussions

## Evaluation

(Tentative; more details to follow.)

• Discussion lead for 1-2 meetings

• Short summaries of meetings

• Class participation

• Short summaries of meetings

• Class participation

(Seminar meetings will not be recorded.)