✦ LIBER ✦

A Lower Bound for Primality

✍ Scribed by Eric Allender; Michael Saks; Igor Shparlinski

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 130 KB
Volume: 62
Category: Article
ISSN: 0022-0000
DOI: 10.1006/jcss.2000.1725

No coin nor oath required. For personal study only.

✦ Synopsis

Recent work by Bernasconi, Damm, and Shparlinski showed that the set of square-free numbers is not in AC 0 and raised as an open question whether similar (or stronger) lower bounds could be proved for the set of prime numbers. We show that the Boolean majority function is AC 0 -Turing reducible to the set of prime numbers (represented in binary). From known lower bounds on Maj (due to Razborov and Smolensky) we conclude that primality cannot be tested in AC 0 [ p] for any prime p. Similar results are obtained for the set of square-free numbers and for the problem of computing the greatest common divisor of two numbers.

📜 SIMILAR VOLUMES

Lower bounds for lower Ramsey numbers

✍ Ralph Faudree; Ronald J. Gould; Michael S. Jacobson; Linda Lesniak 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 310 KB 👁 1 views

## Abstract For any graph __G__, let __i__(__G__) and μ;(__G__) denote the smallest number of vertices in a maximal independent set and maximal clique, respectively. For positive integers __m__ and __n__, the lower Ramsey number __s__(__m, n__) is the largest integer __p__ so that every graph of or

A lower bound for level spacings

✍ Elliott H Lieb; Walter E Thirring 📂 Article 📅 1977 🏛 Elsevier Science 🌐 English ⚖ 352 KB

We consider a single particle in a negative potential V: H = --d + V(x). A lower bound is found for the quantity +I -EW, where cm is the ground-state energy of H in all space and where EA is the ground-state energy of H in a bounded domain A with Dirichlet ($ = 0) boundary conditions. Our estimate f

Lower Bounds for Shellsort

✍ C.Greg Plaxton; Torsten Suel 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 226 KB

We show lower bounds on the worst-case complexity of Shellsort. In particular, Ž Ž 2 . Ž . 2 . we give a fairly simple proof of an ⍀ n lg n r lg lg n lower bound for the size of Shellsort sorting networks for arbitrary increment sequences. We also show an identical lower bound for the running time o

A lower bound for partial list colorings

✍ Chappell, Glenn G. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 188 KB 👁 2 views

Let G be an n-vertex graph with list-chromatic number χ . Suppose that each vertex of G is assigned a list of t colors. Albertson, Grossman, and Haas [1] conjecture that at least t n /χ vertices can be colored from these lists. We prove a lower bound for the number of colorable vertices. As a coroll

A lower bound for groupies in graphs

✍ Mackey, John 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 145 KB 👁 2 views

A non-isolated vertex of a graph G is called a groupie if the average degree of the vertices connected to it is larger than or equal to the average degree of the vertices in G. An isolated vertex is a groupie only if all vertices of G are isolated. While it is well known that every graph must contai

A lower bound for r(5, 5)

✍ Geoffrey Exoo 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 76 KB