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!

UB Theory Weekly – Week 6

Hi all,

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

4:00 – 4:40 pm – A talk by Sai Vikneshwar(me :)). The plan for the talk is as follows –

I will be talking about obtaining bounds for Join Queries via Fractional Edge Covers and extend this idea to a Degree Based Bound.

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

Hoping to see you all!

UB Theory Weekly – Week 5

Hi all,

The fifth Theory Weekly Meeting will happen this Friday 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 Atri Rudra. The abstract of the talk in his own words –

A non-divide and conquer FFT
————————–
I will describe a description of the FFT (Fast Fourier Transform) that does not use the textbook Divide and Conquer paradigm. This is a message passing algorithm for the FFT and it has the following “advantages” over the standard description: (i) (In my personal opinion) this version makes it more transparent as to why we can get the O(nlog(n)) runtime for FFT when compared to the naive O(n^2) runtime; and (ii) This version also generalizes to show a class of matrices (of which the DFT is a special case) for which matrix vector multiplication can be done in near linear time.

Just to clarify: this is a *known* description that (in my informal polls) seems to be not that well-known. Also for simplicity I’m going to show a sub-quadratic version of the FFT.

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

All are welcome!