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

Recent Submissions

  • Online algorithms and the k-server conjecture 

    Madry, Aleksander (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 ...
  • Algorithms for Circuits and Circuits for Algorithms 

    Williams, Ryan (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 ...
  • A Randomized Rounding Approach for Symmetric TSP 

    Singh, Mohit (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 ...
  • Subexponential lower bounds for randomized pivoting rules for the simplex algorithm 

    Hansen, Thomas Dueholm (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 ...
  • The Power and Weakness of Randomness (When You are Short on Time) 

    Wigderson, Avi (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 ...