Theory Students' Lunch Fall 2008
Previous semesters: Fall 2007 & Spring 2008 2006 2004 2003 List of suggested papers
Time: Fridays Noon
Current Themes
None
Format
This semester, we will try to get people discuss more and the speaker speak less. The talk will take about 3060 minutes (discussion is not included). The speaker is free to pick anything he wants to present, including technical papers, survey papers, and books. If preferred, people may present in pair. Proposed formats include:
 Your own work or practice talk.
 Paper(s) you just read.
 SYSKO ("Stuff" You Should Know Of).
 Survey of some area.
 Rump Sessions  Many short presentations.
 Theory Jam Sessions  Group collaboration on open problems.
Suggested Papers If you have any paper you want to hear about, please send a suggestion to danupon at gmail dot com.For the list of suggested papers, click here.
Upcoming Talks
 Nov. 21 Noon Klaus 2124: Farbod Shokrieh. Algebraic Graph Theory: An Introduction and Some Recent Results.
I will talk about the following concepts:
 chipfiring games.
 critical and reduced divisors on graphs and related algorithms.
 Jacobian, which is a finite group attached to any given graph.
As application:
 I will show how one can use these tools to pick (efficiently) a random (uniformly) spanning tree of a given graph.

I will also talk about the potential use of Jacobian for cryptography
and some relationship with number of points on elliptic curves.
I assume no background knowledge on the subject.  Soon: Subruk
I will talk about the following concepts:
 chipfiring games.
 critical and reduced divisors on graphs and related algorithms.
 Jacobian, which is a finite group attached to any given graph.
As application:
 I will show how one can use these tools to pick (efficiently) a random (uniformly) spanning tree of a given graph.
 I will also talk about the potential use of Jacobian for cryptography and some relationship with number of points on elliptic curves.
I assume no background knowledge on the subject.
All Talks
 Sep. 12, Noon, Klaus 1212
Atish Das Samar will present his PODS best paper, Estimating PageRank on Graph Streams. He will present the onehour version of the talk he just gave earlier this week at Perdue and give some open problems for a discussion.
 Sep. 18 (THURSDAY), Noon, Klaus 2124 (Theory Lab)
Shiva Kintali will talk about the paper "Natural Proofs" by Razborov and Rudich (Gödel Prize 2007). The goal is to discuss about some open problems. He will explain some background and give some open problems for us to discuss.  Sep. 26, Noon, Klaus 2108 (NOT theory lab)
Gagan Goel will present his FOCS paper (with Deeparnab Chakrabarty)
"On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP"
There are tons of open questions that he will give us to discuss during/after the talk.  Oct. 3, Canceled.
 Oct. 10, Noon, Klaus 2124 (Theory Lab)
Danupon Nanongkai will present under the topic "An Introduction to Communication Complexity and its applications".
The main goal of the talk is to introduce the notion of communication complexity and show how to use it in various applications. Later, depending on time constraint, some lower bound results of the paper "The Space Complexity of Approximating the Frequency Moments" by Alon, Matias and Szegedy (STOC96, Gödel Prize 2005) will be presented.
 Oct. 17 Noon, Klaus 2124 (Theory Lab)
