DROPS

Document

Very Large Cliques are Easy to Detect

Authors: Alexander E. Andreev and Stasys Jukna

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{andreev_et_al:DagSemProc.06111.22,
  author =	{Andreev, Alexander E. and Jukna, Stasys},
  title =	{{Very Large Cliques are Easy to Detect}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.22},
  URN =		{urn:nbn:de:0030-drops-6092},
  doi =		{10.4230/DagSemProc.06111.22},
  annote =	{Keywords: Clique function, monotone circuits, perfect hashing}
}

Document

DOI: 10.4230/DagSemProc.06111.19

The optimal sequence compression

Authors: Alexander E. Andreev

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

Abstract

This paper presents the optimal compression for sequences with undefined values. Let we have $(N-m)$ undefined and $m$ defined positions in the boolean sequence $vv V$ of length $N$. The sequence code length can't be less then $m$ in general case, otherwise at least two sequences will have the same code. We present the coding algorithm which generates codes of almost $m$ length, i.e. almost equal to the lower bound. The paper presents the decoding circuit too. The circuit has low complexity which depends from the inverse density of defined values $D(vv V) = frac{N}{m}$. The decoding circuit includes RAM and random logic. It performs sequential decoding. The total RAM size is proportional to the $$logleft(D(vv V) ight) ,$$ the number of random logic cells is proportional to $$log logleft(D(vv V) ight) * left(log log logleft(D(vv V) ight) ight)^2 .$$ So the decoding circuit will be small enough even for the very low density sequences. The decoder complexity doesn't depend of the sequence length at all.

Cite as

Alexander E. Andreev. The optimal sequence compression. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{andreev:DagSemProc.06111.19,
  author =	{Andreev, Alexander E.},
  title =	{{The optimal sequence compression}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.19},
  URN =		{urn:nbn:de:0030-drops-6025},
  doi =		{10.4230/DagSemProc.06111.19},
  annote =	{Keywords: Compression, partial boolean function}
}

Search Results

Documents authored by Andreev, Alexander E.

Very Large Cliques are Easy to Detect

Abstract

Cite as

The optimal sequence compression

Abstract

Cite as

Thanks for your feedback!

Could not send message