UB Theory Weekly – Week 10

Hi all,

The tenth 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 Shi Li. The abstract of the talk in his own words –

I will talk about the classic 3/2-approximation for the scheduling problem to minimize the total weighted competition time.

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

Advertisements

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.