We bound the performance guarantees that follow from Turán-like bounds for unweighted and weighted independent sets in bounded-degree graphs. In particular, a randomized approach of Boppana forms a simple 1-round distributed algorithm, as well as a streaming and preemptive online algorithm. We show it gives a tight (Δ+1)/2-approximation in unweighted graphs of maximum degree Δ, which is best possible for 1-round distributed algorithms. For weighted graphs, it gives only a (Δ+1)-approximation, but a simple modification results in an asymptotic expected 0.529(Δ+1)-approximation.

Let k = k(n) be the largest integer such that there exists a k-wise uniform distribution over {0,1}^n that is supported on the set S_m := {x in {0,1}^n: sum_i x_i equiv 0 mod m}, where m is any integer. We show that Omega(n/m^2 log m) <= k <= 2n/m + 2. For k = O(n/m) we also show that any k-wise uniform distribution puts probability mass at most 1/m + 1/100 over S_m. For any fixed odd m there is k \ge (1 - Omega(1))n such that any k-wise uniform distribution lands in S_m with probability exponentially close to |S_m|/2^n; and this result is false for any even m.

This paper investigates the leader-election problem in the perfect-information model of distributed computing. It is shown that for every $\epsilon < \half$, there exist leader-election protocols for n processors that tolerate $\eps n$ faults.

The average sensitivity of a Boolean circuit is the expected number of input bits that, when flipped, change the output of the circuit, starting with a random input setting. We show that unbounded-fanin circuits of depth d and size s have average sensitivity O(log s)d−1. This bound is asymptotically tight.

A slightly random source (with bias$\epsilon $) is a sequence $\mathbf{x} = (\mathbf{x}_1 ,\mathbf{x}_2 , \ldots ,\mathbf{x}_n )$ of random bits such that the conditional probability that $\mathbf{x}_i = 1$, given the outcomes of the first $i - 1$ bits, is always between $\frac{1}{2} - \epsilon $ and $\frac{1}{2} + \epsilon $. Given a subset S of $\{ 0,1\} ^n $, define its $\epsilon $-biased probability to be the minimum of $\text{Pr}[ \mathbf{x} \in S ]$ over all slightly random sources $\mathbf{x}$ with bias $\epsilon $. It is shown that, for every fixed $\epsilon < \frac{1}{2}$ and almost every subset S of $\{ 0,1\} ^n $, the $\epsilon $-biased probability of S is bounded away from 0.

Article Free Access Share on The biased coin problem Authors: Ravi B. Boppana View Profile , Babu O. Narayanan View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 252–257https://doi.org/10.1145/167088.167164Published:01 June 1993Publication History 6citation529DownloadsMetricsTotal Citations6Total Downloads529Last 12 Months33Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We obtain tight bounds on the relative powers of the Priority and Common models of parallel random-access machines (PRAMs). Specifically we prove that:

Graph Bisection is the problem of partitioning the vertices of a graph into two equal-size pieces so as to minimize the number of edges between the two pieces. This paper presents an algorithm that will, for almost all graphs in a certain class, output the minimum-size bisection. Furthermore the algorithm will yield, for almost all such graphs, a proof that the bisection is optimal. The algorithm is based on computing eigenvalues and eigenvectors of matrices associated with the graph.

The amplification of probabilistic Boolean formulas refers to combining independent copies of such formulas to reduce the error probability. Les Valiant used the amplification method to produce monotone Boolean formulas of size O(n5.3) for the majority function of n variables. In this paper we show that the amount of amplification that Valiant obtained is optimal. In addition, using the amplification method we give an O(k4.3 n log n) upper bound for the size of monotone formulas computing the kth threshold function of n variables.

We prove an exponential lower bound for the majority function on constant depth monotone circuits, solving an open problem of A. Yao's.. In particular, we prove that computing majority on depth d monotone circuits requires expΩ(n1/(d-1)) size. Using this result we also get exponential lower bounds for other problems, such as connectivity and cliques.