(Jointly organized with Michal Garlik)

Topic: Infinitary Methods in Complexity Theory.

Time and Location: Thursday, 17:20. Dept. of Algebra (Karlin), Room K3.

Description. We plan to focus on the application of infinitary techniques to the study of circuit complexity, proof complexity, and/or finite structures.

Motivation. We mention a few reasons for the investigation of such methods. First, infinitary techniques may avoid certain barriers to standard combinatorial techniques, such as the framework of natural proofs. Secondly, even if an infinitary argument admits a more constructive formulation, the former usually provides new intuitions and insights into the original problem. Indeed, certain seminal results and techniques in complexity theory were initially established or motivated by infinitary reasoning. Moreover, an infinitary proof can sometimes be easier and shorter than its finitary counterpart. Finally, and more speculatively, the solution of some questions in complexity theory might intrinsically depend on infinitary concepts.

Directions. The specific theme of the seminar will depend on the interests of the participants. Here is a partial list of possible topics and directions:

- Ultraproducts and limits of discrete structures.
- Nonstandard models and expansions of pseudofinite structures.
- Existence of purely infinitary (non-uniform) circuit lower bound proofs.
- Boolean-valued models in complexity theory.

Topic | Date | Speaker |

Introduction to Pseudofinite Models and FO-Definability [1], [6], [7] | October 20 | Igor Oliveira |

FO-Definability / Nonstandard Models of Arithmetic [10] | October 27 | Igor Oliveira / Michal Garlik |

Expansions and Ajtai's PHP Lower Bound [10] | November 3 | Michal Garlik |

Boolean-valued models, I [13], [19], [20], [21] | November 10 | Igor Oliveira |

[National Holiday] | November 17 | - |

Boolean-valued models, II | November 24 | Igor Oliveira |

Boolean-valued models, III | December 1 | Igor Oliveira / Michal Garlik |

Boolean-valued models, IV | December 8 | Michal Garlik |

Boolean-valued models, V | December 15 | Raheleh Jalali |

Infinitary Boolean Circuits [17], [18], [11] | TBD | TBD |

References (Preliminary).

1. S. Lindell, H. Towsner, and S. Weinstein. Infinitary methods in finite model theory, 2015.

2. M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy (Conference Version), 1981.

3. M. Ajtai. ∑-Formulae on finite structures, 1983.

4. J. Krajicek. Expansions of pseudofinite structures and circuit and proof complexity, 2015.

5. T. Tao. Ultraproducts as a bridge between discrete and continuous analysis, 2013.

6. M. Otto. Finite Model Theory, 2009.

7. J. Vaananen. Pseudo-finite model theory, 2003.

8. J. Nesetril and P. Ossona de Mendez. A model theory approach to structural limits, 2013.

9. D. Scott. A proof of the independence of the continuum hypothesis, 1967.

10. M. Ajtai. The complexity of the pigeonhole principle, 1994.

11. P. Clote and E. Kranakis. Boolean functions and computation models (Book), 2002.

12. G. Elek and B. Szegedy. Limits of hypergraphs, removal and regularity lemmas. A non-standard approach, 2007.

13. J. Krajicek. Forcing with random variables and proof complexity, 2011.

14. A. Pillay. Pseudofinite model theory, 2015.

15. B. Rossman. Infinite AC0 circuits for parity (Manuscript).

16. M. Garlik. A new proof of Ajtai's completeness theorem for nonstandard finite structures, 2015.

17. M. Sipser. A topological view of some problems in complexity theory, 1984.

18. M. Sipser. Borel circuits and circuit complexity, 1983.

19. I. Goldbring. Nonstandard analysis, 2014.

20. J. L. Bell. Set Theory - Boolean-valued models and independence proofs (Book), 2005.

21. J. F. Maly. Jan Krajicek's forcing construction and pseudo proof systems (Master's Thesis), 2016.

22. A. Wigderson. The Fusion Method for proving lower bounds in circuit complexity, 1993.

If you have questions, please contact Igor Oliveira.

For more information about the seminar, check Krajicek's page.