FOCS 2012
53rd Annual IEEE Symposium on
Foundations of Computer Science

October 20-23, 2012
Hyatt Regency, New Brunswick, New Jersey


FOCS 2012 will have a poster session, which can be thought of as an extended hallway discussion with a visual aid. The poster session will be held during the conference, in a special Monday night session, accompanied by refreshments. We welcome posters on research in any aspect of theoretical computer science.  We hope that the poster session is particularly useful for:

  • Researchers with papers in other conferences that would be of interest to the FOCS community.
  • FOCS 2012 authors who want to have a visual aid for extended/related discussions of their work.
  • Students who wish to discuss their work in a broader context (for example, by presenting an overview of a line of research)

  • Anna Blasiak, Cornell University (Joint work with Robert Kleinberg, Cornell University, and Eyal Lubetzky, Microsoft Research)
    Broadcasting with Side Information: Bounding and Approximating the Broadcast Rate

  • Yang Cai, MIT (Joint work with Gagan Aggarwal, Google, Aranyak Mehta, Google, and
    George Pierrakos, University of California, Berkeley)
    Biobjective Online Bipartite Matching

  • Kashyap Dixit, Pennsylvania State University
    Testing Lipschitz Property over Distributions and its Applications to Statistical Data Privacy

  • Andrew Dobson, Rutgers University (Joint work with and Kostas Bekris, Rutgers University)
    Approximate Distance Oracles in Continuous Configuration Spaces: Sparse Roadmap Spanners

  • Vasilis Gkatzelis, Courant Institute, NYU (Joint work with Richard Cole, Courant Institute, NYU and Gagan Goel, Google NY)
    Truthfulness, Proportional Fairness, and Efficiency

  • Nima Haghpanah, Northwestern University (Joint work with Saeed Alaei, University of Maryland, Hu Fu, Cornell University,
    Jason Hartline, Northwestern University, and Azarakhsh Malekian, MIT)
    Bayesian Optimal Auctions via Multi- to Single-agent Reduction

  • Madhav Jha, Pennsylvania State University
    Sublinear Algorithms in Data Privacy

  • Marco Molinaro, Carnegie Mellon University (Joint work with David P. Woodruff, MIT, and
    Grigory Yaroslavtsev, Pennsylvania State University)
    Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketchingy

  • Aleksandar Nikolov, Rutgers University (Joint work with Alexandr Andoni, Microsoft Research,
    Krzysztof Onak, Carnegie Mellon University, and Grigory Yaroslavtsev, Pennsylvania State University)
    Geometric Algorithms in the Map-Reduce Framework

  • Swapnoneel Roy, University at Buffalo, SUNY (Joint work with Atri Rudra, University at Buffalo, SUNY,
    and Akshat Verma, IBM Research, India)
    An Energy Complexity Model for Algorithms

  • Venu Satuluri, Ohio State University
    Bayesian Locality Sensitive Hashing for Fast Similarity Search

  • Adam Smith, Pennsylvania State University
    Analyzing Graphs with Node-Level Differential Privacy

  • Grigory Yaroslavtsev, Pennsylvania State University (Joint work with Sofya Raskhodnikova, Pennsylvania State University,
    and Rocco Servedio, Columbia University)
    Attribute-efficient learning and testing of k-DNF and sub modular functions

  • Grigory Yaroslavtsev, Pennsylvania State University (Joint work with Howard Karloff, AT&T Labs,
    and Anthony Wirth, University of Melbourne)
    Correlation clustering with overlaps

Poster presenters: Poster boards and push pins will be provided. Posters should be at most 40" high and at most 30" wide.