Tuesday, October 4, 2011

Wish List


Topics I would like to learn about:
  1. Multiplicative weights update method.[link]
  2. Semi-definite programming.
  3. Natural Proofs--I know nothing about this, but sounds interesting.
  4. What are the common ways of exploiting planarity in design of algorithms?
  5. Derandomization/Random walks/Expanders.

Topics I would like to give talks on:

  1. Lower bounds for Element distinctness Problem.
    Consider the following problem: Given an array of n elements x1,..,xn decide if xi=xj for some i≠j. Prove that any comparison-based algorithm takes at least Ω(nlogn) operations to decide if all the elements are distinct.
  2. Trade-off revealing LPs
  3. Lower bounds for Linear Satisfiability. An Ω(nr/2) lower bound for the following problem: For some fixed linear equation in r variables, given a set of n real numbers, do any r of them satisfy the equation? [ pdf ]
  4. Broadcast scheduling on paths. A problem I was initially working on..there is a small gap in bounds and I would like to solicit ideas for improvement.
  5. Farkas Lemma and its applications.
  6. Introduction to Matroids.



--Jagadish



Topics I would like to see presented:
  1. "A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations" by Daniele Micciancio and Panagiotis Voulgaris, a breakthrough result on the shortest vector problem. [ pdf ]
  2. Proof(s) of the Borsuk Ulam theorem, a generalization of Brouwer's fixed point theorem to arbitrary dimensions.[ pdf ] Another excellent source is the book by Matousek, titled "Using the Borsuk-Ulam theorem".
  3. An intro to entropy and information theory.
  4. Szemeredi's regularity lemma and applications.
Note: I am willing to discuss on the Micciancio-Voulgaris paper.

Topics I would like to present:

  1. Expanders.
  2. Linear algebraic methods in combinatorics.
  3. The Guth-Katz bound on the Erdős distance problem: Terrence Tao has a nice expository post. This is a complex proof and I could use some help.
  4. Extractors and derandomization.
--Aravind



Topics I would like to see presented:
  1. Interior point methods to solve convex optimization problems
  2. UGC, hardness of approximation
  3. SDPs
  4. Expanders
  5. PCP theorem :D
Topics I would like to present:
  1. Two player games and Lemke-Howson algorithm
  2. PPAD problems and properties
  3. Lemke's algorithm

-Ruta.

Posted by at

3 comments:

  1. AravindOctober 7, 2011 at 9:31 AM

    @Jagadish:

    The topics look interesting. About your wish list - I can present expanders and related stuff. I think Ayush is interested in presenting SDPs.
    Can you be more specific about "exploiting planarity" in algorithm design?

    I am not able to create a post, so I'll mention my list of topics here:

    Topics I'd like to see presented:

    1. The paper "A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations" by Daniele Micciancio and Panagiotis Voulgaris, a breakthrough result on the shortest vector problem.
    Link: http://cseweb.ucsd.edu/~daniele/papers/Voronoi.pdf

    2. Proof(s) of the Borsuk Ulam theorem, a generalization of Brouwer's fixed point theorem to arbitrary dimensions.
    Link: http://www.math.neu.edu/~king_chris/Borsuk-Ulam.pdf
    Another excellent source is the book by Matousek, titled "Using the Borsuk-Ulam theorem".

    3. An intro to entropy and information theory
    4. Szemeredi's regularity lemma and applications

    Note: I am willing to discuss on the Micciancio-Voulgaris paper.

    Topics I'd like to present:

    1. Expanders.
    2. Linear algebraic methods in combinatorics.

    3. The Guth-Katz bound on the Erdős distance problem: Terrence Tao has a nice expository post at http://terrytao.wordpress.com/2010/11/20/the-guth-katz-bound-on-the-erdos-distance-problem/.
    This is a complex proof and I could use some help.

    4. Extractors and derandomization.

    ReplyDelete
  2. JagadishOctober 9, 2011 at 7:08 AM

    I've sent you an invite.

    > Can you be more specific about "exploiting planarity" in algorithm design?

    A specific classes of graphs usually have some nice properties that are useful in designing fast algorithms. For example, running intersection property of chordal graphs, umbrella property for proper interval graphs, etc. I would like to know which properties, if any, of planar graphs make them amenable to efficient algorithms.

    ReplyDelete
  3. Ashish ChiplunkarOctober 19, 2011 at 12:16 AM

    Talks I would like to present:

    1. Wedge products and the proof of skew Bollobás' theorem.
    2. Online graph traversal and its equivalence with MSS.

    Topic I would like to understand through discussions in theorychat: Dinur's proof of PCP theorem.

    ReplyDelete

Subscribe to: Post Comments (Atom)