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
injective overlap labeling assigns a unique string to each vertex such
that there is an arc from x
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).
- 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
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.
: 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.