UB Theory Weekly – Week 19

Hi all,

The 19th Theory Weekly Meeting will happen this Friday between 2:00 – 3:00 pm at 203 Davis Hall(Theory Lab). The schedule will be as follows :

2:00 – 2:50 pm – An informal talk by Michael Wehar on the wonderful summer that he spent at IBM Research! 🙂

2:50 – 3:00 pm  – Socializing with the Theory community. 

UB Theory Weekly – Week 7

Hi all,

The seventh Theory Weekly Meeting will happen today between 4:00 – 5:00 pm at 203 Davis Hall(Theory Lab). The schedule will be as follows :

4:00 – 4:50 pm – A talk by Michael Wehar. The abstract of the talk in his own words –

We consider the intersection problem for finite automata.  Given DFA’s D_1 and D_2, does there exist a string that is accepted by both D_1 and D_2?  This problem is solvable in quadratic time.  We show that if it can be solved in O(n^{2 - epsilon}) time, then there are faster algorithms for SAT.  Further, we investigate the complexity of the intersection problem for three DFA’s.

4:50 – 5:00 pm  – Socializing with the Theory community. 

Hoping to see you all!