loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)
Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization
Berkeley, California
October 21-October 24
ISBN: 0-7695-2720-5
Laszlo Lovasz, Microsoft Research
Santosh Vempala, Georgia Tech and MIT, USA
We prove that the hit-and-run random walk is rapidly mixing for an arbitrary logconcave distribution starting from any point in the support. This extends the work of [26], where this was shown for an important special case, and settles the main conjecture formulated there. From this result, we derive asymptotically faster algorithms in the general oracle model for sampling, rounding, integration and maximization of logconcave functions, improving or generalizing the main results of [24, 25, 1] and [16] respectively. The algorithms for integration and optimization both use sampling and are surprisingly similar.
Citation:
Laszlo Lovasz, Santosh Vempala, "Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization," focs, pp.57-68, 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.