List of suggested papers

Back to homepage 

If there is any paper you want to hear or talk about, please send a suggestion to danupon at gmail dot com.

Some ideas

Papers from SODA'08

  • Comparison-Based, Time-Space Lower Bounds for Selection
    Timothy M. Chan.
  • An almost O(log k)-approximation for k-connected subgraphs
    Zeev Nutov.
  • Finding repeats in a data-stream
    Parikshit Gopalan and Jaikumar Radhakrishnan.
  • The Geometry of Binary Search Trees
    Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane and Mihai Patrascu.

Papers from STOC'08

  • Elusive Functions and Lower Bounds for Arithmetic Circuits
    Ran Raz
  • An $O(\log^2 k)$-approximation algorithm for the $k$-vertex connected subgraph problem
    Jittat Fakcharoenphol and Bundit Laekhanukit
  • Algebrization: A New Barrier in Complexity Theory
    Scott Aaronson and Avi Wigderson
  • Network Design for Vertex Connectivity
    Tanmoy Chakraborty and Julia Chuzhoy and Sanjeev Khanna

Papers from FOCS'08

  • Set Covering with Our Eyes Closed
    Fabrizio Grandoni, Anupam Gupta, Stefano Leonardi, Pauli Miettinen, Piotr Sankowski and Mohit Singh.
  • Arithmetic Circuits: A Chasm at Depth Four
    Manindra Agrawal and V Vinay.
  • On the Hardness of Being Truthful
    Christos Papadimitriou, Michael Schapira and Yaron Singer.