# lower bounds

Published articles for lower bounds.

This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles.

## The Complexity of Communication

DevFeed: [The Complexity of Communication](<https://devfeed.tech/articles/the-complexity-of-communication-40369.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2014/11/10/the-complexity-of-communication/>)

Published: 2014-11-10T09:00:25Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Computer science](<https://devfeed.tech/topics/computer-science.md>), [Algorithms, Complexity](<https://devfeed.tech/topics/algorithms-complexity.md>), [Streaming](<https://devfeed.tech/topics/streaming.md>), [circuit](<https://devfeed.tech/topics/circuit.md>)

Tags: [communication](<https://devfeed.tech/tags/communication.md>), [communication-complexity](<https://devfeed.tech/tags/communication-complexity.md>), [computational-complexity](<https://devfeed.tech/tags/computational-complexity.md>), [fourier-analysis](<https://devfeed.tech/tags/fourier-analysis.md>), [information-theory](<https://devfeed.tech/tags/information-theory.md>), [log-rank-conjecture](<https://devfeed.tech/tags/log-rank-conjecture.md>), [lower-bounds](<https://devfeed.tech/tags/lower-bounds.md>), [matrices](<https://devfeed.tech/tags/matrices.md>), [streaming-algorithms](<https://devfeed.tech/tags/streaming-algorithms.md>), [theory](<https://devfeed.tech/tags/theory.md>)

### AI overview

This tutorial introduces communication complexity: how much information two parties must exchange to jointly compute a function of separate inputs. It presents the basic two-player model and explains the subject's use in proving lower bounds, including applications to circuit design and streaming algorithms.

### Source excerpt

satellite One of the most interesting questions posed in the last thirty years of computer science is to ask how much "information" must be communicated between two parties in order for them to jointly compute something. One can imagine these two parties living on distant planets, so that the cost of communicating any amount of information is very expensive, but each person has an integral component of the answer that the other does not.

## There are Infinitely Many Primes (Erdős)

DevFeed: [There are Infinitely Many Primes (Erdős)](<https://devfeed.tech/articles/there-are-infinitely-many-primes-erdos-40291.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2012/11/10/there-are-infinitely-many-primes-erdos/>)

Published: 2012-11-10T13:48:52Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [primes](<https://devfeed.tech/topics/primes.md>)

Tags: [limits](<https://devfeed.tech/tags/limits.md>), [lower-bounds](<https://devfeed.tech/tags/lower-bounds.md>), [number](<https://devfeed.tech/tags/number.md>), [primes](<https://devfeed.tech/tags/primes.md>), [product](<https://devfeed.tech/tags/product.md>), [square](<https://devfeed.tech/tags/square.md>)

### AI overview

A proof by Paul Erdős establishes that infinitely many primes exist by bounding the number of factorizations of integers as a square-free number times a square. This yields π(n) >= 1/2 log(n), which grows without bound.

### Source excerpt

Problem: Prove there are infinitely many primes Solution: Denote by $ \pi(n)$ the number of primes less than or equal to $ n$. We will give a lower bound on $ \pi(n)$ which increases without bound as $ n \to \infty$. Note that every number $ n$ can be factored as the product of a square free number $ r$ (a number which no square divides) and a square $ s^2$.