moteur de recherche

Séminaire Algo - Nathan Grosshans
Séminaire Algo - Nathan Grosshans
9-Apr-2019 14:00
Age: 1 year

Nathan Grosshans

The power of programs over monoids taken from some small varieties of finite monoids

Seminar room 4B125 (Copernic building)

Abstract: One major approach to the P vs NP question in computational complexity theory is to look for super-polynomial Boolean circuit lower bounds, but even proving such lower bounds in very restrictive settings seems dauntingly challenging. One of the possible restrictions to put on circuits is to limit their depth to be poly-logarithmic: this gives rise to the NC hierarchy within P for an appropriate uniformity condition, initially defined to capture the notion of efficient parallel computation. At the bottom of this hierarchy, the complexity class NC^1 of languages decided by polynomial-size logarithmic-depth fan-in 2 Boolean circuits is particularly interesting because it is much better understood than the levels above in the hierarchy but at the same time concentrates a number of deep and difficult open questions, both about its internal structure and about its relationship to the levels above in the NC hierarchy, to P and even NP. 

The computational model of programs over monoids, introduced by Barrington and Thérien in the late 1980s, gives a way to generalise the notion of (classical) recognition through morphisms into monoids in such a way that almost all open questions about the internal structure of the complexity class NC^1 can be reformulated as understanding what languages (and, in fact, even regular languages) can be program-recognised by monoids taken from some given variety of finite monoids. Unfortunately, for the moment, this finite semigroup theoretical approach did not help to prove any new result about the internal structure of NC^1 and, even worse, any attempt to reprove well-known results about this internal structure (like the fact that the language of words over the binary alphabet containing a number of 1s not divisible by some fixed integer greater than 1 is not in AC^0) using techniques stemming from algebraic automata theory failed. In this talk, I shall give a global introduction to circuit complexity with a focus on NC^1 and other "small" classes, present the model of programs over monoids after giving the basics of algebraic automata theory, explain how this model relates to "small" circuit complexity classes and present some of the contributions I made during my Ph.D. thesis to the understanding of the computational power of programs over monoids, focusing on the well-known varieties of finite monoids DA and J (giving rise to "small" circuit complexity classes well within AC^0). I shall conclude with a word about ongoing work and future research directions.

<- Back to: Accueil