Document

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

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.

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

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

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.

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} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail