slideshow 3

Logic seminar

usually takes place each Monday at 16:00 in IM, rear building, ground floor
Chair: Pavel Pudlak, Neil Thapen, Jan Krajíček
More information on the old seminar web page. The programme is announced via the mailing list.

On the parameterized complexity of Delta-0 truth

Moritz Müller
University of Passau
Monday, 21. November 2022 - 16:00 to 17:30
Online - https://cesnet.zoom.us/j/472648284 - contact thapen@math.cas.cz before the meeting to join
We consider the problem, given a Δ0 formula φ(x) and a natural number n in unary, whether φ(n) is true. We are interested in instances of the problem where n is much bigger than φ. More precisely, we consider the parameterized problem with parameter |φ|. We show unconditionally that this problem does not belong to the parameterized version of AC0. We also show that certain natural upper bounds on the parameterized complexity of the problem imply separations of classical complexity classes. These results are obtained by an analysis of a parameterized halting problem. A related problem concerns the provability of the MRDP theorem in bounded arithmetic.

Integrating Machine Learning into Saturation-based ATPs

Martin Suda
CVUT
Monday, 14. November 2022 - 16:00 to 17:30
Large lecture room at Zitna and online at https://cesnet.zoom.us/j/472648284 - contact thapen@math.cas.cz before the meeting to join online
Applying the techniques of machine learning (ML) promises to dramatically improve the performance of modern automatic theorem provers (ATPs) and thus to positively impact their applications. The most successful avenue in this direction explored so far is machine-learned clause selection guidance, where we learn to recognize and prefer for selection clauses that look like those that contributed to a proof in past successful runs. In this talk I present Deepire, an extension of the ATP Vampire where clause selection is guided by a recursive neural network (RvNN) for classifying clauses based solely on their derivation history.

Elementary analytic functions in VTC^0, Part 2

Emil Jeřábek
IM CAS
Monday, 24. October 2022 - 16:00 to 17:30
Large lecture room at Zitna and online at https://cesnet.zoom.us/j/472648284 - contact thapen@math.cas.cz before the meeting to join online
It is known that rational approximations of elementary analytic functions (exp, log, trigonometric and hyperbolic functions, and their inverse functions) are computable in the complexity class TC^0. In this talk, we will show how to formalize their construction and basic properties in the correspoding arithmetical theory VTC^0, working with completions of fraction fields of models of VTC^0. As a consequence, we will show that every countable model of VTC^0 is an exponential integer part of a real-closed exponential field, using a recursive saturation argument.

Elementary analytic functions in VTC^0

Emil Jeřábek
IM CAS
Monday, 17. October 2022 - 16:00 to 17:30
Large lecture room at Zitna and online at https://cesnet.zoom.us/j/472648284 - contact thapen@math.cas.cz before the meeting to join online
It is known that rational approximations of elementary analytic functions (exp, log, trigonometric and hyperbolic functions, and their inverse functions) are computable in the complexity class TC^0. In this talk, we will show how to formalize their construction and basic properties in the correspoding arithmetical theory VTC^0, working with completions of fraction fields of models of VTC^0. As a consequence, we will show that every countable model of VTC^0 is an exponential integer part of a real-closed exponential field, using a recursive saturation argument.

Compactness and incompactness in set theory, with applications to uncountable graphs

Chris Lambie-Hanson
IM CAS
Monday, 26. September 2022 - 16:00 to 17:30

IM, rear building, ground floor

(Joint seminar with set theory group)

The study of compactness phenomena at uncountable cardinals has been a central line of research in combinatorial set theory since the mid-twentieth century. In the first part of this talk, we will give a broad overview of this area of research and survey some of its most prominent results. We will then look at a few recent results concerning compactness phenomena for uncountable graphs. We first look at possible generalizations of the de Bruijn-Erdos compactness theorem for chromatic numbers to uncountable cardinalities, in particular showing that consistently there are large uncountable graphs witnessing extreme failures of compactness for, e.g., the property of having a countable chromatic number. We then turn to the study of the structure of the collections of finite subgraphs of uncountably chromatic graphs, answering a question of Erdos, Hajnal, and Szemeredi about the growth rates of chromatic numbers in such collections of... more

On the Conjectures of Razborov and Rudich

Rahul Santhanam
University of Oxford
Monday, 23. May 2022 - 16:00 to 17:30
Online - https://cesnet.zoom.us/j/472648284 - contact thapen@math.cas.cz before the meeting to join
We say that Rudich's Conjecture holds for a propositional proof system Q if there are no efficient Q-proofs of random truth table tautologies. We say that Razborov's Conjecture holds for a propositional proof system Q if there are no efficient Q-proofs of any truth table tautologies. A fundamental task in proof complexity and the meta-mathematics of circuit lower bounds is to understand for which Q these conjectures hold. We show various results about these conjectures, including evidence for their difficulty.

Based on joint work with Jan Pich.

Pages

  • 1