SIGTACS - Spring 2009

SIGTACS Seminar Series

SIGTACS is holding a seminar series this semester where group members would present talks on various areas of algorithm and complexity theory.

Back to SIGTACS Home.

Seminar 1 - Average-Case Complexity
Speaker :
Piyush Srivastava

ABSTRACT : In this talk we describe some results in the theory of Average Case Complexity. We first define the notion of distributional NP(dist NP) completeness, present Levin's results on the existence of problems complete for the class dist NP, describe some incompleteness results for problems under distributions close to the uniform distribution, and also present Livne's work on the existence of dist NP complete versions of NP complete problems, along with the discussion of problems in related areas.

  1. The Average case Complexity Forum, maintained by Jie Wang at This contains a list of distNp complete problems, and a discussion of most of what we did.
  2. Yuri Gurevich, Average Case Completeness. A nice survey article available here.
  3. P.S., Average Case Complexity Theory, A project report available at
  4. Andrej Bogdanov and Luca Trevisan, On Worst-Case to Average-Case Reductions for NP Problems, available here.

Seminar 2 - Metric Embeddings and Applications
Speaker : Purushottam Kar

ABSTRACT : In this talk we propose to introduce the area of metric embeddings. From a subfield of functional analysis in the days of Johnson and Lindenstrauss, metric embeddings have since gone on to find wide applicability in Computer Science. We will present some of the classical problems studied in this area and explore the problem of dimensionality reduction in the Euclidean domain in detail.

  1. P.K., Metric Embeddings and Applications in Computer Science, Notes on the material presented in the seminar. Available here.
  2. Jiri Matousek, Embedding finite metric spaces into normed spaces, A nice introduction to the area with pointers to recent results. Available here.
  3. Dimitris Achlioptas, Database Friendly Random Projections, One of the simpler proofs of the Johnson-Lindenstrauss Lemma. Available here.
  4. Nir Ailon and Edo Liberty, Fast Dimension Reduction using Rademacher series on dual BCH codes, A recent result on "fast" random projections, Available here.

Seminars 3-4 - Fourier Analysis and Applications
Speaker : Ramprasad Saptharishi

ABSTRACT : In this talk I hope present a powerful technique, to analyse functions, called 'Fourier Analysis'. We shall look at the definitions, some basic techniques, and a few short and elegant applications of this tool. I'll also leave a few exercises here and there so that people get familiar with the topic; would certainly be useful for other applications.

  1. R.S., Introduction to Fourier Analysis of Boolean Functions, Notes on the material that was presented in the seminar. Available here.
  2. Analysis of Boolean Functions, a course offered by Ryan O'Donnell. Lecture notes available here.

Seminar 5 - List Decoding Reed-Muller Codes over Small Fields
Speaker : Piyush Srivastava

ABSTRACT : In this talk we review the techniques used by Gopalan et al in list decoding Reed-Muller codes over small fields.

  1. P. Gopalan, A.R. Klivans, and D. Zuckerman, List Decoding Reed-Muller Codes over Small Fields, Available here.

Seminar 6 - Poly-logarithmic independence fools AC0 circuits
Speaker : Ramprasad Saptharishi

ABSTRACT : Linial and Nisan, in 1990, conjectured that constant depth polysized circuits (AC0) can be fooled by polylog independence. There was little progress made until Bazzi, in 2007, gave a (64 page) proof of this conjecture for depth two circuits. Razborov subsequently simplified the proof (greatly, made it a 6 page proof). Last month, Mark Braverman settled this conjecture by showing that (log n)^{O(d^2)}-independence fools polysized circuits of depth d. The proof is quite simple and uses a few very neat ideas. The original conjecture is to show that (log n)^{O(d)} fools depth d circuits, and this is still open. Any new ideas in modifying Braverman's proof might shave off the exponent a little.

  1. M. Braverman, Poly-logarithmic independence fools AC0 circuits, Available here.

Seminar 7 - An O(log n) approximation algorithm for SPARSEST CUT
Speaker : Manjish Pal

