Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR15-046 | 2nd April 2015
Talya Eden, Amit Levi, Dana Ron

Approximately Counting Triangles in Sublinear Time

Comments: 1

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

ISSN 1433-8092 | Imprint