Very Large Cliques are Easy to Detect

Authors Alexander E. Andreev, Stasys Jukna



PDF
Thumbnail PDF

File

DagSemProc.06111.22.pdf
  • Filesize: 188 kB
  • 7 pages

Document Identifiers

Author Details

Alexander E. Andreev
Stasys Jukna

Cite AsGet 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.
Keywords
  • Clique function
  • monotone circuits
  • perfect hashing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail