DagSemProc.06111.22.pdf
- Filesize: 188 kB
- 7 pages
Document
Very Large Cliques are Easy to Detect
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 6111
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2006-11-20
Cite As Get BibTex
Alexander E. Andreev and Stasys Jukna. Very Large Cliques are Easy to Detect. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
https://doi.org/10.4230/DagSemProc.06111.22
Abstract
It is known that, for every constant $kgeq 3$, the presence of a $k$-clique (a complete subgraph on $k$ vertices) in an $n$-vertex graph cannot be detected by a monotone boolean circuit using fewer than $Omega((n/log n)^k)$ gates. We show that, for every constant $k$, the presence of an $(n-k)$-clique in an $n$-vertex graph can be detected by a monotone circuit using only $O(n^2log n)$ gates. Moreover, if we allow unbounded fanin, then $O(log n)$ gates are enough.
Subject Classification
Keywords
- Clique function
- monotone circuits
- perfect hashing
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads