UB Theory Weekly – Week 9

Hi all,

The ninth 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 Atri Rudra. The abstract of the talk in his own words –


How to compute recurrences efficiently

Say you are given a recurrence:

f_{i+1} = \sum_{j=0}^t g_j*f_{i-j}

where g_j‘s are from some field (say the complex numbers).

How quickly can you compute f_n for an arbitrary n? The trivial algorithm can do this with O(nt) operations over the field. In this talk, I will outline the method to do this much quickly with the hope of ultimately showing an algorithm that takes  O(t\log{n}\log{t}) operations over the field. All of the results are known results (and have been know for more than 30 years).

No prior knowledge will be assumed but at some point comfort with polynomials will be useful. Also a warning that the presentation might not be up to snuff since I might be giving this talk cold turkey [but if you have not seen these algorithms it’ll still be worth your time to show up :-)]


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


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s