•  
    • Dmitry Sokolov
    • (EPFL)
    • Top-down depth-4 circuit lower bounds
    • Abstract:
    • In this talk, we present a top-down lower-bound method for depth-4 boolean circuits. In particular, we give a new proof of the well-known result that the parity function requires depth-4 circuits of size exponential in n^{1/3}. Our proof is an application of robust sunflowers and block unpredictability. Joint work with Mika Göös, Artur Riazanov and Anastasia Sofronova
    • 05.06.23   16:00
    • Leonardo Coregliano
    • (IAS Princeton)
    • Continuous combinatorics
    • Abstract:
    • The field of continuous combinatorics is the study of (large, dense) combinatorial structures using tools typically associated with continuous objects, such as tools from analysis, topology or measure theory. The field started under the name of "graph limits" since the main object of study were graphons, i.e., limits of graphs. Since then, several other limits have been constructed for all sorts of combinatorial objects (e.g., digraphs, hypergraphs, permutations, etc.) and even general limits were provided through the unifying theory of flag algebras.

      However, the limits constructed in the theory of flag algebras are of an algebraic/syntactic nature, due to the minimalist nature of the theory (as opposed to the more semantic/geometric nature of the previous ad hoc limits of the literature). In this talk, I will present the semantic/geometric counterpart to flag algebras: the theory of theons. I will also give a couple of examples of proofs both within continuous combinatorics and of applications that use its tools.

      This talk is based on joint work with Alexander A. Razborov.

    • 22.05.23   16:00

    Pavel Pudlak, Neil Thapen, Jan Krajíček
    organizers

  •