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.

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

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

in IM, rear building, 1st floor (!)

In this talk, we will investigate the relationship between proof complexity conjectures that are mentioned in the "Incompleteness in the finite domain" paper. In particular, we are interested in the relationship between the nonexistence of a complete problem for TFNP class (TFNP_c)  and the nonexistence of an optimal proof system for propositional tautologies (CON^N). For this matter,  we will construct two oracles V and W such that:

1. With respect to the V
     a. There is no complete problem for disjoint NP-pairs.
     b. E=NE.
2. With respect to the W
     a. There is no optimal proof system for propositional tautologies.
     b. TFNP=FP.
The existence of these oracles shows that TFNP_c and CON^N are independent of each other in the relativized worlds.

Grassmann meets Macaulay: From Algebra to Algorithms and back

Cornelius Brand
Friday, 29. November 2019 - 13:30 to 15:00

in IM, rear building, ground floor

In this talk, I will give an introduction to two recent algebraic techniques in (parameterized) algorithms for hard problems: One is the exterior-algebra based approach of Brand, Dell and Husfeldt (STOC'18) and Brand (ESA'19), the other is the one by Pratt (FOCS'19) and Brand and Pratt (submitted), based on a symbolic calculus of differential operators.

Both techniques will be gently introduced in the context of their flagship application problem: Detecting squarefree monomials in polynomials computed by arithmetic circuits, where they each yield the state-of-the-art in certain settings. I then proceed to show how these seemingly unrelated algorithmic techniques both arise from an underlying isomorphism of algebraic structures. This is of independent interest, and gives lower bounds on the symmetric rank of a specific symmetric tensor, namely the determinant of generic Hankel matrices, and extends recent work in commutative algebra (Shafiei 2015, J. Commut. Alg.).
... more

Adventures in Monotone Complexity and TFNP

Lukáš Folwarczný
Friday, 15. November 2019 - 13:30 to 15:00

in IM, rear building, ground floor

In this talk, I present the main ideas from the paper Adventures in Monotone Complexity and TFNP by Mika Göös, Pritish Kamath, Robert Robere, and Dmitry Sokolov. The main focus of the talk will be on the relations between monotone computational models and communication complexity (going from Karchmer-Wigderson (formulas) and Razborov (circuits) to this paper (span programs)).

Presburger meets Cambridge Analytica

Martin Koutecký
Friday, 1. November 2019 - 13:30 to 15:00

in IM, rear building, ground floor

Cambridge Analytica is an infamous and now bankrupt (but sure to survive in some other way) company which helped manipulate elections all over the world (including the Brexit and Trump campaigns) through targeted advertising on social networks. We want to analyze such tasks and events from the perspective of computational complexity, asking questions such as: what is the cheapest bribery which makes my candidate win? what if opinion diffusion happens in the underlying social network? what if manipulation happens simultaneously by multiple agents? Answering these questions is helpful not only to a potential briber, but also to observers wishing to detect bribery or have meaningful measures of the (surprisingly elusive) notion of margin of victory.

Presburger arithmetic (PrA) is the first-order theory of the natural numbers with addition, named in honor of Mojżesz Presburger who introduced it in 1929 and proved its decidability. While the questions posed above are hard in... more