## On the Readability of Overlap Digraphs

We introduce the graph parameter readability and study it as a function of the number of vertices in a graph. Given a digraph*D*, an injective overlap labeling assigns a unique string to each vertex such that there is an arc from

*x*to

*y*if and only if

*x*properly overlaps

*y*. The readability of

*D*is the minimum string length for which an injective overlap labeling exists. In applications that utilize overlap digraphs (

*e.g.*, in bioinformatics), readability reflects the length of the strings from which the overlap digraph is constructed.

We study the asymptotic behavior of readability by casting it in purely graph theoretic terms (without any reference to strings). We prove upper and lower bounds on readability for certain graph families and general graphs.

This is joint work with Rayan Chikhi, Martin Milanic, and Sofya Raskhodnikova.

## Wallpaper Group-based Human Perception of Regular Patterns from EEG Data

Mathematicians have long proven that there is a finite number of crystallographic groups associated with all possible periodical patterns in N-dimensional Euclidean space, while little is known on how human perceive such patterns and how the regular patterns are organized in human brain. We explore human perception using, systematically, wallpaper patterns as stimuli and collect electroencephalogram (EEG) responses of human brain directly. Our initial analysis of the EEG data through machine learning, MDS and minimum/maximum spanning tree extraction leads to surprising graph-representation resemblance between the subgroup hierarchy of the 17 wallpaper groups and the human neural responses (EEG data) to the corresponding wallpaper patterns.Joint work of Chris Funk (PSU), Peter Jes Kohler (Stanford), Anthony Norcia (Stanford).

Helpful links:

- For a quick look on wallpaper groups, see chapter 2 of this survey paper on "computational symmetry".

- For some background/related information on our NSF grant of 'Symmetry Group-based Regularity Perception in Human and Computer Vision', check out this project page.

## A nearly optimal approximation algorithm for 3LIN

Suppose we are given a system of linear equations each having 3 variables on Z_2. The problem 3LIn is to come with an assignment to the variables that satisfies the maximum fraction of equations. Random guessing will satisfy half of equations. Can we do better? This talk will be about an algorithm that nearly matches NP-hardness result on approximation ratio. The algorithm is from Håstad’s work.## The Pseudo-Dimension of Near-Optimal Auctions

In the traditional economic approach to identifying a revenue-maximizing auction, one first posits a prior distribution over all unknown information, in particular, the values of buyers in the market, and then solves for the auction that maximizes expected revenue with respect to this distribution. The first obstacle to making this approach operational is the difficulty of formulating an appropriate prior. The second obstacle is that, even if an appropriate prior distribution is available, the corresponding optimal auction can be far too complex and unintuitive for practical use. This motivates the goal of identifying auctions that are “simple” and yet nearly-optimal in terms of expected revenue.In this talk, I will describe recent work that simultaneously addresses these two difficulties, using techniques from statistical learning theory to design auction classes. Formally, we design a parametric class of auctions which trades off between the pseudo-dimension of the class and the revenue optimality of the best auction within that class. This approach allows one to state precisely how much data is needed about buyers in order to learn a revenue-optimal auction from a class of auctions, and also gives a precise measure of the relative simplicity of a class of auctions.

This work is joint with Tim Roughgarden of Stanford University.

**Speaker Bio**: Jamie Morgenstern is a Warren fellow in computer science at the University of Pennsylvania, hosted by Michael Kearns, Aaron Roth, and Rakesh Vohra. She recently completed her PhD working with Avrim Blum at Carnegie Mellon University. Her interests lie within the area of theoretical computer science; more specifically, she spends a lot of her time thinking about mechanism design, learning, algorithmic game theory, privacy, and approximation algorithms.