**Location: **We meet in the Gates 4B lobby, also known as the theory lounge.

**Mailing List: **thseminar@cs.stanford.edu. Email shaddin to sign up.

**Contact: **Shaddin Dughmi (shaddin at cs dot stanford dot edu)

**Food: ** Wendy usually choses the food at her discretion. However, the speaker may suggest a preference to Wendy for the day of their talk ahead of time.

** For previous quarter schedules see here. **

**4/3: Organizational****4/10: Don Knuth: The Amazing Y Function****4/17: Mukund Sundararajan: Stop Characterizing and Start Bounding**(Joint work with Shahar Dobzinski (Hebrew University), Aranyak Mehta (Google), Tim Roughgarden)We investigate a fundamental (public-good) cost-sharing mechanism design problem. The goal is to implement a socially efficient solution (our objective) while recovering cost (a constraint). As participants value for service is private, we would also like incentive compatibility (another constraint). It was known previously that the problem is over constrained. We would like to investigate \emph{how} over constrained the problem is. Our proof has two phases: A. Characterizing: Using the constraints to figure out what kind of mechanisms are valid. (Almost non-existent and we will see why) B. Bounding: Using the characterization to prove a lower bound on the efficiency loss. (A fun application of Yao's Minimax principle)

**4/24: Mihaela Enachescu: Routelet Placement for Multipath Transport**I plan to present an approach for enabling multi-path routing in large networks. This is based on a project at NEC Labs, and is joint work with Ravi Kokku. Our approach is to create multiple paths between various source-destination pairs by selecting a special subset of relay nodes. We give hardness results and provide some approximation algorithms. This work is motivated by the observation that given two end-host in the Internet there exist potentially many independent or partially overlapping paths between them. However, only one of these is usually used by the underlay routing, leading to many inefficiencies (the single path routings are usually slow to adapt in the presence of fluctuating network conditions). Multi-path routing provides a more adaptive framework, and it also raises a variety of (still open) problems for our enjoyment. Link to a preliminary version of the paper on which this talk is based: http://www-cs-students.stanford.edu/~mihaela/pdfs/mpr-extended.pdf

**5/1: Tim Roughgarden: New connections between bayesian and worst-case auction design****5/8: Bahman Bahmani: Random projection trees and low dimensional manifolds**I will be presenting the STOC '08 paper "Random projection trees and low dimensional manifolds" by Sanjoy Dasgupta and Yoav Freund. The paper proposes two randomized variants of k-d trees and proves that, each of them, on the contrary to the basic k-d tree structure, adapts to the dimensionality of the data set. Due to the time constraints, I will just present the first method, the second being not very dissimilar in essence.

**5/15: Arash Asadpour: Max-min fair allocation of indivisible goods**Resource allocation is an important and interesting problem, whether you wish to cut a cake for your guests, distribute a water resource among farms, or allocate bandwidth in packet routing. These problems provide a wide and deep area for scientific research across disciplines. The area has been touched by measure theory, combinatorics, theoretical computer science, economics, operations research, and so on. In this talk, I will be exploring a main problem in this area: max-min fair allocation of indvisible goods. In this problem, there are agents (e.g., children) and objects (e.g., toys). Each agent has a given value for each object, and the goal is to distribute the objects in order to maximize the minimum value of an agent for his allocation. Though very natural and simple to state, the inherent difficulty of the problem (which mostly arises from the lack of robustness in the solution) has left it almost untouched for a long time. However, recent progress has proved that the combinatorial nature of the problem is very rich. In this talk, I will show how to use matchings in hypergraphs to tackle the problem.

**5/22: Mike Hamburg: General Identity-Based Encryption**Mike Hamburg and Dan Boneh

Since 2001, there have been a number of papers describing new variants on identity-based encryption. We describe a general model for identity-based encryption, unifying the security games of most of these schemes. Furthermore, we describe a new framework for building identity-based schemes for many different scenarios, including a novel mechanism for encrypted email.

**5/29: Aneesh Sharma: Pricing strategies for viral marketing on social networks**We study revenue maximization in the independent cascade model for viral marketing using social networks, where influence propagates through the network via product recommendations. In this model, we can control the "force" with which this influence propagates by choosing differential prices for nodes in the network. The problem of expected revenue maximization turns out to be NP-hard, but we propose an algorithm which has a constant approximation factor.

This is joint work with David Arthur, Rajeev Motwani and Ying Xu.

**6/5: QiQi Yan: An Introduction to EF-Game without Logic**Ehrenfeucht-Fraisse game is an interesting and important tool for characterizing the expressive power of first-order logic. Some variants of EF-game can even be used to characterize complexity classes like P, NP as well. Here in theory lunch (which is NOT logic lunch) however, we will be talking about a variant of EF-game in the context of (generalized) regular expressions (so, NO logic at all!), as well as its application to the (generalized) star height problem. To warm you up, a generalized regular expression (or simply expression) is just a regular expression with possible uses of the complement operator. So we are allowing phi^c to represent Sigma^* \ L(phi) etc. The star height of a regular language is then the minimum nesting depth of stars of an expression representing the language, and the star height problem simply asks if there is a regular language of star height n for any n? Sounds simple hah? You are encouraged to try the cases n=0,1,2 yourself.