Adam O'Neill. "Rational Cryptography"
Abstract: A classical problem in cryptography (called secure function evaluation or SFE) is as follows: There are n players P_1,...,P_n, each of whom have a corresponding input x_i. They wish to compute some function f(x_1,...,x_n) of their inputs. However, the inputs represent some sensitive information and they are not willing to simply exchange them. Since the 80's, cryptographers studied ways to allow them to compute f(x_1,...,x_n) while maintaining privacy. In this classical study it is assumed that some players are "totally honest" and the rest are "totally arbitrary." A drawback of this approach, however, is that some desirable properties of SFE protocols are very difficult to achieve. (E.g., they require more than half the players to be totally honest, which does not seem like a reasonable assumption in many realworld scenarios.) This motivates looking at alternative models. A recent and exciting approach is applying game theory to model the SFE problem, where players have utility functions that they try to maximize. An advantage of this approach is that the players (unlike ones that are totally arbitrary) may be "punished" by the others for deviating from the protocol. In this talk, we discuss some prior and current work in this emerging area and future directions.  Oct. 24: Noon Klaus 2108
Two Practice talks for FOCS'08:
1. Spencer Charles Brubaker:
Isotropic PCA and AffineInvariant Clustering
S. Charles Brubaker and Santosh S. Vempala pdf
2. Gagan Goel
"On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP" (with Deeparnab Chakrabarty)  Oct. 31 Noon, Klaus 2124 (Theory Lab)
David Cash. Cryptography From Learning Problems
This will be a selfcontained talk covering some simple results on constructing secure schemes whose security relies on the hardness of computational learning problems. These constructions are interesting for both theoretical and practical reasons.
1) On the theoretical side, these schemes offer the possibility of security even if quantum computers are developed (in contrast to numbertheoretic schemes), and in some cases these schemes are secure based on worstcase hardness (in contrast to the usual average case hardness  there exist possible worlds where problems are hard in the worst case but not on average).
2) On the practical side, these schemes are very computationally efficient. In some cases, a protocol execution involves only a few thousand XOR and OR bit operations, and some protocols are even
efficient enough to run on RFID tags. I will cover the basics of crypto and learning problems. Then I will run through simple examples of schemes. If there's time and interest I'll talk about my research, including some open problems.
REFERENCES
 Avrim Blum, Merrick L. Furst, Michael J. Kearns, Richard J. Lipton:
Cryptographic Primitives Based on Hard Learning Problems. CRYPTO 1993:
278291
 Nicholas J. Hopper, Manuel Blum: Secure Human Identification Protocols. ASIACRYPT 2001: 5266
 Oded Regev: On lattices, learning with errors, random linear codes, and cryptography. STOC 2005:8493
 Henri Gilbert, Matthew J. B. Robshaw, Yannick Seurin: How to Encrypt with the LPN Problem. ICALP (2) 2008: 679690
 Nov. 18 (Tuesday) Noon, Klaus 2124 (Theory Lab)
Chinmay Karade: Speeding up Algorithms on Compressed Graphs
I will present my work at Microsoft.
Graph compression has been widely studied from the point of view of
storage reduction. Most studies attempt to optimize the binary
representation of the Graph, measured by bitsperedge required to
store it. Structural compression schemes on the other hand modify the
graph to add or delete vertices and edges, still maintaining the
topology. Our work is based on compressions that use the cliquestar
primitive  replacing a clique by a star to reduce the number of
edges stored.
One option when designing an algorithm that uses a compressed graph is
to decompress it onthefly. This fails to give us any runtime
advantage. Our goal was to design algorithms that work on the
compressed graph, to yield results on the original uncompressed graph.
This is a winwin situation  the dedicated algorithm running on a
smaller graph saves computation as well as storage.
We have two main results:
1) A scheme that allows us to compute the matrix vector product E^Tx
for any vector x and the adjacency matrix E of a graph G. This routine
requires access to only E*, the (smaller) adjacency matrix of the
compressed graph G* and runs in time proportional to size of the
smaller graph.
2) A completely asynchronized method to implement stochastic processes
using the compressed version of a graph.
Nov. 21 Noon Klaus 2124:
Farbod Shokrieh. Algebraic Graph Theory: An Introduction and Some Recent Results.
I will talk about the following concepts:
 chipfiring games.
 critical and reduced divisors on graphs and related algorithms.
 Jacobian, which is a finite group attached to any given graph.
As application:
 I will show how one can use these tools to pick (efficiently) a random (uniformly) spanning tree of a given graph.

I will also talk about the potential use of Jacobian for cryptography
and some relationship with number of points on elliptic curves.
I assume no background knowledge on the subject.
 Nov. 28 Holiday
 Dec. 5
