All reports by Author Amit Levi:

__
TR16-105
| 13th July 2016
__

Eric Blais, Clement Canonne, Talya Eden, Amit Levi, Dana Ron#### Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism

Revisions: 1

__
TR15-046
| 2nd April 2015
__

Talya Eden, Amit Levi, Dana Ron#### Approximately Counting Triangles in Sublinear Time

Comments: 1

Eric Blais, Clement Canonne, Talya Eden, Amit Levi, Dana Ron

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 >>>

Talya Eden, Amit Levi, Dana Ron

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 >>>