The function f\colon \{-1,1\}^n \to \{-1,1\} is a k-junta if it depends on at most k of its variables. We consider the problem of tolerant testing of k-juntas, where the testing algorithm must accept any function that is \epsilon-close to some k-junta and reject any function that is \epsilon'-far from ... more >>>

We consider the problem of estimating the number of triangles in a graph. This problem has been extensively studied in two models: Exact counting algorithms, which require reading the entire graph, and streaming algorithms, where the edges are given in a stream and the memory is limited. In this work ... more >>>