Randomized Algorithms (Spring 2010)/Problem Set 5: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>WikiSysop
Created page with '== Problem 1 == In class, we learn that with the presence of a membership oracle, we can sample near uniformly from any convex body <math>K</math> in <math>n</math> dimensions, a…'
 
imported>WikiSysop
Line 1: Line 1:
== Problem 1 ==
== Problem 1 (20 points)==
In class, we learn that with the presence of a membership oracle, we can sample near uniformly from any convex body <math>K</math> in <math>n</math> dimensions, and estimate the volume <math>K</math>. Then we make the following idealized assumptions: for any convex body <math>K</math>, we can
In class, we learn that with the presence of a membership oracle, we can sample near uniformly from any convex body <math>K</math> in <math>n</math> dimensions, and estimate the volume <math>K</math>. Then we make the following idealized assumptions: for any convex body <math>K</math>, we can
* sample uniformly from <math>K</math> in time polynomial of <math>n</math>;
* sample uniformly from <math>K</math> in time polynomial of <math>n</math>;

Revision as of 14:27, 31 May 2010

Problem 1 (20 points)

In class, we learn that with the presence of a membership oracle, we can sample near uniformly from any convex body [math]\displaystyle{ K }[/math] in [math]\displaystyle{ n }[/math] dimensions, and estimate the volume [math]\displaystyle{ K }[/math]. Then we make the following idealized assumptions: for any convex body [math]\displaystyle{ K }[/math], we can

  • sample uniformly from [math]\displaystyle{ K }[/math] in time polynomial of [math]\displaystyle{ n }[/math];
  • compute its volume [math]\displaystyle{ \mathrm{vol}(K) }[/math] precisely in time polynomial of [math]\displaystyle{ n }[/math].

(Note that in both assumptions, the errors are ignored.)

Now consider the following problem:

Suppose that we have [math]\displaystyle{ m }[/math] convex bodies [math]\displaystyle{ K_1,K_2,\ldots,K_m }[/math], in [math]\displaystyle{ n }[/math] dimensions, provided by [math]\displaystyle{ m }[/math] membership oracles [math]\displaystyle{ \mathcal{O}_1,\mathcal{O}_2,\ldots,\mathcal{O}_m }[/math], where for any [math]\displaystyle{ n }[/math]-dimensional point [math]\displaystyle{ x }[/math], and any [math]\displaystyle{ 1\le i\le m }[/math], [math]\displaystyle{ \mathcal{O}_i(x) }[/math] indicates whether [math]\displaystyle{ x\in K_i }[/math].

With the above ideal assumptions and inputs:

  1. Compute [math]\displaystyle{ \mathrm{vol}\left(\bigcap_{i=1}^mK_i\right) }[/math].
  2. Compute [math]\displaystyle{ \mathrm{vol}\left(\bigcup_{i=1}^mK_i\right) }[/math].

(Remark: for both questions, you should explicitly describe the algorithm, and give mathematically sound analysis. The only unspecified calls of subroutines should be the membership oracles [math]\displaystyle{ \mathcal{O}_1,\mathcal{O}_2,\ldots,\mathcal{O}_m }[/math], the uniform samples from convex [math]\displaystyle{ K }[/math], and [math]\displaystyle{ \mathrm{vol}(K) }[/math] for convex [math]\displaystyle{ K }[/math].)

Problem 2

Problem 3