**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/27: (Organizational)
- 10/4: Don Knuth: Pistols and BDDs
Pistols and BDDs are examples of combinatorial objects that are best counted by defining several layers of one-to-one correspondences to different objects. This talk will examine how these maps are constructed.

- 10/11: Ying Xu: Stochastic Kronecker Graphs
Stochastic Kronecker graphs are a random graph model recently proposed and studied as a model that captures many properties of real-world networks. We analyze basic graph properties of this model, including connectivity, giant component, diameter, searchability.

This is joint work with Mohammad Mahdian from Yahoo!.

- 10/18: Peerapong Dhangwatnotai: A Truthful QPTAS for Related Machine Scheduling
We consider the problem of scheduling jobs on selfish related machines. Our goal is to minimize the makespan -- the maximum completion time. We show that for every fixed epsilon, there exists a truthful mechanism that approximates the makespan within a factor of (1+epsilon) in quasi-polynomial time.

Joint work with Shahar Dobzinski, Shaddin Dughmi, and Tim Roughgarden.

- 10/25: Chris Luhrs: DNA Tile Systems that Heal from Small Fragments
joint work with Ho-Lin Chen, Ashish Goel and Erik Winfree.

Tile systems have proved to be a useful model for understanding self-assembly at the nano scale. Self-healing tile systems, introduced by Winfree, have the property that the self-assembled shape can recover from the loss of arbitrarily many tiles, provided the seed tile of the assembly remains intact and the assembly remains connected. In this talk, we first outline the basic of the Tile assembly model. We then present improved self-healing tile systems for the self-assembly of several interesting classes of shapes, including counters, squares, and Turing-computable shapes. Our tile systems can recover from the loss of arbitrary many tiles, including the seed, provided that a large enough fragment is left intact.

- 11/1: Mike Hamburg: Tagged Finite Automata
Intro CS theory classes teach that regular languages can be implemented either as non-deterministic or deterministic finite automata. But the "regular expressions" used in most programming languages are more powerful than regular languages. At the very least, most regular expressions use capturing parentheses to extract matched substrings (thus making them partial functions, rather than languages). The engines used to implement them additionally support back-references, counted submatches, assertions, and so on. As a result, the regular expression libraries used in practice usually do not use any sort of finite automata. As a result, perl's regular expression engine can take exponential time to match relatively simple regular expressions (the same is true for python, ruby, and prcegrep). Whereas Perl's regexes are NP-hard or worse, extracting captured strings from regular languages is not. A relatively simple algorithm using tagged finite automata (deterministic or non-) has been known for over 20 years, but is not widely implemented.

- 11/8: Hamid Nazerzadeh: Dynamic Cost-Per-Action Mechanisms and Applications to Online Advertising
We examine the problem of allocating a resource repeatedly over time amongst a set of agents. The utility that each agent derives from the consumption of the item is private information to that agent and, prior to consumption, may be unknown even to that agent. The problem is motivated by keyword auctions, where the resource to be allocated is a slot on a search page. We describe a mechanism based on a sampling-based learning algorithm that under suitable assumptions is asymptotically individually rational, asymptotically Bayesian incentive compatible and asymptotically ex-ante efficient. The mechanism can be interpreted as a cost per action keyword auction.

This is a joint work with Amin Saberi and Rakesh Vohra

- 11/15: Ian Post
I'll talk about "Natural Proofs" by Razborov and Rudich, which won the Godel prize earlier this year. They show that assuming one-way functions exist a large class of straightforward, constructive proof techniques is unable to separate certain complexity classes (e.g. P and NP) because the proofs become self-defeating--in proving a lower-bound they simultaneously create an algorithm that solves a very hard problem.

- 11/22: (thanksgiving)
- 11/29: Ioannis Antonellis
We focus on the problem of query rewriting for sponsored search. We base rewrites on a historical click graph that records the ads that have been clicked on in response to past user queries. Given a query q, we first consider Simrank as a way to identify queries similar to q, i.e., queries whose ads a user may be interested in. We argue that Simrank fails to properly identify query similarities in our application, and we present two enhanced version of Simrank: one that exploits weights on click graph edges and another that exploits "evidence". We experimentally evaluate our new schemes against Simrank, using actual click graphs and queries form Yahoo!, and using a variety of metrics. Our results show that the enhanced methods can yield more and better query rewrites.

Joint Work with Hector Garcia-Molina and Chi-Chao Chang

- 12/6: Adam Barth
Web browsers implement a complex security policy that is understood only by very few experts. Many essential security details have been forgotten and reinvented over the past decade, often leaving users at risk. We are in the process of encoding this complex security policy, and corresponding attacker models, in a declarative fragment of Prolog, letting us automatically search for attacks and verify the correctness of defense techniques. In this talk, I'll overview several recent attacks, some forgotten by history and some novel, and present the current state of the model.