Abstract: Within complexity theory, circuits are traditionally formalized as having what is sometimes called a "feed forward" topology. Under this topology, no gate is allowed to be its own input nor are any cycles allowed to exist in the circuit. However in real life, circuits are under no such obligation to follow that exact topology. This begs the question: if we allow our circuits to have any arbitrary topology, do we gain any additional computational power over feed forward circuits? In this seminar we will define the class of "Recurrent Circuits", circuits that are able to have cycles, present unique constructions that can be built under them, and ultimately demonstrate them to be computationally equivalent to traditional feed forward circuits.
The CICS Theory Seminar is free and open to the public. If you are interested in giving a talk, please email Cameron Musco or Rik Sengupta. Note that in addition to being a public lecture series, this is also a one-credit graduate seminar (CompSci 891M) that can be taken repeatedly for credit.