ARC Theory Day
Georgia Tech's Algorithms, Randomness and Complexity Center presents:
ARC Theory Day
|Thursday||November 10, 2011||Lectures by Avi Wigderson|
|Friday||November 11, 2011||9:20 AM||Welcome by Zvi Galil|
|9:30 AM||Thomas Dueholm Hansen - Subexponential Lower Bounds For Randomized Pivoting Rules For The Simplex Algorithm|
|10:45 AM||Aleksander Madry - Online Algorithms and The K-server Conjecture|
|1:30 PM||Mohit Singh - A Randomized Rounding Approach for Symmetric TSP|
|2:45 PM||Ryan Williams - Algorithms for Circuits and Circuits for Algorithms|
All materials in SMARTech are protected under U.S. Copyright Law and all rights are reserved. Such materials may be used, quoted or reproduced for educational purposes only with prior permission, provided proper attribution is given. Any redistribution, reproduction or use of the materials, in whole or in part, is prohibited without prior permission of the author.
(Georgia Institute of Technology, 2011-11-11)Traditionally, in the problems considered in optimization, one needs to produce the solution only after the whole input is made available. However, in many real-world scenarios the input is revealed gradually, and one needs ...
(Georgia Institute of Technology, 2011-11-11)We show a (3/2-epsilon)-approximation algorithm for the graphical traveling salesman problem where the goal is to find a shortest tour in an unweighted graph G. This is a special case of the metric traveling salesman problem ...
(Georgia Institute of Technology, 2011-11-11)Connections have been recently developed between the existence of non-trivial circuitanalysis algorithms and proofs of circuit size lower bounds. Algorithms that can check whether a given circuit from some class satisfies ...
(Georgia Institute of Technology, 2011-11-11)The simplex algorithm is among the most widely used algorithms for solving linear programs in practice. Most deterministic pivoting rules are known, however, to need an exponential number of steps to solve some linear ...
(Georgia Institute of Technology, 2011-11-10)Man has grappled with the meaning and utility of randomness for centuries. Research in the Theory of Computation in the last thirty years has enriched this study considerably. I will describe two main aspects of this ...