archive-edu.com » EDU » C » COLUMBIA.EDU Total: 442 Choose link from "Titles, links and description words view": Or switch to
"Titles and links view". |

- COMS 6998 home page

Relevant readings A nice concise account of the sortedness testing algorithm can be found in Section 7 of Fischer s survey on property testing which is a good overview of property testing in general The sortedness testing algorithm is originally from this paper of Ergun Kannan Kumar Rubinfeld and Viswanathan Boolean Functions Warmup Learning parities and juntas Basics of Fourier analysis over the Boolean cube Relevant readings Sections 1 3 of O Donnell s nice overview of Fourier analysis on the hypercube are a good source for basic material of Fourier analysis that we ll need as is section 2 of this survey by Kobler and Lindner on Fourier analysis and learning Fourier analysis and learning Finding large Fourier coefficients using membership queries Learning decision trees sparse polynomials monotone functions and constant depth circuits Relevant readings Section 3 1 of the Kobler Lindner survey for the low degree algorithm and application to constant depth circuits Section 3 2 for the KM algorithm for finding large Fourier coefficients and applications to learning decision trees and sparse polynomials Section 4 for monotone functions The KL survey also has pointers to the original papers on these topics Learning intersections of halfspaces and more using ROBPs Relevant readings See here for the original Gopalan Klivans Meka paper Testing Boolean functions the basics Testing linearity Relevant readings These two surveys of Dana Ron provide an extensive introduction to property testing of Boolean functions and more The Fourier based linearity test we present is from this paper of Bellare Coppersmith Hastad Kiwi and Sudan Testing monotone functions upper and lower bounds Relevant readings The monotonicity testing algorithm we presented is from this paper of Goldreich Goldwasser Lehman Ron and Samorodnitsky The lower bound for one sided testing algorithms is from this paper of Fischer Lehman Newman Raskhodnikova Rubinfeld and Samorodnitsky The lower bound for two sided testing algorithms is from a forthcoming paper of Chen Servedio and Tan Testing juntas upper and lower bounds Other testing results Relevant readings The junta testing algorithm we presented is from this paper of Blais The lower bound for testing juntas is from this paper of Chockler and Gutfreund Graphs Testing dense graphs the basics Testing bipartiteness Testing triangle freeness Regularity and Szemeredi s regularity lemma Testing sparse graphs the basics Testing connectivity Distributions Learning distributions the basics Learning general distributions Hypothesis testing for distribution learning Learning monotone distributions Testing distributions the basics Testing uniformity upper and lower bounds Testing equivalence to known and unknown distributions Testing monotone distributions Grading and Requirements The requirements of the course are as follows Class Participation Students are expected to come to lecture and are encouraged to participate Scribing lectures For each lecture there will be one or more assigned scribes Your duties as a scribe are to take careful notes which will be made available on the class web page Your notes should be a clear detailed and readable exposition of the material covered in that lecture You are encouraged to use outside

Original URL path: http://www.cs.columbia.edu/~rocco/Teaching/S14/ (2016-02-17)

Open archived version from archive - Privacy and Online Social Networks

to convince me and I d be happy to have you register The course is not about the role of government legal or policy issues Students will be expected to read papers write code and present You are free to code in any language on any OS etc Please note that I will not be able to help you with any aspects of coding No specific prerequisites are needed For

Original URL path: https://www.cs.columbia.edu/~bala/s14/ (2016-02-17)

Open archived version from archive