[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
Private Access to Remote Data via the Melbourne Shuffle
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
Fahad Dogar, Tufts
Monday, February 9, 2015 at 11am in MCS 148

Abstract: Popular applications like Facebook and Google Search perform rich and complex "tasks" (e.g., generating a user's social newsfeed). From a network perspective, these tasks typically comprise multiple flows, which traverse different parts of the network at potentially different times. Existing network resource allocation schemes (e.g., TCP), however, treat all these flows in isolation - rather than as part of a task - which delays completion of tasks (i.e., user requests). In this talk, I will make a case for "task-aware" network scheduling, and present Baraat, a decentralized task-aware scheduling system. Compared to existing approaches (e.g., TCP and other flow based schemes), Baraat improves both the average and tail response times for a wide range of workloads. I will also present a deployment friendly transport framework (PASE) which can support richer resource allocation schemes (e.g., task-aware scheduling) without requiring changes to network switches. Both Baraat and PASE appeared in ACM Sigcomm 2014. Joint work with researchers from MSR, MSU, and LUMS.

Bio: Fahad Dogar is an assistant professor in the computer science department at Tufts University. Earlier he did his PhD from Carnegie Mellon and undergrad from LUMS, Pakistan. Most recently, he was a post-doc in the systems and networking group at Microsoft Research UK. webpage: https://sites.google.com/site/fahaddogar/home
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/cs-talks/attachments/20150129/fb2a97eb/attachment.html>


More information about the cs-talks mailing list