slideshow 3

Complexity seminar

The seminar takes place in the seminar room of IM, rear building, ground floor, Friday  at  14:00 - 16:00
Chair: Michal Koucky, Pavel Pudlak
The programme is announced via the mailing list.

A tutorial on character sums and Paley graphs

Navid Talebanfard
Friday, 27. March 2020 - 13:30 to 15:00


We recall the famous of problem explicit constructions of Ramsey graphs. One of the early non-trivial constructions is Paley graphs defined using quadratic residues in finite fields. We will see nice tools from analytic number theory to study properties of this graph.

A Logical Characteristic of Read-Once Branching Programs

Stanislav Žák
Institute of Computer Science, CAS
Friday, 31. January 2020 - 13:30 to 15:00

in IM, rear building, ground floor

We present a mathematical model of the intuitive notions such as the knowledge or the information arising at different stages of computations on branching programs (b.p.). The model has two appropriate properties:

i) The "knowledge" arising at a stage of computation in question is derivable from the "knowledge" arising at the previous stage according to the rules of the model and according to the local arrangement of the b.p.

ii) The model confirms the intuitively well-known fact that the knowledge arising at a node of a computation depends not only on it but in some cases also on a "mystery" information. (I. e. different computations reaching the same node may have different knowledge(s) arisen at it.)

We prove that with respect to our model no such information exists in read-once b.p.`s but on the other hand in b. p.`s which are not read-once such information must be present. The read-once property forms a frontier. More concretely, we may see... more

Some Results in Property Testing

Alexander Belov
University of Latvia
Friday, 20. December 2019 - 13:30 to 15:00

in IM, rear building, ground floor

The field of property testing deals with the following question. Given an object, detect whether it satisfies some property or is far from doing so. Usually, the object is modelled as a bit-string, and the distance is (relative) Hamming distance. The goal is to develop an algorithm whose complexity is very small: much smaller than the size of the object.


Does the existence of a complete problem for TFNP class imply the existence of an optimal proof system or vice versa? Part II.

Erfan Khaniki
Friday, 13. December 2019 - 13:30 to 15:00

in IM, rear building, ground floor

In this lecture we will construct an oracle with respect to which:
     a. There is no optimal proof system for propositional tautologies.
     b. TFNP=FP.
The existence of this oracle and the one constructed in the previous lecture shows that TFNP_c and CON^N are independent
of each other in relativized worlds.