Final Project and Presentations
Here are some guidelines for choosing the topic and working on the project.- The participants are required to form groups size 2 each to work on the project.
- The number within bracket for each topic indicates suggested number of people taking it up. If it is 2, only a group can take it up. If it is 1, then the other member of that group should choose a different topic and the team should work together on both the topics.
- Please select your topic and inform me on or before Apr 1, 2011, 5pm.
- Allotment is on a FIFO mode. This color indicates the topic is already taken up !.
- All participants crediting this course are required to choose a topic to work on and the work and the presentation will contribute to 25% of the grading process.
- It is highly recommended that the auditors also choose a topic to work on and do the presentations, in order to take the full advantage of the course.
- A tentative schedule for project presentations.
Suggested Topics for Final Project
18 topics (5 from Themes 1-3, 5 from Theme 4, 3 from Theme 5 and 5 extra topics)Topics in Theme 1-3 : Structural Complexity and Space Complexity:
- Crossing Sequence Arguments in
Complexity Theory(1) - Assigned to Balagopal Komarath-: This project
aims to explore the applications of crossing sequences in complexity
theory. A good starting point is this lecture by
Katz.
-
Applications of Pebbling Games in Complexity Theory (1) - Assigned
to Praneel Raja: This project aims to explore use of pebbling games in
complexity theory. One of the main result is that DTIME(t) is contained in DSPACE(t/log t)
whose proof uses some combinatorial arguments using Pebbling. The original
results are quite old, but there has been some recent
developments related to this. First, and second paper may be required
for the presentation.
- Page 264, Section 19.2 of Goldreich's notes.
- Use of Pebbling to show that not all non-deterministic linear time computations can be simulated in deterministic linear time.
- Optional Reading : Further extensions of this.
- Universal Traversal Sequences(1) : A vertex sequence is a (d,n) universal traversal sequence
for a family of graphs G, if for any labelled d-regular graph on n vertices in G, starting with the
vertex v in V, and following the sequence instructions leads to visiting all the vertices in the graph.
This project explores the existence and constructions of such sequences, and their consequences:
- Lecture Notes
- Universal Traversal Sequences for Expander Graphs - Shlomo Hoory and Avi Wigderson
- Structural Properties of
PP (1) - Assigned to Gaurav Maheswary
This is a classical topic which goes back to the basic randomized algorithms. We skipped over some important structural properties of the class PP in class. This project is to explore the stronger form of these results that uses the power of "polynomials" again. The reference is: PP is closed under intersection by Richard Beigel, Nick Reingold, and Daniel Spielman. (STOC 1991, JCSS 1995) - Zero Knowledge Proof Systems (1) - Assigned to Kritika Ramaswamy and Prateek Barapatre: We will see interactive proofs briefly in this course. This project explores another related area which is important from the complexity theory and cryptography perspective. This area is vast, but this project could read up the basics. The specific reading can be fixed in a discussion with the instructor.
- Polylog Threshold is in
AC^0(1) - Assigned to Nalini Behera
We saw that majority is the hardest of the threshold functions while the special cases like OR and AND are in AC^0. This project is to explore extensions of this to other restricted cases threshold function that can be computed in AC^0. References are not available online, and is available with the instructor. - Discrepancy Method in Lower
Bounds(1) - Assigned to Abhinay Sama
This is to explore applications of Discrepancy methods in circuit lower bounds, especially lower bounds against threshold circuits. For example, it can be shown that the inner product function cannot be computed by threhsold gates of depth 2 in poly size. References are available with the instructor. - Amplifying Lower bounds by Self-reducibility (1) - :
This project aims to explore an exciting recent development in the circuit lower bounds against TC^0 and
NC^1 which showed it suffices to prove superlinear size lower bounds in certain contexts to obtain
superpolynomial size lower bounds.
- Amplifying Lower Bounds by Means of Self-Reducibility - Eric Allender, Michal Koucky.
- New Surprises from Self-reducibility - Eric Allender.
- Monotone circuit lower
bounds (2) -(Assigned to Rikin and Ashish) - :
This project is to explore circuit lower bounds against monotone circuits.
The sample references are :
- Lecture Notes by Ramprasad Saptarshi from Arvind's course. The course textbook also has a neat presentation of the introductory material. The original result is due to Razborov.
- Monotone Circuits for Connectivity Requires Super-logarithmic Depth - Karchmer, Wigderson (SIDM 1990).
- Communication Complexity and Monotone Depth - an expository article by Stasys Jukna.
- Evasive Functions (1): A Boolean function is said to be evasive if every decision tree is of depth at least n. This project explores the property of evasiveness. Here is a specific reference for the topic of evasiveness of graph properties.
The presentations of this set of topics (from Theme 5) will align well with the course plan if they are done after Apr 15th.
- Derandomizing Space Bounded Computations (2):
This project explores derandomization in the space domain which uses different techniques as
compared to the time domain. Some references:
- RL is contained in SC - Noam Nisan.
- BPSPACE(s) subseteq DSPACE(s^1.5) Michael E. Saks, Shiyu Zhou : FOCS 95, JCSS 58(2): 376-403 1999.
- Lecture 20 and Lecture 21 from Jin-Yi Cai's course
- More on Extractors (1): This project aims at exploring the overview of extractor constructions available and specifically exploring the Trevisan's extractor in some detail.
- More on Derandomization(1) There are plenty of extensions of the Nisan-Wigderson Hardness vs Randomness derandomization paradigm. Each of them is a direction on the frontier on their own. Here is a notable one among them : Derandomizing Arthur-Merlin games using hitting sets - Miltersen and Vinodchandran (FOCS 1999, CC 2005).
- Infeasibility of Instance Compression (Assigned to Mrinal): The aim here is to explore a connection between parameterized complexity and classical complexity theory. The central concepts in parameterized complexity is that of Kernelisation. A closely related notion is instance compression. A language L in NP is instance compressible if there is a polynomial-time computable function f and a set A such that for each instance x of L, f(x) is of size polynomial in the witness size of x, and f reduces L to A. One of the interesting results here is due to Fortnow and Santhanam which says SAT is incompressible unless NP is contained in CoNP/poly.
- Restricted Arithmetic Circuit Lower Bounds(1)
In this project we explore the known lower bounds in restricted arithmetic circuits. The aim is just to understand the techniques in the paper: Multilinear Formulas for Permanent and Determinant are of Super-Polynomial Size - Ran Raz (STOC 2004). - Elusive Functions(1): The aim is to understand the techniques and open problems of the paper: Elusive Functions and Lower Bounds for Arithmetic Circuits - Ran Raz (STOC 2008).
- Arithmetic Circuits - A Chasm at depth four (1 - Assigned
to Sajin Koroth): The aim is
to understand the depth reduction
technique in Arithmetic
Circuits - A
Chasm at depth four - Manindra Agarwal, V. Vinay
- Remote Point Problem and Boolean Circuit Lower bounds:
The aim is to understand the connections between Boolean circuit lower bounds and versions of
the combinatorial/algebraic problem called Remote Point Problem.
Circuit Lower Bounds, Help Functions and Remote point problem - V. Arvind and Srikanth
Srinivasan.
The paper also proves connections to arithemtic circuit lower bounds, but this can be skipped if only one person is taking up the reading.
Last updated on Fri May 13 21:08:49 IST 2011