Seminar code: NMMB453 (both semesters)

(you can sign up for the seminar repeatedly)

The seminar is run in English if students not speaking Czech attend, as happened many semesters during the past.

The seminar is intended for students interested in mathematical logic. It does not assume more than basic knowledge, e.g. on the level of basic course Uvod do matematicke logiky (taking that particular course is not a necessary admission condition though). The seminar runs from the summer semester 06/07. Students are welcome to attend also a more advanced Logic seminar.

In every semester we concentrate on a different theme and it is generally not assumed that you have attended earlier semesters (there were some exceptions when the topic from one semester over-spilled into the next one). The themes are chosen in a discussion with the participants in order to respect their backgrounds and interests, and often relate to the area of interactions of logic and computational complexity theory. The main program is complemented by occasional lectures by guests.## Past program.

## Winter semester 2020/21:

## Topics in Boolean complexity

Boolean complexity is concerned with the question how hard it is to define various Boolean functions by propositional formulas or circuits (or other devices) and, in particular, how large these need to be. The fundamental problem (linked with such notorious problems as is the P vs. NP problem) is to exhibit an explicit Boolean function which is hard to define.

We shall look at some basic background and then at few topics that have a common facet with logic or are relevant in proof complexity.## The particular topics and talk sequence page.

On Wednesday 7.October the seminar will attend (via zoom) the Jarnik lecture of Libor Barto on CSPs and symmetries.

Our own talks will start the week after.## Day, time and place:

Wednesday at 14.oo, starting on 30.September.

Zoom meeting ID: 396 697 4589

https://lfp-cuni.zoom.us/j/3966974589

Password: I sent the password to all students who signed up for the seminar by 29.IX.2020. If you will sign-up on some later date write me for the password.

After you joining the meeting you will find yourself in a waiting room - this is just a precaution to avoid unwanted visitors.

For the same reason please join each meeting under your *real name*. Only those who signed up for the course will be let in. The zoom room will open always cca 5 minutes before the seminar.## Web:

http://www.karlin.mff.cuni.cz/~krajicek/babylogika.html