Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Approximating the Number of $k$ Cliques in a Graph in Sublinear Time
event speaker icon
Talya Eden (Tel-Aviv University)
event date icon
Wednesday, 24.05.2017, 12:30
event location icon
Taub 201
We present a sublinear-time algorithm for approximating the number of $k$-cliques in an input graph.

We assume the standard general graphs access model via (1) degree queries, (2) neighbor queries and (3) pair queries.

Consider a graph with $n$ vertices, $m$ edges, and $k$-cliques. We design an algorithm that outputs a $(1+\eps)$-approximation (with high probability) for $k$ with expected query complexity and running time $O\left(\frac{n}{\clk^{1/k}}+\frac{m^{k/2}}{\clk} \right)\poly(\log n, 1/\eps,k)$.

Furthermore, we prove a lower bound showing that our algorithm is essentially optimal (up to the dependence on $\log n$, $1/\eps$ and $k$).