Logic seminar: archive since 1995

1995

  • S. Riis (Aarhus)
    Symmetrical equations -> symmetrical solutions?

    1996

  • A. Woods (Australia)
    Random finite functions -- standard and nonstandard
    January 4, 1996

  • J. Hruska (Charles University)
    Open-point a Open-open hry na regularnich topologickych prostorech a jejich ekvivalenty na Booleovskych algebrach
    March 25, 1996

  • Dan Willard (SUNY, Albany)
    Introspective Semantics for Turing Machine Languages
    March 4, 1996

  • Yuri Gurevich (Ann Arbor)
    Finite model theory
    June 17, 1996

  • Stevo Todorcevic (Toronto)
    Borel chromatic numbers
    July 10, 1996

  • L. van den Dries (Urbana)
    O-minimal extensions of R and quantifier elimination with Exp
    July 15, 1996

  • A. Sochor (MU)
    Nestandartnost nadmodelu
    September 16, 1996

  • A. Sochor (MU)
    Nestandartnost nadmodelu II.
    September 30, 1996

  • A. Sochor (MU)
    Nestandartnost nadmodelu III.
    October 7, 1996

  • P. Pudlak (MU)
    O Dawkingskove knize "Selfish gene"
    October 21, 1996

  • J. Krajicek (MU)
    Forcing v jazyce teorie miry
    November 11, 1996

  • J. Krajicek (MU)
    Spodni odhad pro polynomialni kalkulus podle A.A.Razborova
    December 2, 1996

    1997

  • J. Krajicek & P. Pudlak (MU)
    Nove poznatky o polynomialnim kalkulu (dle Razborova) a o variacich systemu "cutting planes" (dle Lovasze-Schrijvera)
    January 6, 1997

  • J. Krajicek (MU)
    Razborovuv dukaz spodniho odhadu pro polynomialni kalkulus
    January 13, 1997

  • J.-P.Ressayre (Paris 7 & CNRS)
    Applications of transfinite series to integers and reals
    January 16, 1997

  • J. Krajicek (MU)
    Spodni odhad pro polynomialni kalkulus II.
    January 27, 1997

  • P. Hajek (UIVT)
    Fuzzy predikatove logiky - soucasny stav oboru
    February 10, 1997

  • Jui-Lin Lee (host MU)
    Counting technique inside NC^1
    February 17, 1997

  • P. Pudlak
    Is Godel theorem applicable to human thinking?
    February 24, 1997

  • J. Witzany (Charles University)
    Konstrukce a aplikace vnitrnich modelu (Czech)
    March 17, 1997

  • P. Vojtas (Kosice)
    Logicke metody studia asymptotickeho chovani a znalostnych systemu s neurcitosti
    May 19, 1997

  • J. Krajicek
    Lower bound for F_d(MOD_p)
    December 1, 1997

  • J. Krajicek
    Euler structures
    December 15, 1997

    1998

  • A. Voronkov (Uppsala)
    Herbrand's theorem, automated deduction and semantic tableaux
    February 2, 1998

  • J. Krajicek
    Permutation modules and their applications to proof theory I. - IV.
    starting March 30, 1998 (12.oo - 14.oo)

  • T. Jech (Penn State)
    Mechanical proofs, combinatorial logic, and Quine's set theory
    November 27, 1998 at 10.oo

    1999

  • P. Pudlak (MU)
    Complexity of intuitionistic propositional logic
    January 8, 1999 at 10.oo

  • J.Stepanek
    Interpretation of RA in a weak set theory
    March 29, 1999 at 13.oo

  • J.Krajicek
    Forcing, resolution, bounded arithmetic I.
    April 19, 1999 at 13.oo

  • J.Krajicek
    Forcing, resolution, bounded arithmetic II.
    April 26, 1999 at 13.oo

  • P.Jirku (FF UK)
    A remark on many-valued logics of missing information
    May 10, 1999 at 13.oo

  • J.Krajicek
    Amalgamation (and a bit of stability)
    May 17, 1999 at 13.oo

  • K.Bendova (FF UK)
    Arithmetic without addition
    May 24, 1999 at 13.oo

  • P.Hajek (UIVT)
    Arithmetic complexity of fuzzy predicate logics
    June 14, 1999 at 13.oo

  • P.Vanousek (NEON/CAI Prague)
    Automated theorem proving
    June 21, 1999 at 13.oo

  • T. Pitassi (U. of Arizona)
    Binomial Ideals, the Polynomial Calculus and Resolution Width
    June 28, 1999 at 13.oo

  • P. Pudlak
    Large cardinals I.
    October 4, 1999 at 13.oo

  • P. Pudlak
    Large cardinals II.
    October 11, 1999 at 13.oo

  • P. Pudlak
    Large cardinals III.
    November 1, 1999 at 13.oo

  • A. Sochor
    Quantifier elimination in arithmetic
    November 8, 1999 at 13.oo

  • J. Krajicek
    Combinatorics with definable sets
    (Side notes : a proof of WPHP by Maciel-Pitassi-Woods.)
    November 15, 1999 at 13.oo

  • A. Sochor
    Saturated structures and good ultrafilters
    November 22, 1999 at 13.oo

  • A. Sochor
    Continuation from 22.XI.99
    Large cardinals IV.
    November 29, 1999 at 13.oo

  • J. Krajicek
    Large cardinals V.
    December 6, 1999 at 13.oo

  • J. Krajicek
    Large cardinals VI. (axiom of determinacy)
    December 13, 1999 at 13.oo

    2000

  • L.Behounek
    Kunen's barrier
    January 10, 2000 at 13.oo

  • L.van den Dries
    Hardy fields
    January 14, 2000 at 14.45

  • B.Balcar
    Exhaustive structures on boolean algebras
    February 21, 2000 at 13.oo

  • P.Pudlak
    Quine's set theory NF (New Foundations)
    February 28, 2000 at 13.oo

  • P.Pudlak
    Scott's model for Lambda calculus
    March 6, 2000 at 13.oo

  • J.Krajicek
    Descriptive set theory - introduction
    March 13, 2000 at 13.oo

  • J.Krajicek
    Descriptive set theory II.
    March 20, 2000 at 13.oo

  • J.Krajicek
    Descriptive set theory III.
    March 27, 2000 at 13.oo

  • Lev Beklemishev (Vienna)
    Rules and parameter-free schemata in arithmetic
    March 30, 2000 at 13.3o

  • J.Krajicek
    Abstract dimension theory in model theory and in arithmetic
    April 17, 2000 at 13.oo

  • P.Pudlak
    Linear logic - semantics and syntax
    May 15, 2000 at 13.oo

  • P.Pudlak
    Linear logic - continuation
    May 22, 2000 at 13.oo

  • R. Impagliazzo (UC S.Diego)
    Can we encrypt programs?
    July 7, 2000 at 10.3o

  • J. Krajicek
    Geometric model theory I.
    (after Zilber's notes "Elements of geometric stability")
    October 23, 2000 at 13.oo

  • J. Krajicek
    Geometric model theory II.
    October 30, 2000 at 13.oo

  • J. Krajicek
    Geometric model theory III.
    November 6, 2000 at 13.oo

  • J. Krajicek
    Geometric model theory IV.
    November 13, 2000 at 13.oo

    2001

  • A.Sochor
    Unprovability of Goodstein's theorem
    January 15, 2001 at 13.oo

  • P.Pudlak
    Parallel strategies for finite and infinite games
    January 22, 2001 at 13.oo

  • A.Sochor
    Unprovability of Goodstein's theorem II.
    January 29, 2001 at 13.oo

  • A.Sochor
    Unprovability of Goodstein's theorem III.
    February 5, 2001 at 13.oo

  • Michal Rossler
    A fragment of non-standard analysis whose consistency can be proved in a finitary way I.
    (A reference: R.Chuaqui, P.Suppes, Free-Variable Axiomatic Foundations of Infinitesimal Analysis - A Fragment with Finitary Consistency Proof, The Journal of Symbolic Logic, March 1995.)
    February 19, 2001 at 13.oo

  • Michal Rossler
    A fragment of non-standard analysis whose consistency can be proved in a finitary way II.
    February 26, 2001 at 13.oo

  • Michal Rossler
    A fragment of non-standard analysis whose consistency can be proved in a finitary way III.
    March 12, 2001 at 13.oo

  • Michal Rossler
    A fragment of non-standard analysis whose consistency can be proved in a finitary way IV.
    March 19, 2001 at 13.oo

  • J.Krajicek
    Word problem in groups and Dehn function
    April 2, 2001, at 13.00

  • D.Therien (Montreal)
    Definability of regular languages in first-order logic

    Abstract: First-order logic offers a convenient framework to describe regular languages. I will present old and new results about the model: in particular, deep connections with algebra will be emphasized.
    April 9, 2001 at 13.oo

  • P.Pudlak
    On disjoint pairs of NP sets and propositional proof systems
    April 23, 2001, at 13.00

  • J.Makowsky (Technion, Haifa)
    Algorithmic aspects of the Feferman-Vaught Theorem
    Abstract
    May 14, 2001, at 13.00

  • P.Pudlak
    On communication complexity of a problem about subword occurences
    October 15, 2001, at 13.oo

  • J.Krajicek
    Open problems on the border of mathematical logic and complexity theory I.
    October 22, 2001 at 13.oo

  • P.Pudlak
    Hindman's theorem and its application
    (a loose continuation of the seminar from 15.10.01)
    October 29, 2001, at 13.oo

  • P.Hajek
    Mathematical fuzzy logic - current state of art
    November 5, 2001 at 13.oo

  • J.Krajicek
    Open problems on the border of mathematical logic and complexity theory II.
    November 12, 2001 at 13.oo

  • P.Pudlak
    Hindman's theorem and its application II.
    November 26, 2001 at 13.oo

  • J.Krajicek
    Holographic proofs
    December 3, 2001 at 13.oo

  • M.Rossler
    Locally finite theories
    (after J.Mycielski)
    December 10, 2001 at 13.oo

    2002

  • J.Urban (MFF UK)
    Proof checking, system Mizar
    January 28, 2002 at 13.oo

  • A.Kucera (MFF UK)
    Randomness from the recursion theory point of view I.
    February 25, 2002 at 13.oo

  • A.Kucera (MFF UK)
    Randomness from the recursion theory point of view II.
    March 4, 2002 at 13.oo

  • J.Krajicek
    Games, forcing, arithmetic
    March 11, 2002 at 13.oo

  • M.Rossler
    A fragment of non-standard analysis whose consistency can be proved in a finitary way - new version I.
    March 18, 2002 at 13.oo

  • M.Rossler
    A fragment of non-standard analysis whose consistency can be proved in a finitary way - new version II.
    March 25, 2002 at 13.oo

  • E.Jerabek
    An interpretation of a fragment of non-standard analysis in a fragment of PA and vice versa
    April 8, 2002 at 13.oo

  • A.Sochor
    Combinatorics in L, part I.
    April 15, 2002 at 13.oo

  • A.Sochor
    Combinatorics in L, part II.
    April 22, 2002 at 13.oo

  • A.Sochor
    Combinatorics in L, part III.
    April 29, 2002 at 13.oo

  • A.Sochor
    Combinatorics in L, part IV.
    May 6, 2002 at 13.oo

  • T.Jech
    Stacionary sets of countable models
    May 13, 2002 at 13.oo

  • M.Bilkova
    Feasible disjunction and interpolation properties in modal logic S4
    May 27, 2002 at 13.oo

  • M.Klazar (Charles U.)
    Primes are in P
    (after Manindra Agrawal, Neeraj Kayal and Nitin Saxena).
    October 7, 2002 at 13.oo

  • M.Rossler
    Slaman's solution of Paris's problem on the axiomatization of PA
    October 21, 2002 at 13.oo

  • J.Krajicek
    Model-theoretic forcing I.
    November 4, 2002 at 13.oo

  • J.Krajicek
    Model-theoretic forcing II.
    November 11, 2002 at 13.oo

  • J.Krajicek
    Model-theoretic forcing III.
    November 18, 2002 at 13.3o

  • J.Hanika
    Forcing in proof theory I.: Elimination of Skolem functions
    (after J.Avigad)
    November 25, 2002 at 13.oo

  • J.Hanika
    Forcing in proof theory II.: Elimination of Skolem functions cont.
    (after J.Avigad)
    December 2, 2002 at 13.oo

  • M.Bilkova
    Forcing in proof theory III.: Relations with intuitionistic logic
    December 9, 2002 at 13.oo

  • M.Bilkova
    Forcing in proof theory IV.: Interpretability of theories
    December 16, 2002 at 13.oo

    2003

  • A.Sochor
    Permutation models and forcing I.
    February 17, 2003 at 13.oo

  • Pascal Tesson (Montreal)
    Complete classifications for the communication complexity of regular languages
    (joint work with Denis Therien). Abstract.
    February 24, 2003 at 13.oo

  • Marta Bilkova
    Forcing and cut elimination
    (after J.Avigad)
    March 3, 2003 at 13.oo

  • A.Sochor
    Permutation models and forcing II.
    March 10, 2003 at 13.oo

  • A.Sochor
    Permutation models and forcing III.
    March 17, 2003 at 13.oo

  • M.Rossler
    Interpretations of weak nonstandard theories via forcing I.
    (after J.Avigad)
    March 24, 2003 at 13.oo

  • A.Beckmann (TU Wien)
    Separations of constant depth LK
    March 28, 2003 at 14.oo

  • M.Rossler
    Interpretations of weak nonstandard theories via forcing II.
    March 31, 2003 at 13.oo

  • J.Krajicek
    Independence of the CH via focing with random variables
    April 7, 2003 at 13.oo

  • R.Honzik
    Jensen's fine structure for L
    April 14, 2003 at 13.oo

  • R.Honzik
    Jensen's fine structure for L, cont.'
    April 28, 2003 at 13.oo

  • E.Jerabek
    Dual WPHP, boolean complexity, and derandomization I.
    May 5, 2003 at 13.oo

  • E.Jerabek
    Dual WPHP, boolean complexity, and derandomization II.
    May 12, 2003 at 13.oo

  • J.Marikova
    Geometric properties of definable sets
    May 19, 2003 at 13.oo

  • P.Pudlak
    Combinatorial principles and computational problems based on finite games
    May 26, 2003 at 13.oo

  • J.Krajicek
    Implicit proofs
    October 6, 2003 at 13.oo

  • J.Hanika
    Search problems I.
    October 13, 2003 at 13.oo

  • J.Hanika
    Search problems II.
    October 20, 2003 at 13.oo

  • J.Hanika
    Search problems III.
    November 3, 2003 at 13.oo

  • M.Navara (CVUT)
    (Non)compatibility in quantum logic
    November 10, 2003 at 13.oo

  • J.Hanika
    Search problems IV.
    November 24, 2003 at 13.oo

  • P.Pudlak
    Games and consistency - a search for new combinatorial principles I.
    December 8, 2003 at 13.oo

  • P.Pudlak
    Games and consistency - a search for new combinatorial principles II.
    December 15, 2003 at 13.oo

    2004

  • P.Pudlak
    Classical tautology that is not a tautology of quantum logic
    (after Kochen-Specker)
    February 23, 2004 at 13.oo

  • E.Jerabek
    Counting quantifiers and bounded arithmetic in a 3-valued logic
    March 22, 2004 at 13.oo

  • T.Jech
    On a problem of von Neumann and Maharam
    April 19, 2004 at 13.oo

  • J.Krajicek
    Ramsey's theorem and PHP
    April 26, 2004 at 13.oo

  • P.Hrubes
    The truth and the definability in the standard model of arithmetic I.
    May 3, 2004 at 13.oo

  • P.Hrubes
    The truth and the definability in the standard model of arithmetic II.
    May 10, 2004 at 13.oo

  • P.Hajek
    On arithmetic in the Cantor-Lukasiewicz fuzzy set theory
    May 17, 2004 at 13.oo

  • R.Honzik
    Shoenfield's theorem on absoluteness of Sigma^1_2 relations in Baire space
    May 24, 2004 at 14.oo

  • Denis Therien (McGill Univ., Montreal)
    First Order Logic and Circuit Lower Bounds
    July 19, 2004 at 14.3o

  • Kerry Ojakian
    Combinatorics in bounded arithmetic
    October 4, 2004 at 13.oo

  • Andres Cordon-Franco
    Fragments of arithmetic with extensions of bounded complexity I.
    October 11, 2004 at 13.oo

  • Andres Cordon-Franco
    Fragments of arithmetic with extensions of bounded complexity II.
    October 18, 2004 at 13.oo

  • Valentine Kabanets (Simon Fraser University)
    Chernoff-type Direct Product Theorems
    October 25, 2004 at 13.oo

  • Antonina Kolokolova
    Systems of bounded arithmetic from descriptive complexity
    November 1, 2004 at 13.oo

  • Marta Bilkova
    Uniform interpolation for modal logic K
    November 8, 2004 at 13.oo

  • Pavel Hrubes
    Transfinite hierarchies of degrees I.
    November 15, 2004 at 13.oo

  • Pavel Hrubes
    Transfinite hierarchies of degrees II.
    November 22, 2004 at 13.oo

  • Andres Cordon-Franco
    Conservation results for parameter free systems of Arithmetic
    November 29, 2004 at 13.oo

  • Stefano Cavagnetto
    Kreisel's conjecture: a survey
    December 6, 2004 at 13.oo

    2005

  • Petr Hajek
    A non-arithmetical Godel logic
    February 28, 2005 at 13.oo

  • Emil Jerabek
    Impagliazzo-Kapron theory
    March 7, 2005 at 13.oo

  • Radek Honzik
    Coding large objects by reals
    March 14, 2005 at 13.oo

  • Pavel Pudlak
    Basic structures appearing in quantum logic
    April 4, 2005 at 13.oo

  • Pavel Pudlak
    Proof systems for ortho-logic
    April 11, 2005 at 13.oo

  • Vitezslav Svejdar (FF UK)
    Interplay of Quantifiers in Godel-Dummett Fuzzy Logics
    April 18, 2005, at 13.oo

  • Pavel Hrubes
    A principle in arithmetical definability and its application
    April 25, 2005 at 13.oo

  • Mirko Navara (CVUT)
    Why the logic of quantum systems cannot be classical
    May 2, 2005 at 13.2o

  • Joost Joosten (Utrecht)
    Provability, Interpretability and Proof Strength
    May 16, 2005 at 13.oo

  • Jan Krajicek
    A model of bounded arithmetic with the parity quantifier, I.
    May 23, 2005 at 13.oo

  • Olaf Beyersdorff (Berlin)
    Disjoint NP-Pairs from Propositional Proof Systems
    June 1, 2005 at 14.oo

  • Yuri Gurevich (Microsoft Research)
    What is an Algorithm?
    Introduction to Behavioral Computation Theory
    June 24, 2005 at 14.oo
    Charles University, MFF - Mala Strana, room S4
    (joint seminar)

  • Neil Thapen
    Delta_1 induction and Sigma_1 collection
    October 3, 2005 at 13.oo

  • Pavel Hrubes
    Theories where Kreisel Conjecture is false, I.
    October 10, 2005 at 13.oo

  • Pavel Hrubes
    Theories where Kreisel Conjecture is false, II.
    October 17, 2005 at 13.oo

  • Pavel Pudlak
    On \Sigma_1^b nonconservativity of fragments S_2^i, I.
    October 24, 2005 at 13.oo

  • Pavel Pudlak
    On \Sigma_1^b nonconservativity of fragments S_2^i, II.
    October 31, 2005 at 13.oo

  • Pavel Pudlak
    On \Sigma_1^b nonconservativity of fragments S_2^i, III.
    November 7, 2005 at 13.oo

  • Sy Friedman
    Logic colloquium:
    Large cardinals, L-like universes and the Inner model hypothesis
    November 10, 2005 at 13.3o

  • Pavel Pudlak
    On \Sigma_1^b nonconservativity of fragments S_2^i, IV.
    November 14, 2005 at 13.oo

  • Radek Honzik
    Long projective wellorderings and measurability, I.
    November 21, 2005 at 13.oo

  • Joost Joosten
    Notes on optimal propositional proof systems, I.
    November 28, 2005 at 13.oo

  • Joost Joosten
    Notes on optimal propositional proof systems, II.
    December 5, 2005 at 13.oo

  • Radek Honzik
    Long projective wellorderings and measurability, II.
    December 12, 2005 at 13.oo

  • Avi Wigderson (IAS, Princeton) - video presence
    Randomness, Games and Computers
    December 19, 2005 at 13.oo

    2006

  • Neil Thapen
    T^2_2 and search problems I.
    March 20, 2006 at 13.oo

  • Neil Thapen
    T^2_2 and search problems II.
    March 27, 2006 at 13.oo

  • Jan Krajicek
    Proof systems with advice
    October 2, 2006 at 13.oo

  • Alan Skelley
    Complexity of intuitionistic propositional logic
    (after Hertel and Urquhart)
    October 9, 2006 at 13.oo

  • Pavel Hrubes
    A lower bound for intuitionistic propositional logic, I.
    October 16, 2006 at 13.oo

  • Pavel Hrubes
    A lower bound for intuitionistic propositional logic, II.
    October 23, 2006 at 13.oo

  • Leszek Kolodziejczyk
    The polynomial and linear time hierarchies in PV and V^0, I.
    November 6, 2006 at 13.oo

  • Leszek Kolodziejczyk
    The polynomial and linear time hierarchies in PV and V^0, II.
    November 13, 2006 at 13.oo

  • Emil Jerabek
    Extension Frege and Substitution Frege systems for modal and superintuitionistic logics, part I.
    November 20, 2006 at 13.oo

  • Emil Jerabek
    EXxension Frege and Substitution Frege systems for modal and superintuitionistic logics, part II.
    November 27, 2006 at 13.oo

  • R.Kaye (Birmingham)
    Expansions omitting a type
    (Joint work with Fredrik Engstrom, Sweden)
    November 29, 1006 a 13.oo

  • Emil Jerabek
    Extensions Frege and Substitution Frege systems for modal and superintuitionistic logics, part III.
    December 4, 2006 at 13.oo

  • Neil Thapen
    The polynomial hierarchy does not provably collapse in S^1_2, under a cryptographic assumption
    December 11, 2006 at 13.oo

  • Matthias Baaz (TU Wien)
    Controlling Witnesses
    December 18, 2006 at 13.oo

    2007

  • Radek Honzik
    Preservation of measurability and forcing, I.
    February 19, 2007 at 13.oo

  • Radek Honzik
    Preservation of measurability and forcing, II.
    February 26, 2007 at 13.oo

  • Pavel Pudlak
    Quantum deduction rules, I.
    March 5, 2007 at 13.oo

  • Pavel Pudlak
    Quantum deduction rules, II.
    March 12, 2007 at 13.oo

  • Alan Skelley (Roma)
    MAX-SAT and resolution
    March 16, 2007 at 11.oo

  • Radek Honzik
    Preservation of measurbility and forcing, III.
    March 19, 2007 at 13.oo

  • Pavel Pudlak
    Quantum deduction rules, III.
    March 26, 2007 at 13.oo

  • Problem session, I.
    April 2, 2007 at 13.oo

  • Problem session, II.
    April 23, 2007 at 13.oo

  • J.Krajicek
    Proof complexity generators, I.
    May 21, 2007 at 13.oo

  • J.Krajicek
    Proof complexity generators, II.
    May 28, 2007 at 13.oo

  • Niel Thapen
    The provably total search problems in bounded arithmetic
    October 15, 22 and 29, 2008

  • Bernard Anderson
    Automorphisms of the truth table degrees
    November 5, 2007

  • Neil Thapen
    Bounded arithmetic and search problems
    November 12, 2007

  • Emil Jerabek
    Approximate counting by hashing in bounded arithmetic
    November 26 and December 3 and 10, 2007

  • Pavel Hrubes
    A theory where Kreisel's Conjecture is true.
    December 17, 2007

    2008

  • P. Pudlak
    Hrubes's paper on Kreisel's conjecture
    January 18 and 25, 2008

  • Bernard Anderson (Charles University)
    Reals n-generic relative to some perfect tree
    March 17, 2008

  • Stefano Cavagnetto
    Ancient Logic: Aristotle and the Stoics, part I.
    March 31, 2008

  • Stefano Cavagnetto
    Medieval Logic, part II.
    April 14, 2008

  • Tomas Jech
    Measure algebras
    May 19, 2008

  • Phuong The Nguyen
    Bounded Reverse Mathematics
    May 26, 2008