Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Ramsey Theorem:
TR11-162 | 7th December 2011
Pavel Pudlak

A lower bound on the size of resolution proofs of the Ramsey theorem

We prove an exponential lower bound on the lengths of resolution proofs of propositions expressing the finite Ramsey theorem for pairs.

more >>>

TR17-015 | 4th February 2017
Ilan Komargodski, Moni Naor, Eylon Yogev

White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing

Revisions: 1

Ramsey theory assures us that in any graph there is a clique or independent set of a certain size, roughly logarithmic in the graph size. But how difficult is it to find the clique or independent set? If the graph is given explicitly, then it is possible to do so ... more >>>

ISSN 1433-8092 | Imprint