COMS 6998 Projects: Spring 2014
Project Presentation Schedule
All project presentations will take place in CSB 477.
Tues May 13:
- 10:00 Lucas Kowalczyk (functions)
- 10:30 Richard Stark (graphs)
- 11:00 Ting-Chu Lin / Hyungtae Kim (distributions)
- 11:30 Hyungtae Kim / Ting-Chu Lin (distributions)
- 12:00 Psallidas Fotis (functions)
Wed May 14:
- 3:00 Anirban Gangopadhyay (distributions)
- 3:30 Enze Li / Bach Nguyen (graphs)
- 4:00 Bach Nguyen / Enze Li (graphs)
- 4:30 Timothy Sun (graphs)
- 5:00 Yiren Lu (graphs)
Thurs May 15:
- 10:00 Dimitris Paidarakis (functions)
- 10:30 Yichi Zhang (functions)
- 11:00 Jinyu Xie (functions)
- 11:30 Keith Nichols (graphs)
- 12:00 Yang Liu (distributions)
Overview of Project Expectations and Requirements
There are two main goals for a project in this class:
(1) You should learn a significant amount about your chosen
project topic. This will involve closely and carefully reading
literature on your specific project topic
(likely to be a paper or two).
You'll demonstrate this aspect of your project in the "Background"
section(s) of your project report, which should be a clear synthesis
and exposition in your own words of what you learned.
You can format this according to the scribe notes of the class --
basically, for this portion of the project you should turn in
a polished and high-quality set of scribe notes, as if you had been
the scribe for a lecture on your chosen topic.
(2) You should gain research experience in this area; i.e. make a
serious effort to contribute to the state of knowledge on your project
topic by (i) identifying an interesting open question or direction for
future research related to your project topic; (ii) coming up with an
approach to make progress; and (iii) working to carry out your approach.
You'll demonstrate this aspect of your project by
explaining in detail what you did for (i), (ii) and (iii) in the rest of your
The timetable for projects will be as follows:
For the first phase of your project (the initial proposal) you
should not only select a general topic, but come up with
a clear idea of the sources you will use and the specific material
within those sources that you will cover.
Wed March 5: Turn in a brief (1-2 paragraph) project proposal to
me by email, describing your chosen topic, the sources you will use,
and the portions of those sources that you will cover.
Fri May 9, 11:59pm: Email your final project report to the course
account, coms6998learntests14 at gmail dot com. You should send two separate
files, one for the scribe note portion and one for the original
research component as described above. Copies of the
scribe notes portion of each student's project will be made available to the
Tues May 13, Wed May 14, Thurs May 15:
Project presentations (see above).
The end products of your project will be:
(A) An in-class presentation. You should expect to
give a 15-30 minute presentation on what you did. This is not much time
so good preparation for your presentation is a must. The scribe
note portion of your project should cover much more material, and in more
detail, than you will be able to get through in your presentation.
(B) A project report that you'll turn in via email to Rocco. As described
above this will consist of a scribe note component and an original
research component. This will be the
major component of your course grade and should reflect your best effort.
You may work alone or in pairs on the project. Expectations for
projects will be calibrated according to group size.
Possible Project Topics
Below are some potential project topics with associated references to the
literature (more will be added soon).
You are encouraged to make up your own project topic,
but check with me very early on to make sure your project
topic is OK -- i.e. that it is sufficiently relevant
to the course topic, and that we're not going to cover it in
Learning Boolean functions:
Agnostic learning under the uniform and other distributions.
Relevant papers: Gopalan/Kalai/Klivans 2008, Kalai/Klivans/Mansour/Servedio
2008, Kane/Klivans/Meka 2013.
Agnostic boosting: Kalai/Mansour/Verbin 2008
(with application to agnostically learning parities); Kalai 2009; Feldman 2009
"Distribution-specific agnostic boosting".
Statistical Query learning. Original model: Kearns 1993.
SQ dimension: Blum/Furst/Jackson/Kearns/Mansour 1994.
``Strong SQ dimension'': Simon 2007, Feldman 2009.
Learning DNF using membership queries: Jackson 1997. This algorithm
crucially relies on boosting;
see also Jackson/Klivans/Servedio 2002 for another application combining
boosting with Fourier-based learning. See also the Feldman 2009
"Distribution-specific agnostic boosting" paper for a different
boosting-based approach to these results.
Testing Boolean functions:
Testing halfspaces: Matulef/O'Donnell/Rubinfeld/Servedio 2009.
Testing for concise representations: Matulef et al. 2007
and Chakraborty et al 2010.
Distribution-independent testing of Boolean functions:
Halevy/Kushilevitz 2003, 2005, 2007; Glasner/Servedio 2009; Dolev/Ron 2011.
Testing Graph Properties:
Testing isomorphism of graphs: Fischer/Matsliah 2006.
Characterizing constant-query testable graph properties:
- Learning continuous distributions (such as mixtures of Gaussians and
others). Relevant papers: Simha/Belkin 2010,
Kalai/Moitra/Valiant 2010, Moitra/Valiant 2011, and references therein.
Learning the distribution of satisfying assignments of Boolean functions:
Other aspects of sublinear-time algorithms:
- Optimal query complexity for testing closeness of distributions:
- Tolerant testing / distance estimation for distributions:
Valiant/Valiant ``The power of linear estimators'' 2011
- Sublinear time approximation algorithms for optimization problems:
see Section 6 of
and the many references therein.
- Interactive proofs of proximity: Rothblum/Vadhan/Wigderson 2013.