✦ LIBER ✦

A probabilistic lower bound for checking disjointness of sets

✍ Scribed by Udi Manber

Book ID: 113162740
Publisher: Elsevier Science
Year: 1984
Tongue: English
Weight: 283 KB
Volume: 19
Category: Article
ISSN: 0020-0190
DOI: 10.1016/0020-0190(84)90129-7

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A lower bound for probabilistic distribu

A lower bound for probabilistic distributed algorithms

✍ Jan K Pachl 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 766 KB

A natural lower bound for the size of no

A natural lower bound for the size of nodal sets

✍ Hezari, Hamid; Sogge, Christopher 📂 Article 📅 2012 🏛 Mathematical Sciences Publishers 🌐 English ⚖ 960 KB

A Lower Bound on Probabilistic Algorithm

A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring

✍ Naor, Moni 📂 Article 📅 1991 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 526 KB

Lower Bounds for Nodal Sets of Eigenfunc

Lower Bounds for Nodal Sets of Eigenfunctions

✍ Tobias H. Colding; William P. Minicozzi 📂 Article 📅 2011 🏛 Springer 🌐 English ⚖ 159 KB

DP lower bounds for equivalence-checking

DP lower bounds for equivalence-checking and model-checking of one-counter automata

✍ Petr Jančar; Antonı́n Kučera; Faron Moller; Zdeněk Sawa 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 304 KB

A Probabilistic lower bound on the indep

A Probabilistic lower bound on the independence number of graphs

✍ Stanley M. Selkow 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 124 KB

Caro (1979) and Wei (1981) established a bound on the size of an independent set of a graph as a function of its degrees. In case the degrees of each vertex's neighbors are also known, we establish a lower bound which is tighter for most graphs.