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 30-60 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:
    - chip-firing 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

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 one-hour 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 real-world 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 Affine-Invariant 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 self-contained 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 number-theoretic schemes), and in some cases these schemes are secure based on worst-case 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: 278-291
    - Nicholas J. Hopper, Manuel Blum: Secure Human Identification Protocols. ASIACRYPT 2001: 52-66
    - Oded Regev: On lattices, learning with errors, random linear codes, and cryptography. STOC 2005:84-93
    - Henri Gilbert, Matthew J. B. Robshaw, Yannick Seurin: How to Encrypt with the LPN Problem. ICALP (2) 2008: 679-690

  • 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 bits-per-edge 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 clique-star
    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 on-the-fly. 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 win-win 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:
    - chip-firing 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