0 views

Skip to first unread message

May 4, 2023, 5:06:10 AM5/4/23

to BIU Theory Seminar, eio...@gmail.com

Hello all,

Next week (Wed May 10, at 12) we will meet for our theory seminar.

We give an O(log d)-competitive algorithm for this problem, where d is the maximum row sparsity of any matrix Ct. This bypasses and improves exponentially over the lower bound of sqrt(n) known for general convex bodies. Our algorithm is based on iterated information projections, and, in contrast to general convex body chasing algorithms, is entirely memoryless. We also show how to round our solution dynamically to obtain the first fully dynamic algorithms with competitive recourse for all the stated problems above; i.e. their recourse is less than the recourse of every other algorithm on every update sequence, up to polylogarithmic factors. This is a significantly stronger notion than the notion of absolute recourse in the dynamic algorithms literature.

This is joint work with Sayan Bhattacharya, Niv Buchbinder, and Thatchaphol Saranurak.

May 9, 2023, 9:24:11 AM5/9/23

to BIU Theory Seminar, eio...@gmail.com

This is only a one time change, and next week our seminar will come back to building 605, room 14.

See you there at 12!

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu