[Colloquium] Kristoffer Hansen, University of Aarhus: TTI-C Talk

[Julia MacGlashan]

When:             Tuesday, July 1, 2008 @ 2:00 pm

                        Theory Seminar

 

Where:            TTI-C Conference Room

1427 E. 60th St, 2nd Floor

 

Who:               Kristoffer Hansen, University of Aarhus

 

Topic:             Constant Width Characterizations of Small Depth Circuit
Classes

 

 

Barrington's Theorem showed that constant width branching programs or
equivalently, constant width circuits are surprisingly powerful. They
compute exactly the functions computed by AND/OR circuits of constant fanin
and of logarithmic depth, i.e NC^1.

 

At the heart of this result is an algebraic construction, showing that the
word problem for any finite unsolvable monoid is complete for NC^1. Shortly
after Barrington's result Barrington and Thérien gave characterizations for
the constant depth circuit classes AC^0 and ACC^0 within the same algebraic
framework of finite monoids, by using aperiodic and solvable monoids,
respectively.

 

In this talk we will survey recent results providing characterizations of
AC^0 and ACC^0 by imposing certain topological constraints (for instance
planarity) on constant width branching programs and circuits.

 

Contact:          Prahladh Harsha, TTI-C         prahladh at tti-c.org
773-834-2549

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20080630/ffcc3c32/attachment-0009.htm