**Topics I would like to learn about:**

- Multiplicative weights update method.[link]
- Semi-definite programming.
- Natural Proofs--
*I know nothing about this, but sounds interesting.* - What are the common ways of exploiting planarity in design of algorithms?
- Derandomization/Random walks/Expanders.

**Topics I would like to give talks on:**

- Lower bounds for Element distinctness Problem.

Consider the following problem: Given an array of*n*elements*x*decide if_{1},..,x_{n}*x*for some_{i}=x_{j}*i≠j*. Prove that any comparison-based algorithm takes at least Ω(*n*log*n*) operations to decide if all the elements are distinct. - Trade-off revealing LPs
- Lower bounds for Linear Satisfiability. An Ω(
*n*) lower bound for the following problem: For some fixed linear equation in^{r/2}*r*variables, given a set of*n*real numbers, do any*r*of them satisfy the equation? [ pdf ] - 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.* - Farkas Lemma and its applications.
- Introduction to Matroids.

--Jagadish

-Ruta.**Topics I would like to see presented:**

- "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 ]
- 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".
- An intro to entropy and information theory
*.* - Szemeredi's regularity lemma and applications.

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

**Topics I would like to present:**

- Expanders.
- Linear algebraic methods in combinatorics.
- 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*. - Extractors and derandomization.

Topics I would like to see presented:

Topics I would like to see presented:

- Interior point methods to solve convex optimization problems
- UGC, hardness of approximation
- SDPs
- Expanders
- PCP theorem :D

**Topics I would like to present:**

- Two player games and Lemke-Howson algorithm
- PPAD problems and properties
- Lemke's algorithm

@Jagadish:

ReplyDeleteThe 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.

I've sent you an invite.

ReplyDelete> 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.

Talks I would like to present:

ReplyDelete1. 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.