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.

Beyond Natural Proofs

Jan Pich
Friday, 18. October 2019 - 13:30 to 15:00

in IM, rear building, ground floor

Hardness magnification reduces major complexity separations to proving lower bounds for some natural problem Q against weak circuit models. Several recent works have established results of this form. In the most intriguing cases, the required lower bound is known for problems that appear to be significantly easier than Q, while Q itself is susceptible to lower bounds but these are not yet sufficient for magnification. In this work, we provide more examples of this phenomenon, and investigate the prospects of proving new lower bounds using this approach. In particular, we consider the following essential questions associated with the hardness magnification program:

- Does hardness magnification avoid the natural proofs barrier of Razborov and Rudich?
- Can we adapt known lower bound techniques to establish the desired lower bound for Q?

We establish that some instantiations of hardness magnification overcome the natural proofs barrier in the following... more

On the distribution of runners on a circle

Pavel Hrubes
Friday, 11. October 2019 - 13:30 to 15:00

in IM, rear building, ground floor

I will discuss the following problem: consider runners on a circular track, running with constant speeds such that k of the speeds are distinct. Does it have to be the case that, at some point in time, their distribution on the circle is far from uniform? I will give an almost optimal solution, as a function of k. This has an interesting application to the distribution of complex arguments of roots of univariate polynomials, and the Real Tau Conjecture in arithmetic circuit complexity.

Solving connectivity problems via basic Linear Algebra

Anish Mukherjee
Friday, 4. October 2019 - 13:30 to 15:00

in IM, rear building, ground floor

We consider some classical graph connectivity problems like reachability,
shortest path and disjoint paths in this talk. For the first two problems,
we show efficient parallel (dynamic AC^0) algorithms in the dynamic model,
confirming a conjecture of Patnaik and Immerman ’94 for directed
reachability. Recently, we have been able to extend this for batch updates
also. For the optimization version of the disjoint paths problem, we show
efficient sequential and parallel algorithms in planar graphs where all the
terminals lie on a single face. This partly answers an open question of
Colin De Verdière and Schrijver ’08. Interestingly the basic idea behind
these algorithms is to compute some linear algebraic property of the matrix
associated with the given graph, which I shall try to convey in this talk.

Based on joint works with Samir Datta, Raghav Kulkarni, Siddharth Iyer,
Thomas Schwentick, and Thomas Zeume.... more

Who needs category theory?

Yuri Gurevich
University of Michigan
Friday, 13. September 2019 - 13:30 to 15:00

in IM, rear building, ground floor

Mathematicians use category theory, at least some of them do. In fact category theory
is instrumental in some branches of mathematics, e.g. algebraic topology. But what
about computer scientists or physicists? Do they need category theory?

If category theory is your hammer, some computing problems look like appropriate
nails. However the speaker was not impressed and remained skeptical about the use of
category theory in computer science. When he learned that the generally accepted
mathematical basis for topological quantum computing is sophisticated category theory,
he proposed to his long-time collaborator Andreas Blass to "decategorize" topological
quantum computing.

It turned out, surprisingly, that category theory or something like it is necessary
for topological quantum computing. Moreover the root cause of the necessity is not
specific to topological quantum computing. There should be numerous other... more