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 ?
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: 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.
Title: beating the random ordering is hard: inapproximability of maximum acyclic subgraph
ReplyDeleteAuthors: 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.
List is live:
ReplyDeleteFOCS 2008 Accepted Papers