Fall school

of the Logic seminar at the Mathematical Institute

Pec p. Snezkou 2003

Earlier mini-conferences: Pec'99 and Pec'00 , and Fall schools Pec'01 and Pec'02.

Information about the Fall school: krajicek@math.cas.cz.

Usefull information for foreign visitors of the country.


Chata UK (pension VAK) - pension of the Charles University
Mala plan 159
542 21, Pec pod Snezkou


September 14.-20, 2003 (arrival Sunday 14. - departure Saturday 20.).


We will have three tutorials during the first four days (Mon-Thu). The themes and the speakers are:

  • PCPs and Inapproximability
    Lecturer: Johan Hastad (Stockholm)

  • Proof mining
    Lecturer: Ulrich Kohlenbach (Aarhus)

  • Recent topics in (or relevant to) propositional proof complexity and bounded arithmetic,
    Part 1: Godel's theorem in Bounded Arithmetic , lecturer: P. Pudlak (Prague)
    Part 2:Strong proof systems and hard tautologies , lecturer: J. Krajicek (Prague)

    Friday was devoted to lectures of participants on their own work:


    O. Beyersdorff: A strong reduction between disjont NP-pairs
    G. Fereira: Systems of weak analysis and the hierarchy of counting functions
    J.Hanika: Investigating bounded arithmetic using search problems
    L. Kolodziejczyk: A property of bounded query classes within N^{NP}
    D. Kral: Edge-disjoint odd cycles in planar graphs
    M.Pergel: Complicacy of PC^* graphs
    Z.Sadowski: On a D-N-optimal acceptor for TAUT
    R. Spalek: Quantum computation and quantum circuits
    K.Zdanowski: Properties of arithmetics in finite models

    There was plenty of time for informal program and for walks in surrounding beautiful countryside - Pec is in mountains Krkonose ( The Giant Mountains) on the north border of the country.

    Accommodation and board

    Accommodation is in double rooms with own bathroom.

    We shall pay a part of expenses of students (from our grants and from a grant of the Institute of Theoretical Computer Science).
    The price will be at most 10 USD (or 100 CZK for Czech students) per day for full board. We hope to lower this upper bound yet somewhat. The discrepancy in upper bounds on the price for Czech students and others is due to the fact that some grants can be used only for Czech citizens.

    We shall collect the payment during the meeting.


    If you are interested to come, please write me. Everybody is, in principle, welcome to participate. Graduate students have priority. We are limited somewhat by space.

    Participants registered so far

    from Prague:

    Marta Bilkova, Jirka Hanika, Jan Henzl, Emil Jerabek, Jan Krajicek, Daniel Kral, Martin Pergel, Pavel Pudlak, Jirka Sgall, Antonin Sochor, Tomas Tichy.

    and from elsewhere:

    Olaf Beyersdorff (Berlin), Stefano Cavagnetto (Milano), Gilda Ferreira (Lisbon), Annelies Gerber (Tours), Johan Hastad (Stockholm), Ulrich Kohlenbach (Aarhus), Leszek Kolodziejczyk (Warsaw), Zenon Sadowski (Bialystok), Robert Spalek (Amsterdam), Konrad Zdanowski (Warsaw).

    Some practical info for the participants.