Monday, June 23, 2008

FOCS 08 list ?

The FOCS 2008 page has a link for accepted papers, but it's empty for now. We know at least 4 of the papers that got in, but does anyone know of a list ?

Update: that was quick! here it is.

2 comments:

  1. Title: beating the random ordering is hard: inapproximability of maximum acyclic subgraph
    Authors: Venkatesan Guruswami, Rajsekar Manokaran, Prasad Raghavendra
    URL: http://www.cs.princeton.edu/~rajsekar/papers/mas.pdf
    URL: http://www.cs.washington.edu/homes/prasad/Files/mas.pdf

    Title: broadcasting with side information
    Authors: Noga Alon, Avinatan Hasidim, Eyal Lubetzky, Uri Stav, Amit Weinstein
    URL: http://arxiv.org/abs/0806.3246
    URL: http://www.cs.tau.ac.il/~uristav/data/broad.pdf
    URL: http://www.math.tau.ac.il/~nogaa/PDFS/broad8.pdf
    URL: http://arxiv.org/e-print/0806.3246

    Title: constant-time approximation algorithms via local improvements
    Authors: Huy Ngoc Nguyen (or Ngọc Huy Nguyễn?), Krzysztof Onak
    URL: http://people
    .csail.mit.edu/konak/papers/focs_2008-constant_time_approximation_algorithms_via_local_improvements.html

    Title: (data) structures
    Authors: Mihai Pătraşcu
    URL: http://mit.edu/mip/www/papers/structures/paper.pdf

    Title: dynamic connectivity: connecting to networks and geometry
    Authors: Timothy Moon-Yew Chan, Mihai Pătraşcu, Liam Roditty
    URL: http://mit.edu/mip/www/papers/subconn/subconn.pdf

    Title: eigenvalue bounds, spectral partitioning, and metrical deformations via flows
    Authors: James Russell Lee, Punya Shloka Biswal, Satish Balusu Rao
    URL: http://math.technion.ac.il/~techm/20080622110020080622lee

    Title: hardness of nearest neighbor under L-infinity
    Authors: Alex Andoni, Dorian Croitoru, and Mihai Pătraşcu
    URL: http://mit.edu/mip/www/papers/Linfty/paper.pdf

    Title: inapproximability for metric embeddings into R^d
    Authors: Jirí Matousek, Anastasios Sidiropoulos

    Title: k-wise independent random graphs
    Authors: Noga Alon, Asaf Nussboim
    URL: http://www.wisdom.weizmann.ac.il/~asafn/PAPERS/K_WISE_GNP.pdf
    URL: http://arxiv.org/abs/0804.1268

    Title: learning geometric concepts via Gaussian surface area
    Authors: Adam Richard Klivans, Ryan William O'Donnell, Rocco Anthony Servedio
    URL: http://www.cs.cmu.edu/~odonnell/papers/perimeter.pdf

    Title: rounding parallel repetitions of unique games
    Authors: Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev, David Steurer

    Title: sketching and streaming entropy via approximation theory
    Authors: Nicholas James Alexander Harvey, Jelani Nelson, Krzysztof Onak
    URL: http://arxiv.org/e-print/0804.4138
    URL: http://mit.edu/minilek/www/papers/entropy.pdf
    URL: http://people.csail.mit.edu/konak/papers/focs_2008-sketching_and_streaming_entropy_via_approximation_theory.html
    URL: http://people.csail.mit.edu/nickh/Publications/StreamingEntropy/StreamingEntropy.pdf

    [The title of the following accepted paper seems to be undetermined, so I list both:]
    Title: spherical cubes and rounding in high dimensions
    Title: cubical tilings with sphere-like surface area
    Authors: Guy Kindler, Ryan William O'Donnell, Anup Rao, Avi Wigderson

    Title: succincter
    Authors: Mihai Pătraşcu
    URL: http://mit.edu/mip/www/papers/succinct/succinct.pdf

    Title: truthful approximation schemes for single-parameter agents
    Authors: Peerapong Dhangwatnotai, Shahar Dobzinski, Shaddin Dughmi, Timothy Avelin Roughgarden

    Title: on the value of multiple read/write streams for approximating frequency moments
    Authors: Paul William Beame, Dang-Trinh Huynh-Ngoc (or Đăng-Trình Huỳnh Ngọc?)
    URL: http://eccc.hpi-web.de/eccc-reports/2008/TR08-024

    Other ten claimed submissions are unconfirmed as far.

    ReplyDelete

Disqus for The Geomblog