Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > RAMSEY GRAPH:
Reports tagged with Ramsey Graph:
TR05-106 | 26th September 2005
Anup Rao

Extractors for a Constant Number of Polynomial Min-Entropy Independent Sources

Revisions: 1


We consider the problem of bit extraction from independent sources. We
construct an extractor that can extract from a constant number of
independent sources of length n, each of which have min-entropy
n^\gamma for an arbitrarily small constant \gamma > 0. Our
constructions are different from recent extractor constructions
more >>>


TR18-065 | 8th April 2018
Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma

Near-Optimal Strong Dispersers, Erasure List-Decodable Codes and Friends

Revisions: 1

A code \mathcal{C} is (1-\tau,L) erasure list-decodable if for every codeword w, after erasing any 1-\tau fraction of the symbols of w,
the remaining \tau-fraction of its symbols have at most L possible completions into codewords of \mathcal{C}.
Non-explicitly, there exist binary (1-\tau,L) erasure list-decodable codes having rate O(\tau) and ... more >>>


TR23-023 | 13th March 2023
Xin Li

Two Source Extractors for Asymptotically Optimal Entropy, and (Many) More

Revisions: 1

A long line of work in the past two decades or so established close connections between several different pseudorandom objects and applications, including seeded or seedless non-malleable extractors, two source extractors, (bipartite) Ramsey graphs, privacy amplification protocols with an active adversary, non-malleable codes and many more. These connections essentially show ... more >>>




ISSN 1433-8092 | Imprint