# Polyhedral products and the Aanderaa-Karp-Rosenberg conjecture

-
Ivan Limonchenko, National Research University Higher School of Economics

If a (simple) graph has $n$ vertices, then $m=n(n-1)/2$ is the maximal possible number of its edges: the Aanderaa-Rosenberg conjecture (now proved) states that there exists a positive constant $C$ such that at least $Cm$ questions are needed to check any (non-trivial) monotonic invariant property. A stronger Aanderaa-Karp-Rosenberg conjecture (still open) asserts that one can always assume $C=1$ above. The topological approach developed to attack the last conjecture relates it to the study of fixed point sets of finite group actions on cellular spaces.
In this talk, we'll be interested in a version of the Aanderaa-Karp-Rosenberg conjecture, in which one considers all non-trivial monotonic properties. We're going to interpret a monotonic boolean function of $m$ variables as a simplicial complex with $m$ vertices, and then estimate its algorithmic complexity in terms of the topological characteristics of the corresponding polyhedral products. This new perspective provides new connections between toric topology and theoretical informatics.