Atish Das Samar will present his PODS best paper, Estimating PageRank on Graph Streams. He will present the onehour version of the talk he just gave earlier this week at Perdue and give some open problems for a discussion.
Shiva Kintali will talk about the paper "Natural Proofs" by Razborov and Rudich (Gödel Prize 2007). The goal is to discuss about some open problems. He will explain some background and give some open problems for us to discuss.
Gagan Goel will present his FOCS paper (with Deeparnab Chakrabarty)
"On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP"
There are tons of open questions that he will give us to discuss during/after the talk.
Danupon Nanongkai will present under the topic "An Introduction to Communication Complexity and its applications".
The main goal of the talk is to introduce the notion of communication complexity and show how to use it in various applications. Later, depending on time constraint, some lower bound results of the paper "The Space Complexity of Approximating the Frequency Moments" by Alon, Matias and Szegedy (STOC96, Gödel Prize 2005) will be presented.
Adam O'Neill. "Rational Cryptography"
Abstract: A classical problem in cryptography (called secure function evaluation or SFE) is as follows: There are n players P_1,...,P_n, each of whom have a corresponding input x_i. They wish to compute some function f(x_1,...,x_n) of their inputs. However, the inputs represent some sensitive information and they are not willing to simply exchange them. Since the 80's, cryptographers studied ways to allow them to compute f(x_1,...,x_n) while maintaining privacy. In this classical study it is assumed that some players are "totally honest" and the rest are "totally arbitrary." A drawback of this approach, however, is that some desirable properties of SFE protocols are very difficult to achieve. (E.g., they require more than half the players to be totally honest, which does not seem like a reasonable assumption in many realworld scenarios.) This motivates looking at alternative models. A recent and exciting approach is applying game theory to model the SFE problem, where players have utility functions that they try to maximize. An advantage of this approach is that the players (unlike ones that are totally arbitrary) may be "punished" by the others for deviating from the protocol. In this talk, we discuss some prior and current work in this emerging area and future directions.
Two Practice talks for FOCS'08:
1. Spencer Charles Brubaker:
Isotropic PCA and AffineInvariant Clustering
S. Charles Brubaker and Santosh S. Vempala pdf
2. Gagan Goel
"On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP" (with Deeparnab Chakrabarty)
David Cash. Cryptography From Learning Problems
This will be a selfcontained talk covering some simple results on constructing secure schemes whose security relies on the hardness of computational learning problems. These constructions are interesting for both theoretical and practical reasons.
1) On the theoretical side, these schemes offer the possibility of security even if quantum computers are developed (in contrast to numbertheoretic schemes), and in some cases these schemes are secure based on worstcase hardness (in contrast to the usual average case hardness  there exist possible worlds where problems are hard in the worst case but not on average).
2) On the practical side, these schemes are very computationally efficient. In some cases, a protocol execution involves only a few thousand XOR and OR bit operations, and some protocols are even
efficient enough to run on RFID tags. I will cover the basics of crypto and learning problems. Then I will run through simple examples of schemes. If there's time and interest I'll talk about my research, including some open problems.
REFERENCES
 Avrim Blum, Merrick L. Furst, Michael J. Kearns, Richard J. Lipton: Cryptographic Primitives Based on Hard Learning Problems. CRYPTO 1993: 278291
 Nicholas J. Hopper, Manuel Blum: Secure Human Identification Protocols. ASIACRYPT 2001: 5266
 Oded Regev: On lattices, learning with errors, random linear codes, and cryptography. STOC 2005:8493
 Henri Gilbert, Matthew J. B. Robshaw, Yannick Seurin: How to Encrypt with the LPN Problem. ICALP (2) 2008: 679690
Chinmay Karade: Speeding up Algorithms on Compressed Graphs
I will present my work at Microsoft.
Graph compression has been widely studied from the point of view of
storage reduction. Most studies attempt to optimize the binary
representation of the Graph, measured by bitsperedge required to
store it. Structural compression schemes on the other hand modify the
graph to add or delete vertices and edges, still maintaining the
topology. Our work is based on compressions that use the cliquestar
primitive  replacing a clique by a star to reduce the number of
edges stored.
One option when designing an algorithm that uses a compressed graph is
to decompress it onthefly. This fails to give us any runtime
advantage. Our goal was to design algorithms that work on the
compressed graph, to yield results on the original uncompressed graph.
This is a winwin situation  the dedicated algorithm running on a
smaller graph saves computation as well as storage.
We have two main results:
1) A scheme that allows us to compute the matrix vector product E^Tx
for any vector x and the adjacency matrix E of a graph G. This routine
requires access to only E*, the (smaller) adjacency matrix of the
compressed graph G* and runs in time proportional to size of the
smaller graph.
2) A completely asynchronized method to implement stochastic processes
using the compressed version of a graph.