Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Sauer-Shelah lemma:
TR10-003 | 6th January 2010
Venkatesan Guruswami, Johan HÃ¥stad, Swastik Kopparty

On the List-Decodability of Random Linear Codes

For every fixed finite field $\F_q$, $p \in (0,1-1/q)$ and $\varepsilon >
0$, we prove that with high probability a random subspace $C$ of
$\F_q^n$ of dimension $(1-H_q(p)-\varepsilon)n$ has the
property that every Hamming ball of radius $pn$ has at most
$O(1/\varepsilon)$ codewords.

This ... more >>>

TR20-153 | 6th October 2020
Robert Kleinberg, Daniel Mitropolsky, Christos Papadimitriou

Total Functions in the Polynomial Hierarchy

We identify several genres of search problems beyond NP for which existence of solutions is guaranteed. One class that seems especially rich in such problems is PEPP (for "polynomial empty pigeonhole principle"), which includes problems related to existence theorems proved through the union bound, such as finding a bit string ... more >>>

ISSN 1433-8092 | Imprint