🚀 go-pugleaf

Lecture Series ``Collegium Logicum''
Kurt Goedel Society
University of Technology, Vienna, Austria


Lecture Announcement
--------------------

Jan Krajicek
=============
Czech Academy of Sciences

		
Recent Developments in Propositional Logic 
and Bounded Arithmetic 
(Short Course)
------------------------------
Monday, May 22 -- Friday, May 26



 Part I.: Efective Interpolation
 -------------------------------

 1. Effective interpolation theorems for
    resolution and cutting planes.

 2. Lower bounds for resolution and cutting
    planes via the effective interpolation.

 3. Some consequences of cryptographical
    conjectures for effective interpolation
    and related open problems.

 Part II.: Applications of Elementary
           Algebraic Geometry
 -------------------------------------------

 4. Independence of modular counting principles
    in constant-depth Frege systems.

 5. Equational proof systems and related open
    problems.

 Part III.: Bounded Arithmetic (if time permits)
 -----------------------------------------------

 6. Independence results for bounded arithmetic:
    definability of search problems, unprovability
    of circuit size lower bounds.


 Selected references:
 -------------------

[1] P. Beame, R. Impagliazzo, J. Krajicek, T. Pitassi and
P.Pudl\'{a}k: "Lower bounds on Hilbert's Nullstellensatz and
propositional proofs", Proceedings of the London
Mathematical Society, (1994), submitted.

[2] M. Chiari and J. Krajicek : "Witnessing functions in
bounded arithmetic and search problems", J. of Symbolic
Logic, (1994), submitted.

[3] J. Krajicek:  "Interpolation theorems, lower bounds for
proof systems, and independence results for bounded arithmetic",
J. of Symbolic Logic, (1995), submitted.

[4] J. Krajicek: "Bounded arithmetic, propositional logic and
complexity theory", {\em Cambridge University Press},
a monograph to appear in 1995.

[5] J. Krajicek and  P. Pudl\'{a}k: "Some consequences
of cryptographical conjectures for $S^1_2$ and $EF$",
Proc. of the meeting {\em Logic and Computational Complexity},
Indianapolis (October 1994), (1995), to appear.


Place and Date: 

The first meeting will be at the Seminarraum SEM 181A des 
Instituts fuer Informationssysteme, Paniglgasse 16, 1040~Wien,
 1.Stock, on Monday, May 22, 16:45. Time and place of
the other lectures will be defined and communicated there.

------------------------
Kurt-Goedel-Gesellschaft
Technische Universitaet Wien
Institut fuer Computersprachen E185.2
Resselgasse 3/1, A-1040 Wien

Tel: (+43 1) 588 01/4088
Fax: (+43 1) 504 15 89
email: kgs@logic.tuwien.ac.at

Mit Unterstuetzung des
Bundesministeriums fuer Wissenschaft und Forschung