**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. **

**9/25: Organizational****10/2: Mukund Sundararajan: Optimal Privacy Mechanisms**How accurately can we answer queries while simultaneously protecting sensitive information? We consider a bayesian view of accuracy and identify optimal mechanisms for a class of queries called count queries. We identify a mechanism that is simultaneously optimal for all priors and penalty functions (these model tolerance for inaccuracy) the querying agent may have. The main proof idea is to show that the optimal mechanism is the solution to a linear program with nice properties.

**10/9: Don Knuth: Sweet Functions****10/16: Janina Brenner: Cooperative Cost Sharing via Singleton Mechanisms**I will talk about results from a recent paper in which we present a generic method to turn approximation algorithms into cooperative cost sharing mechanisms. The resulting "singleton" mechanisms preserve the approximation factor in terms of their budget balance guarantee and perform surprisingly well e.g. for completion time scheduling problems. They are a subclass of acyclic mechanisms as recently introduced by Roughgarden et al. This is joint work with Guido Schaefer.

**10/23: Mikhail Kapralov: Perfect matchings via uniform sampling in regular bipartite graphs**We further investigate the well-studied problem of finding a perfect matching in a regular bipartite graph. The first non-trivial algorithm, with running time $O(mn)$, dates back to Konig's work in 1916 (here $m=nd$ is the number of edges in the graph, $2n$ is the number of vertices, and $d$ is the degree of each node). The currently most efficient algorithm takes time $O(m)$, and is due to Cole, Ost, and Schirra. We improve this running time to $O(\min\{m, \frac{n^{2.5}\ln n}{d}\})$; this minimum can never be larger than $O(n^{1.75}\sqrt{\ln n})$. We obtain this improvement by proving a uniform sampling theorem: if we sample each edge in a $d$-regular bipartite graph independently with a probability $p = O(\frac{n\ln n}{d2})$ then the resulting graph has a perfect matching with high probability. The proof involves a decomposition of the graph into pieces which are guaranteed to have many perfect matchings but do not have any small cuts. We then establish a correspondence between potential witnesses to non-existence of a matching (after sampling) in any piece and cuts of comparable size in that same piece. Karger's sampling theorem for preserving cuts in a graph can now be adapted to prove our uniform sampling theorem for preserving perfect matchings. Using the $O(m\sqrt{n})$ algorithm (due to Hopcroft and Karp) for finding maximum matchings in bipartite graphs on the sampled graph then yields the stated running time. We also provide an infinite family of instances to show that our uniform sampling result is tight up to poly-logarithmic factors (in fact, up to $\ln2 n$).

This is joint work with Ashish Goel and Sanjeev Khanna.

**10/30: Martin Hoefer: Stackelberg Network Pricing**I will present some recent results on network pricing problems. In a so-called Stackelberg setting, a leader (seller) can set prices for a subset of m pricable edges in a graph. The other edges have a publicly known fixed cost. Based on the leader's decision one or more followers (customers) optimize a polynomial-time solvable combinatorial minimization problem and choose a minimum cost solution satisfying their requirements. The leader receives as revenue the total amount of prices paid by the customers for pricable edges in their solutions. Our first result is a tight analysis of a single-price algorithm for revenue maximization with a single follower, which provides a (1+\eps)\log m approximation for any constant \eps > 0. This can be extended to a (1+\eps)(\log k + \log m)-approximation for k followers. For the latter we show almost matching hardness results. Our second result is that in case of a single follower in Stackelberg bipartite vertex cover, there is an efficient algorithm to compute optimum pricies using LP-duality techniques. It can be extended to provide constant-factor approximations for any constant number of followers.

This is joint work with Patrick Briest and Piotr Krysta.

**11/6: Arash Asadpour: Stochastic Submodular Maximization**will talk about stochastic submodular maximization problem with respect to a cardinality constraint. The model can capture the eﬀect of uncertainty in diﬀerent problems, such as cascade eﬀects in social networks, capital budgeting, sensor placement, etc. I will discuss non-adaptive and adaptive policies and show how one can get the optimal constant approximation algorithms for both cases. I will also present upperbound and lowerbound for the adaptivity gap (i.e. how far the outcome of best adaptive and non-adaptive policies can be from each other).

Joint work with Hamid Nazerzadeh and Amin Saberi

**11/13: T.C. Hu**The optimal solutions of the knapsack problem have a periodic structure when the weight-carrying capacity b is sufficiently large. We give a new algorithm of complexity O( n w) for finding the onsite of optimal periodic structure,and a new algorithm of complexity O( n v w) for finding optimal solutions when b is small. The w and v are the weight and value of the best item. These ideas extended to integer programming where most instances of an integer program can be solved in polynomial time but there exists a percentage of instances which cannot.

**11/20: Peter Hawkins**Shape analyses are a powerful class of program analysis techniques that aim to represent and reason about the "shape" of a program's data structures as it executes. A variety of approaches exist, largely based on expressive but complicated logics. In this talk we propose Hierarchical Shape Graphs (HSGs), which are a new graphical representation for memory states based on a hierarchy of nested graphs. We argue that HSGs are a simple, intuitive representation for data structures, which correspond well with the kinds of informal pictures that a programmer might draw to describe their data. HSGs represent unbounded data structures by combining sets of isomorphic subgraphs into summary descriptions, and are capable of precisely describing many common data structures (e.g. singly-linked and doubly-linked lists, arrays, and trees). HSGs can also succinctly describe nested data structures (e.g. an array of lists), and shared data structures (e.g. a set of people on two lists, ordered by last name and SSN), which are challenging to handle using existing techniques.

No knowledge of program analysis will be assumed.

**11/27: Thanksgiving****12/4: Ian Post**Suppose we are given a weighted graph, a set of source nodes, and a root and want to route 1 unit of information from each source to the root where the cost of using an edge is some concave, non-decreasing function of the number of sources routing through that edge. I'll talk about an algorithm for finding a single tree that approximates the optimum for all such cost functions simultaneously.