## Presentation Order

Below is the order of the student presentations (they’re alphabetical by last name):

• Jitendra Bhandiwad (Wed, Mar 7)
• Gang Chen (Fri, Mar 2)
• Nishant Dholakia (Fri, Mar 9)
• Yuqi Fan (Wed, Mar 21)
• Anup  Kumar (Wed, Mar 28)
• Viswanath  Lolla (Fri, Mar 30)
• Divyansh Madan (Wed, Apr 4)
• Harinath Pathuri (Fri, Apr 6)
• Kushal Satrasala (Wed, Apr 11)
• Ming Shao (Fri, Apr 13)
• Abhijit Srinivas (Wed, Apr 18)
• Manikandan Sundaram (Fri, Apr 20)
• Jiun-Jie Wang (Wed, Apr 25)
• Zilong Ye (Fri, Apr 27)

I will keep this post  as sticky so that it is always the first post and will update the above with the presentation date once they are decided. As I mentioned in class typically on a Friday that you will present next Wednesday.

## Lect 4: Norms

On Friday, we defined the notion of norm over a real vectors and studied some of their properties.

The material was from Lecture 2 of Anna Gilbert’s notes.

## Lect 2: Orthogonal matrices

In today’s lecture, we reviewed some basics of complex matrices and in particular, orthogonal matrices. We then looked at the trivial example of the identity matrix and the non-trivial example of the DFT matrix.

## Lect 1: Introduction

In today’s lecture, we went through an overview of what we will be covering in the course: sparse solutions to equations of the form $Ax=b$, where we have different constraints in the three parameters depending on the application. (We looked at three: image compression, data stream algorithms and compressed sensing.)

The slides for today’s lecture have been uploaded. (Note that once whiteboards are installed in 113A, which should happen sometime next week, I’ll be using the whiteboards and hence there won’t be any slides.)

Today’s material was based in part from these lecture notes from Anna Gilbert’s course.

## Welcome to the class of Spring 2012!

This blog will be the one-stop-shop for everything related to the seminar this spring. You’re strongly encouraged to sign-up for email notification for new posts (click the button on the right panel). It’s your responsibility to make sure you follow all the announcements on the blog. If you already have a wordpress account, you can follow this blog.

Here are the main logistics:

• We will meet Wednesdays and Fridays from 9-10am in Davis 113A. The first meeting will be next Wednesday, Jan 18.
• For the course material, we will follow Anna Gilbert‘s lectures notes from a related course.  Anna is one of the world experts on sparse approximation and compressed sensing and she’ll be blogging about the material as well as some excellent lectures notes on her blog. (Again a link is there on the right panel.)
• Depending on the number of registered students, I will present lectures in about half the meeting and each one of you will present for an hour slot during our normal meeting slot. By default all the material will be from Anna Gilbert’s lecture notes. You can present a research paper that is closely related to the seminar material– however, you will have to get prior approval from me or Hung.

This should be a fun seminar and I’m looking forward to interacting with you over this semester.

If you have any questions/comments/concerns, please feel free to use the comment section of this post.

## Student Presentations

1. Monday Oct 03. Sushen: Section 2 of Lecture 4. Connection between $d$-disjunct matrix construction and the $k$-restriction problem.
2. Wednesday Oct 05.Hung, Section 1 of Lecture 5. Connection between $d$-disjunct matrix construction and the set-cover problem.
3. Monday Oct 10.Erdong: Section 2 of Lecture 5. Strongly explicit construction of disjunct matrices by concatenating the Reed-Solomon code with the identity code.
4. Wednesday Oct 12. Nguyen: Section 3 of Lecture 5. Derandomizing the Gilbert-Varshamov bound’s probabilistic proof.
5. Monday Oct 17. Jesse. coNP-completeness of testing whether a matrix is separable.
6. Wednesday Oct 19. Shishir. Efficient decoding and the notions of list-disjunct and list separable matrices.
7. Monday Oct 24 Aggrey. Upper bound for list-disjunct matrices. Section 2 of lecture 8.
8. Wednesday Oct 26 Eric. Sections 1 & 2 of lecture 9. Recursive construction of list disjunct matrices
9. Monday Oct 31 Atri. Section 1 of lecture 10. List-decoding and list-recoverable codes
10. Wednesday Nov 02 Nikhil. Section 2 of lecture 10. List disjunct matrices from RS-based list recoverable codes
11. Monday Nov 07 Venkata S. Section 3 of lecture 10. List disjunct matrices from PV-based list recoverable codes
12. Wednesday Nov 09 Utkarsh. Section 1 of lecture 11. (At least up to Theorem 1.1) Condensers, extractors, and codes.
13. Monday Nov 14 Sandeep. Section 1 of lecture 11. (The rest of section 1.) List-disjunct matrices from extractors
14. Wednesday Nov 16 Vikramsinh. Section 2 of lecture 11. List-disjunct matrices from expanders
15. Monday Nov 21  Sujith. Application: explicit monotone encodings.
16. Monday Nov 28 We won’t have any presentation on this day due to the move to the new building
17. Mon Dec 05 Weixian. Error tolerant case, part I.
18. Wed Dec 07 Nikhil. Error tolerant case, part II.