JT3382 Analys av Booleska funktioner 7,5 hp

Analysis of Boolean Functions

  • Utbildningsnivå

    Forskarnivå
  • Huvudområde

  • Betygsskala

    P, F

Kurstillfällen/kursomgångar

HT18 för programstuderande

  • Perioder

    HT18 P2 (7,5 hp)

  • Anmälningskod

    51778

  • Kursen startar

    2018-10-29

  • Kursen slutar

    2019-01-14

  • Undervisningsspråk

    Engelska

  • Studielokalisering

    KTH Campus

  • Undervisningstid

    Dagtid

  • Undervisningsform

    Normal

  • Antal platser

    Ingen begränsning

Lärandemål

Efter genomgången kurs ska studenten kunna:

-Använda Fouriertransformen av booleska funktioner.

-Bevisa norm-olikheter och isoperimetriska satser for booleska funktioner.

-Analysera booleska funktioner via reelI analys och invarians-principer.

-Använda Fourieranalys av booleska funktioner for att losa problem inom tillämpningsområden inom teoretisk datalogi.

-Presentera forskningsartiklar inom analys av booleska funktioner eller något av dess tillämpningsområden.

Kursens huvudsakliga innehåll

-Fouriertransformen av en boolesk funktion

-Norm-olikheter, hyperkontraktivitet, isoperimetriska olikheter

-Analys av funktioner i gaussiskt rum, invarians-principer

-Tillämpningar inom datalogin

Kursupplägg

  • Undervisningssrpåk: Engelska

Behörighet

  • Förkunskapskrav: Linjär algebra

Litteratur

“Analysis of Boolean Functions" av Ryan O'Donnell samt forskningsartiklar

Examination

  • EXA1 - Examination, 7,5, betygsskala: P, F
  • Undervisningssrpåk: Engelska
  • Betygsskala: P/F

Krav för slutbetyg

Godkännt betyg på examinationsmoment som består av hemuppgifter och presentation av forskningsartikel.

Ges av

EECS/Teoretisk datalogi

Examinator

Johan Håstad <johanh@kth.se>

Versionsinformation

Kursplan gäller från och med VT2018.
Examinationsinformation gäller från och med VT2019.