Theoretical Computer Science Group

Theory Seminar Schedule for Fall 2015

The weekly Theory seminar provides an opportunity to get exposed to cutting edge research in theoretical computer science, to learn to understand technical material from talks and to give technical presentations. Graduate students interested in doing research in algorithms, complexity theory, cryptography, quantum computing and related areas are strongly encouraged to attend.

Date Speaker Title
August 24 Paul Medvedev (PSU) On the Readability of Overlap Digraphs
August 31 Yanxi Liu (PSU) Wallpaper Group-based Human Perception of Regular Patterns from EEG Data
September 9 Eunou Lee (PSU) A nearly optimal approximation algorithm for 3LIN
September 14 Nithin Varma (PSU) TBD
September 21 Mary Wootters (CMU) TBD
September 28 Jamie Morgenstern (UPenn) The Pseudo-Dimension of Near-Optimal Auctions
October 5 Nai-Hui Chia (PSU) TBD
October 12 Sampath Kannan (UPenn) TBD
October 19 FOCS, no seminar
October 26 Ishan Behoora (PSU) TBD
October 28 Bobby Kleinberg (Cornell) TBD
November 2 Chandra Chekuri (Illinois) TBD
November 9 Ramesh Krishnan (PSU) TBD
November 16 Roksana Baleshzar (PSU) TBD
November 23 Thanksgiving week, no seminar
November 30 No seminar
December 2 Michael Langberg (SUNY Buffalo) TBD
December 7 TBD TBD

Spring 2007     Fall 2007     Spring 2008     Summer 2008     Fall 2008     Spring 2009     Fall 2009     Spring 2010     Fall 2010     Spring 2011     Fall 2011     Spring 2012     Fall 2012     Spring 2013     Fall 2013     Fall 2014     Spring 2015

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.