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.

Cobham recursive set functions, part 2

Neil Thapen
Institute of Mathematics
Monday, 30. March 2015 - 13:30
I will define a class CRSF of "polynomial time functions" on arbitrary sets. The definition is in the spirit of Cobham's definition of polynomial time function on strings, in that we can only define a function by recursion if we already know a bound on the complexity of its output. I will show that on binary strings this gives the usual polynomial time functions, and that, for a suitable definition of circuit complexity for sets, every function in CRSF has small circuits. A general theme is that CRSF can be understood as a model of parallel computation over directed acyclic graphs, where the graph of the computation can only be polynomially more complex than the graph given as input. Joint work with Arnold Beckmann, Sam Buss, Sy Friedman and Moritz Mueller.

Cobham recursive set functions

Neil Thapen
Institute of Mathematics
Monday, 23. March 2015 - 13:30
I will define a class CRSF of "polynomial time functions" on arbitrary sets. The definition is in the spirit of Cobham's definition of polynomial time function on strings, in that we can only define a function by recursion if we already know a bound on the complexity of its output. I will show that on binary strings this gives the usual polynomial time functions, and that, for a suitable definition of circuit complexity for sets, every function in CRSF has small circuits. A general theme is that CRSF can be understood as a model of parallel computation over directed acyclic graphs, where the graph of the computation can only be polynomially more complex than the graph given as input. Joint work with Arnold Beckmann, Sam Buss, Sy Friedman and Moritz Mueller.

A restricted reduced power construction of models of bounded arithmetic, part 2

Michal Garlík
Charles University
Monday, 16. March 2015 - 13:30
We will present a construction of models of bounded arithmetic in the framework of a generalization of the ultrapower construction called restricted reduced power. As an application of the construction we show, assuming the existence of a one-way permutation g hard against polynomial-size circuits, that strictR^1_2(g) is weaker than R^1_2(g).

A restricted reduced power construction of models of bounded arithmetic

Michal Garlík
Charles University
Monday, 9. March 2015 - 13:30
We will present a construction of models of bounded arithmetic in the framework of a generalization of the ultrapower construction called restricted reduced power. As an application of the construction we show, assuming the existence of a one-way permutation g hard against polynomial-size circuits, that strictR^1_2(g) is weaker than R^1_2(g).

Pages