# [cs-talks] Upcoming CS Seminars: Theory (tomorrow) + BUSec (Weds) + NRG (next Mon)

Conroy, Nora Mairead conroynm at bu.edu
Thu Jan 29 12:34:51 EST 2015

Theory Seminar
Compressibility and Predictability of Infinite Binary Strings
Tomislav Petrovic, BU
Friday, January 30, 2015 at 2:30pm in MCS 148

Coffee and snowball fight before the talk.

Abstract: Compressibility, defined in terms of Kolmogorov complexity/Martin-Lof randomness, will be compared to several notions of predictability.  Predictability will be defined as winning infinite amount of cash while playing a betting game against a string. Rules of the game can be different, and four different types of game will be considered: betting on the prefix of a string, betting on the next bit, betting on the bit at the position of choice and betting on a set of prefixes.  Some of the results that will be presented are well known: There is a single (Turing) machine that by betting on prefixes predicts all compressible (non-Martin-Lof random) strings.  There is a "very" compressible string which is unpredictable by any machine that bets on the next bit.  There are two machines, betting on the bit at the position of choice, s.t.  all "very" compressible strings are predictable by one of them.  (However, nobody knows if there is a string that is both unpredictable and compressible) A novel type of game, prefix-set betting, which is "in between" betting on prefixes and betting on bits will be described. In any betting game the result of previous bets gives us a subset of strings which contains the string we are betting against. Betting on a bit divides the subset into two sets of equal measure - the ones that have 0 at the position of a bit and the ones that have 1. Similarly, in prefix-set betting, a bet divides the subset into two sets of equal measure, however the player has additional freedom to define those sets as a finite set of prefixes of her choice. On the other hand, prefix-set betting game, like betting on a single prefix, and unlike betting on bits, requires a judge.  It can be shown that while there is no single machine that predicts all compressible strings there are two s.t. all compressible strings are predictable by one of them.

——
UPCOMING
BUSec Seminar
Olya Ohrimenko, MSR
Wednesday, February 4, 2015 at 9:30am in MCS 148

Abstract: A shuffle is an algorithm for rearranging an array to achieve a random permutation of its elements. Early shuffle methods were motivated by the problem of shuffling a deck of cards. An oblivious shuffle is a distributed shuffle executed by a client who permutes an array of encrypted data items stored at a server in such a way that the server cannot determine the output permutation with probability better than a random guess. Several private cloud storage solutions that obfuscate the access pattern to the data use an oblivious shuffle as a fundamental building block. We present the Melbourne Shuffle, a simple and efficient oblivious shuffle that allows a client with O(\sqrt{n}) memory to obliviously shuffle an array of size n stored at a server by exchanging O(\sqrt{n}) messages of size O(\sqrt{n}). The Melbourne Shuffle is the first provably secure oblivious shuffle that is not based on sorting.  This talk is based on the paper “The Melbourne Shuffle: Improving Oblivious Storage in the Cloud”, appeared in International Colloquium on Automata, Languages and Programming (ICALP), 2014. Joint work with Michael Goodrich (UC Irvine), Roberto Tamassia (Brown University) and Eli Upfal (Brown University).

NRG Seminar
Revisiting Network Resource Allocation in Data Centers