Logic and Complexity Student Seminar

Logic & Complexity Student Seminar (Winter 2016)
(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.