UB Theory Weekly – Week 24

Hi all,

The 24th 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 – 3:00 pm – A talk by Shi Li on his recent FOCS 2016 paper: Better Unrelated Machine Scheduling for Weighted Completion Time via Random Offsets from Non-Uniform Distributions.


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. 

UB Theory Weekly – Week 3

Hi all,

This week we have FWCG happening here at UB. I would like to urge you all to attend the same. There are some interesting talks –

Piotr Indyk (MIT)
Talk title: Beyond Locality Sensitive Hashing
Time: 11:00-12:00, Oct. 23,
Location: 106 O’Brian Hall
Kenneth L. Clarkson (IBM Almaden)
Talk title: Input Sparsity and Hardness for Robust Subspace Approximation
Time: 11:00-12:00, Oct. 24
Location: 101 Davis Hall
Kenneth W. Regan (UB)
Talk title: Using the Shape of Space for Shortcuts: Speeding up regression on millions of chess positions
Time: 2:45-3:45 pm, Oct. 23
Location: 106 O’Brian Hall

Weekend Coding Mania – 1

1. SRM 360 Div1 500

2. SRM 448 Div2 1000

3. SRM 510 Div2 250

4. SRM 504 Div2 250

5. SRM 512 Div2 250

6. SRM 510 Div1 250

7. SRM 523 Div1 250