ABSTRACT : In this talk I will discuss the use of Linear and Semi-definite programming in the field of approximation algorithms via one of the most celebrated open problems in this area, namely the SPARSEST-CUT problem. This problem is NP-hard and hence the objective is to design good approximation algorithms. A seminal result of Leighton and Rao [LR'88] says that there is an $O(log n)$ approximation algorithm for this problem. After 16 years this bound was improved to $\sqrt{log n}$ in a breakthrough paper by Arora, Rao and Vazirani [ARV'04]. The two algorithms are respectively based on the linear and semi-definite programming frameworks. I will discuss the Leighton-Rao algorithm and time permitting will give a sketch of the ARV semi-definite program.

  1. Vazirani, V., Approximation algorithms, A book on approximation algorithms - copi(es) available at the library.
  2. Leighton, T. and Rao, S., Multicommodity Max-Flow Min-Cut Theorems and Their Use in Designing Approximation Algorithms, Available here.
  3. Linial, N., London, E. and Rabinovich, U., The Geometry of graphs and some of its algorithmic applications, Available here.

Seminar 8 - Towards dimension expanders over finite fields
Speaker : Prajakta Nimbhorkar (IMSc,Chennai)

ABSTRACT : The problem is to construct explicit dimension expanders of  "small" size for vector spaces over finite fields. The paper gives two constructions which are algebraic in nature.

  1. Dvir, Z. and Shpilka, A., Towards dimension expanders over finite fields, CCC 2008. Available here.

Seminars 9-10 - Reed-Solomon Codes
Speaker : Chandan Saha

ABSTRACT :  In coding theory one is interested in `encoding' the message, to be communicated, in such a way that at the receiver's end one is also able to `decode' this encoded message to obtain the original message despite substantial number of errors that might creep into the encoded message during its communication. The objective here is to find an efficient encoding/decoding mechanism that maximizes the number of errors that the decoding procedure can handle.
    Reed Solomon Codes provide one such efficient way of encoding and decoding. In a way these codes can handle the optimal number of errors in a communication and are widely used in the industry for error-correcting data in CD/DVDs. In the presentation we plan to first cover algorithms for unique and list decoding of Reed Solomon codes. We'll then see a result that indicates that the number of errors corrected by the list decoding algorithm is optimal.
    The disadvantage of using Reed Solomon codes is that the alphabet size has to be relatively large. We will see how to circumvent this problem by constructing new codes, like Reed Muller and BCH codes, with small alphabet size starting from Reed Solomon codes.

  1. Sudan, M., Lecture Notes for a course on Algebra and Computation. Covers unique decoding of Reed Solomon Codes. Available here.
  2. Sudan, M. and Guruswami, V., Improved Decoding of Reed-Solomon and Algebraic-Geometric codes,
    FOCS 1998. Available here.
  3. Sudan, M., Lecture Notes for a course on Algorithmic Introduction to Coding Theory. Covers BCH Codes. Available here.

Seminar 11 - A simple and linear time randomized algorithm for MST
Speaker : Prof. Surender Baswana

ABSTRACT : MST has been a classical and fundamental algorithmic problem. Given an undirected weighted graph G=(V,E) on n=|V| vertices and m=|E| edges, the aim is to compute minimum spanning tree (MST). There does not exist any linear (in n and m) time deterministic algorithm. However, 15 years ago, a simple and linear time randomized algorithm was designed by Karger, Klein and Tarjan. The algorithm is based on the following key result, which is somewhat counter intuitive.
    Let G=(V,E) be an undirected weighted graph on n vertices and m edges. Suppose we select each edge randomly with probability 1/2, and let A be the subset of edges selected, and B=E-A is the set of edges which were not selected. The question is the following : How close MST of A is to MST of the original graph. More specifically, What is the expected number of edges in B which can improve the MST of A ? We say that an edge e from B improves MST of A if MST(A) is not MST(A+{e}).
    The answer is that there are only expected 2n edges in B which can improve the MST of A. The proof of this result is amazingly simple and beautiful.

Seminar 12 - Approximating arbitrary metrics by tree metrics
Speaker : Prof. Surender Baswana

ABSTRACT : Given any arbitrary metric on n points, the metric can be embedded into a distribution over dominating tree metrics such that the expected stretch of each edge is O(\log n). This result is existentially tight also.
    We shall also briefly discuss the following problem which is somewhat related to the above problem : Given a weighted graph on n vertices, compute its spanning tree which achieves O(\polylog n) bound on the average stretch. There exists an algorithm for this (most recent in FOCS 2008). However, it would be interesting to explore if we can have simpler algorithm for this problem, also because the current algorithm does not seem to be extensible to dynamic scenario.

  1. Fakcharoenphol, J., Rao, S. and Talwar, K., A tight bound on approximating arbitrary metrics by tree metrics, STOC 2003. Available here.