Seminář z výpočetní složitosti

Pavel Pudlák, Jiří Sgall

Doba a místo konání

Úmluva na další semestr se koná vždy v rámci hromadné úmluvy KAM v prvním týdnu semestru.

Seminář se koná v MÚ Žitná 25. Budova Matematického ústavu je u křižovatky se Štěpánskou. Projdete průchodem, rovně přes celý dvůr (podél knihovny).

Oznámení o seminářích se distribuuje pomocí mailing listu, do kterého se můžete zapsat na adrese http://list.math.cas.cz/listinfo/complexity-seminar.

Kontakt

sgall@math.cas.cz, http://www.math.cas.cz/~sgall/, tel. 222 090 780;
pudlak@math.cas.cz, http://www.math.cas.cz/~pudlak/, tel. 222 090 721.

Nejbližší program semináře [Next program]

Předběžný připravovaný program semináře [Preliminary future program]

Další články pro tento semestr

Cristopher Moore, Alexander Russell: A simple constant-probability RP reduction from NP to Parity P. ECCC Report TR08-093.

Články zbylé z minulých semestrů

Troy Lee, Adi Shraibman: Disjointness is hard in the multi-party number-on-the-forehead model. CCC'08, also ECCC TR08-003.

Arkadev Chattopadhyay, Anil Ada: Multiparty Communication Complexity of Disjointness. ECCC TR08-002
(Podle informaci z druhe ruky je to temer stejny dukaz jako predchozi clanek, i kdyz ten druhy je mozna o neco kompaktnejsi.)

Harry Buhrman and John M. Hitchcock: NP-hard sets are exponentially dense unless coNP is contained in NP/poly. CCC'08

Clanky od Sherstova - ECCC  (nekolik clanku ohledne discrepancy)

Amit Chakrabarti: Lower Bounds for Multi-Player Pointer Jumping. ECCC TR07-014.

Alexander A. Razborov, Sergey Yekhanin: An Omega(n1/3) Lower Bound for Bilinear Group Based Private Information Retrieval. FOCS'06.

Kontakt

sgall@math.cas.cz, http://www.math.cas.cz/~sgall/, tel. 222 090 780;
pudlak@math.cas.cz, http://www.math.cas.cz/~pudlak/, tel. 222 090 721.

Předchozí program semináře [Past program]