Home

Семинар 23 февраля 2007 года

Пятница, 23 февраля, комната 106. Начало в 16:00.

Докладчик: А. Куликов.

Тема: Миникурс по сложности формул и схем. Первая лекция.

Abstract

Предварительная программа всего миникурса:

Сложность формул:

  1. Introduction. Motivation, Shannon's theorem, communication complexity, Karchmer-Wigderson games, covering by rectangles.
  2. General Lower Bound Methods.
    3. Nechiporuk's method, Krapchenko's method, Hodes and Specker's method, Fischer, Meyer and Paterson Method.
  3. Formula Complexity of Majority Function Valiant's proof of $ n^{5.3} $ upper bound for majority, main ideas of Paterson and Zwick's proof of $ n^{4.57} $ upper bound, trivial $ n^2 $ lower bound.
  4. Formula Complexity of Threshold Functon Wegener's proof of nlogn lower bound for threshold-2, Radhakrishnan's proof of $ nk*log{n/k} $ lower bound for threshold-k,n, Friedman's proof of nlogn upper bound for threshold.
Сложность схем:
  1. Introduction. Motivation, main open problems, linear lower bounds for threshold and XOR.
  2. Lower Bounds for Monotone Circuits Razborov's theorem.
  3. Bounded Depth Circuits.
  4. Lower and Upper Bounds for st-Connectivity.