Complexity Atlas
HE
Exercise

Amplify One-Sided and Two-Sided Randomized Algorithms

Choose repetition and aggregation rules and derive explicit independent-error bounds.

Assignment sources

Noy 2025 high-quality exam preparation and community solutionsCommunity solutionפתרון מטלה 5 - סיבוכיות.pdfAssignment 5High-quality preparation and community solution — not official

These links mark a related idea or close version; only groups explicitly marked as exact repeats in the question map count as duplicates.

q-6559842decc0בהרצאה הוצג אלגוריתם הסתברותי לבעיית וידוא כפל מטריצות. נציע להלן שני אלגוריתמים נוספים לבעיה זו. עבור איזה ערך של m שני האלגוריתמים מבטיחים את אותו ח…0 exams · 1 assignments · lessons 12, 13, 14

Problem

An RP algorithm accepts yes-instances with probability at least 1/21/2 and never accepts no-instances. A BPP algorithm is correct with probability at least 2/32/3. For independent runs, design amplification to error at most δ\delta, prove the bounds, and explain why fresh randomness and the aggregation rule matter.

Prerequisites

Know the unit definitions and how resources are measured against encoded input length. Distinguish a conditional theorem, a reduction, and an algorithm.

Hint 1

For RP, accept if any run accepts.

Hint 2

For BPP, take an odd number of runs and majority vote.

Hint 3

Apply Hoeffding or Chernoff to independent correctness indicators.

Guided construction

Randomized error amplification

Step 1 of 6
Randomized error amplification across independent runsA strip of independent trials feeds an OR gate for RP and a majority gate for BPP, above a logarithmic plot comparing the RP error two to the minus k, the exact BPP majority error, the Hoeffding ceiling e to the minus k over eighteen, and a flat line for reusing the same random string.Independent runs (fixed illustration)RP · OR✗BPP · majority✓Error probability against the number of runs110⁻¹10⁻²10⁻³10⁻⁴10⁻⁵10⁻⁶10⁻⁷159131721k independent runserror probability (log scale)
✓ Run accepts a yes-instance · Run answers correctly✗ Run misses a yes-instance · Run answers wrongly
One run of eachRP: Pr[accept | yes] ≥ 1/2, Pr[accept | no] = 0BPP: Pr[correct] ≥ 2/3 on every inputEvery displayed outcome is a fixed illustration, so the picture never changes between readers.

Full solution

For RP, run the algorithm rr times with independent random bits and accept if any run accepts. A no-instance is still never accepted, so the one-sided guarantee is preserved. On a yes-instance all runs reject with probability at most (1/2)r(1/2)^r. Thus

r≥⌈log⁡2(1/δ)⌉r\ge\left\lceil\log_2(1/\delta)\right\rceil

suffices. More generally, success probability pp gives failure at most (1−p)r≤e−pr(1-p)^r\le e^{-pr}.

For BPP, take an odd rr and output the majority answer. Let XiX_i indicate that run ii is correct. Then the XiX_i are independent, lie in [0,1][0,1], and have EXi≥2/3\mathbb E X_i\ge2/3. Error means ∑iXi≤r/2\sum_iX_i\le r/2, a deviation of at least r/6r/6 below its mean. Hoeffding gives

Pr⁡[majority wrong]≤exp⁡ ⁣(−2r(1/6)2)=e−r/18.\Pr[\text{majority wrong}] \le \exp\!\left(-2r(1/6)^2\right)=e^{-r/18}.

Therefore any odd

r≥18ln⁡(1/δ)r\ge18\ln(1/\delta)

suffices. Sharper Chernoff constants are possible; the important asymptotic count is O(log⁡(1/δ))O(\log(1/\delta)).

The runtime multiplies by rr, plus negligible voting time. For inverse-polynomial error δ=n−c\delta=n^{-c}, only O(log⁡n)O(\log n) repetitions are needed, preserving polynomial time. For exponentially small error δ=2−nc\delta=2^{-n^c}, O(nc)O(n^c) repetitions still preserve polynomial time for fixed cc.

Fresh independent random bits justify multiplying RP failure probabilities and applying concentration for BPP. Reusing the same random seed can make all outcomes identical and provide no amplification. The aggregation rule also depends on error type: “accept if any” would destroy BPP soundness because many independent false accepts accumulate; majority controls both sides. Conversely majority works for RP but wastes its perfect soundness and gives a weaker analysis than the OR rule.

If individual success is only 1/21/2, majority cannot amplify without first creating a positive bias. The strict gap above one half is essential.

Checkpoints

Check both logical directions, halting of every relevant branch, and that output length and construction time are polynomial in the encoded input length.

Common mistakes

  • Multiplying probabilities without independence.
  • Using OR aggregation for a two-sided algorithm.
  • Claiming majority amplifies success exactly 1/21/2.

Sources and verification

  • Merged summary, pp. 89-94 and p. 96
  • Arora-Barak draft, sec. 7.1
  • Papadimitriou, ch. 11
  • Catalog mapping: data/exercises.json; statements and solutions are independently written; personal submissions are non-authoritative.

Provenance and confidence

The exercise is an original synthesis. Confidence reflects verification of the mathematical claim against the textbook sources listed above; course sources are used only where direct coverage is identified.

Open in the visualization gallery: Randomized error amplification