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.
Update: that was quick! here it is.
Subscribe to:
Post Comments (Atom)
2 comments:
Title: beating the random ordering is hard: inapproximability of maximum acyclic subgraph
Reply DeleteAuthors: 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:
Reply DeleteFOCS 2008 Accepted Papers