דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Theory Seminar: Approximating the Number of $k$ Cliques in a Graph in Sublinear Time
event speaker icon
טליה עדן (אונ' תל-אביב)
event date icon
יום רביעי, 24.5.2017, 12:30
event location icon
טאוב 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$).
[בחזרה לאינדקס האירועים]