Algorithms
“We Will be Right With You”: Managing Customers Expectations with Vague Promises and Cheap Talk
Delay announcements informing customers about anticipated service delays are prevalent in service-oriented systems. How to use delay announcements to manage the service system in an efficient manner is a complex problem which depends on both…
Efficient Bayesian Algorithmic Mechanism Design
The principal problem in algorithmic mechanism design is to merge the incentive constraints imposed by selfish behavior with the algorithmic constraints imposed by computational intractability. In this talk we will consider the problem of designing…
Depth Bounded Explicit State Model Checking
Limit Theorems in Pseudorandomness and Learning Theory
An important theme in theoretical computer science over the last decade has been the usefulness of translating a combinatorial problem over a discrete domain to a problem in continuous space. For instance, invariance principles or…
Extracting Knowledge from Networks: Rumors, Superstars, and Communities
As social networks such as Facebook and Twitter become larger and more complex, it becomes more and more difficult to extract useful information from them efficiently. However, there is a great deal of knowledge encoded…
Cryptography with Weak, Noisy, Leaky and Tempered Keys
Traditionally, to achieve cryptographic security, we require that users generate long perfectly random keys, store them on a perfectly reliable and secure device, and perfectly shield this device to prevent an attacker from observing or…
Orthogonal Matching Pursuit with Replacement
Generalized Identity-Based Encryption
My talk will mainly be on new developments in generalized identity-based cryptography. Identity-based cryptography is relatively new technology, less than a decade old, in which a message can be encrypted using any string as a…
