0 views

Skip to first unread message

May 10, 2023, 4:00:25 AM5/10/23

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

Hello all,

The seminar, which starts in 1 hour, will take place (only this time) in __building 504, room 1__.

See you there at 12.

Best,

Arnold

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.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu