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.
Complexity seminar
The seminar takes place in the seminar room of IM, rear building, ground floor, Friday at 14:00 - 16:00Chair: Michal Koucky, Pavel Pudlak
The programme is announced via the mailing list.
A tutorial on character sums and Paley graphs
Navid Talebanfard
IM, CAS
Friday, 27. March 2020 - 13:30 to 15:00
Zoom https://us04web.zoom.us/j/481620087
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
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
IM
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.
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.