CMU Theory Lunch: Kanat Tangwongsan, Regret Minimization and Parallel Algorithms for Approximately Solving Positive LPs/title>  <link rel="stylesheet" href="lunch-main.css"/> </head> <body> <div id="page"> <div id="page_contents">  <div id="header"> <div id="page_title">Theory Lunch</div> <div id="scs_logo"><img src="cmu-scs.gif" alt="School of Computer Science, Carnegie Mellon University" width="290px" border="0" /></div> </div> <div id="main_container">  <div id="sched_header"> Regret Minimization and Parallel Algorithms for Approximately Solving Positive LPs</div> <div id="abs_talk_speaker"> Kanat Tangwongsan </a> </div> <div id="abs_date">Feb 17, 2010</div>  <div id="abs">  <p>ABSTRACT:</p> <p> Regret minimization is a powerful framework for repeated matrix-game playing, with certain provable guarantees on the accrued utility in comparison to that of the best fixed strategy. The framework has found numerous applications, including the rediscovery of efficient *sequential* algorithms for approximately solving linear programs (LPs). Indeed, the connection between regret minimization and LP solving is well understood and has inspired the discovery of many new algorithms.</p> <p> How can we apply this understanding to devise a *parallel* algorithm for approximately solving LPs using the regret minimization framework? In this talk, I will present a brief introduction to regret minimization algorithms and show how to use them to obtain a parallel NC algorithm for approximately solving positive linear programs (PLPs), up to arbitrary accuracy. This algorithm can be viewed as a unification of earlier work on approximately solving PLPs, as seen through the regret minimization lens. Standard complexity theoretic assumptions rule out the possibility of such algorithms for linear programs in general. </p> <p> This is joint work with Guy Blelloch and Anupam Gupta. </p> </div>  </body>