Złożoność Obliczeniowa (Seminarium)

 

Tematy (i źrodła)

¡      Temat 1: Języki McNaughtona (A.Jeż)

·           M.Beaudry, M.Holzer. G.Niemann, F.Otto, McNaughton Languages

·           http://www.theory.informatik.uni-kassel.de/~otto/

¡      Temat 2: Algorytmy kwantowe (rez.: A.Mądry: Slajdy)

·           P. Shor, Polynomial-Time Algorithms for Prime Factorization and Discerete Logarithms on a Quantum Computer

·           Materiały pomocnicze:

i.           S.A.Fenner, A Physics-Free Introduction to the Quantum Computation Model

ii.       D.Aharonov, Quantum Computation

¡      Temat 3: Złożoność deterministycznych języków bezkontekstowych

·           S.Cook, Deterministic CFL's are accepted simultaneously in polynomial time and log squared space

¡      Temat 4: Kompresja przy pomocy gramatyk (rez.: J.Otop: Slajdy)

·           W.Rytter,  Applications of Lempel-Ziv factorization to the approximation of grammar-based compression

·           E.Lehman, Approximation Algorithms for Grammar-Based Data Compression

·           M.Charikar, E.Lehman, D.Liu, R.Panigrahy, M.Prabhakaran, A.Rasala, A.Sahai, A.Shelat, Approximating the Smallest Grammar: Kolmogorov Complexity in Natural Models

¡      Temat 5: Rosnące języki kontekstowe

·           E.Dahlahus, M.Warmuth, Membership for Growing Context Sensitive Grammars is Polynomial

¡      Temat 6: Problem spójności grafów nieskierowanych (A.Jeż: Slajdy)

·           N.Nisan, E.Szemeredi, A.Wigderson, Undirected Connectivity in O(log^1.5 n) Space

¡      Temat 7: Deterministyczna symulacja obliczeń zrandomizowanych z LOGSPACE (A.Wasylkowski: Slajdy)

·           N.Nisan, RL in SC

¡      Temat 8: Ograniczony niedeterminizm (rez.: J.Straszewski)

·           U.Feige, J.Kilian, On Limited versus Polynomial Nondeterminism

¡        Temat 9: Problem spójności grafów nieskierowanych cz.II (M.Wrona)

·           O.Reingold, Undirected ST-Connectivity in Log-Space

·           Materiały pomocnicze:

i.           V.Trifonov, An O(log n loglog n) Space Algorithm for Undirected s,t-Connectivity

ii.         M.Koucky, Universal Traversal Sequences with backtracking

¡        Temat 10: Hierarchie czasowe dla obliczeń probabilistycznych

·           L.Fortnow, R.Santhanam, Hierarchy Theorems for Probabilistic Polynomial Time

·           Materiały pomocnicze:

i.           B.Barak, A Probabilistic-Time Hierarchy Theorem for "Slightly Non-Uniform" Algorithms

ii.         O.Goldreich, M.Sudan, L.Trevisan,  From logarithmic advice to single-bit advice

¡        Temat 11: „Zgadywanie sekretów”

·           A.Razborov, Guessing more secrets via list decoding

·           Materiały pomocnicze:

i.           F.Chung, R.Graham, T.Leighton, Guessing secrets

ii.         N.Alon, V.Guruswami, T.Kaufman, M.Sudan, Guessing secrets efficiently via list decoding

 

 

 

Komunikaty

·           20 października (środa) na seminarium ZZOiAA (godz. 14-16) będziemy gościć prof. Friedricha Otto z Uniwersytetu Kassel.

·           Powyższą listę propozycji tematów będę sukcesywnie uzupełniał. Kolejność prezentowania tematów na seminarium nie jest implikowana kolejnością liście (oczywiście poza pierwszym tematem)

·           22 października na seminarium wystąpi prof. F.Mraz z Pragi. Temat odczytu: Learning Analysis by Reduction.