tag:blogger.com,1999:blog-6555947.post4335369293918847701..comments2024-03-14T01:32:43.610-06:00Comments on The Geomblog: FOCS 08 list ?Suresh Venkatasubramanianhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-6555947.post-81397250021257130182008-06-23T21:02:00.000-06:002008-06-23T21:02:00.000-06:00List is live:FOCS 2008 Accepted PapersList is live:<BR/><BR/><A HREF="http://focs2008.org/accepted.html" REL="nofollow">FOCS 2008 Accepted Papers</A>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-24447169104349735162008-06-23T20:50:00.000-06:002008-06-23T20:50:00.000-06:00Title: beating the random ordering is hard: inappr...Title: beating the random ordering is hard: inapproximability of maximum acyclic subgraph<BR/>Authors: Venkatesan Guruswami, Rajsekar Manokaran, Prasad Raghavendra<BR/>URL: http://www.cs.princeton.edu/~rajsekar/papers/mas.pdf<BR/>URL: http://www.cs.washington.edu/homes/prasad/Files/mas.pdf<BR/><BR/>Title: broadcasting with side information<BR/>Authors: Noga Alon, Avinatan Hasidim, Eyal Lubetzky, Uri Stav, Amit Weinstein<BR/>URL: http://arxiv.org/abs/0806.3246<BR/>URL: http://www.cs.tau.ac.il/~uristav/data/broad.pdf<BR/>URL: http://www.math.tau.ac.il/~nogaa/PDFS/broad8.pdf<BR/>URL: http://arxiv.org/e-print/0806.3246<BR/><BR/>Title: constant-time approximation algorithms via local improvements<BR/>Authors: Huy Ngoc Nguyen (or Ngọc Huy Nguyễn?), Krzysztof Onak<BR/>URL: http://people<BR/>.csail.mit.edu/konak/papers/focs_2008-constant_time_approximation_algorithms_via_local_improvements.html<BR/><BR/>Title: (data) structures<BR/>Authors: Mihai Pătraşcu<BR/>URL: http://mit.edu/mip/www/papers/structures/paper.pdf<BR/><BR/>Title: dynamic connectivity: connecting to networks and geometry<BR/>Authors: Timothy Moon-Yew Chan, Mihai Pătraşcu, Liam Roditty<BR/>URL: http://mit.edu/mip/www/papers/subconn/subconn.pdf<BR/><BR/>Title: eigenvalue bounds, spectral partitioning, and metrical deformations via flows<BR/>Authors: James Russell Lee, Punya Shloka Biswal, Satish Balusu Rao<BR/>URL: http://math.technion.ac.il/~techm/20080622110020080622lee<BR/><BR/>Title: hardness of nearest neighbor under L-infinity<BR/>Authors: Alex Andoni, Dorian Croitoru, and Mihai Pătraşcu<BR/>URL: http://mit.edu/mip/www/papers/Linfty/paper.pdf<BR/><BR/>Title: inapproximability for metric embeddings into R^d<BR/>Authors: Jirí Matousek, Anastasios Sidiropoulos<BR/><BR/>Title: k-wise independent random graphs<BR/>Authors: Noga Alon, Asaf Nussboim<BR/>URL: http://www.wisdom.weizmann.ac.il/~asafn/PAPERS/K_WISE_GNP.pdf<BR/>URL: http://arxiv.org/abs/0804.1268<BR/><BR/>Title: learning geometric concepts via Gaussian surface area<BR/>Authors: Adam Richard Klivans, Ryan William O'Donnell, Rocco Anthony Servedio<BR/>URL: http://www.cs.cmu.edu/~odonnell/papers/perimeter.pdf<BR/><BR/>Title: rounding parallel repetitions of unique games<BR/>Authors: Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev, David Steurer<BR/><BR/>Title: sketching and streaming entropy via approximation theory<BR/>Authors: Nicholas James Alexander Harvey, Jelani Nelson, Krzysztof Onak<BR/>URL: http://arxiv.org/e-print/0804.4138<BR/>URL: http://mit.edu/minilek/www/papers/entropy.pdf<BR/>URL: http://people.csail.mit.edu/konak/papers/focs_2008-sketching_and_streaming_entropy_via_approximation_theory.html<BR/>URL: http://people.csail.mit.edu/nickh/Publications/StreamingEntropy/StreamingEntropy.pdf<BR/><BR/>[The title of the following accepted paper seems to be undetermined, so I list both:]<BR/>Title: spherical cubes and rounding in high dimensions<BR/>Title: cubical tilings with sphere-like surface area<BR/>Authors: Guy Kindler, Ryan William O'Donnell, Anup Rao, Avi Wigderson<BR/><BR/>Title: succincter<BR/>Authors: Mihai Pătraşcu<BR/>URL: http://mit.edu/mip/www/papers/succinct/succinct.pdf<BR/><BR/>Title: truthful approximation schemes for single-parameter agents<BR/>Authors: Peerapong Dhangwatnotai, Shahar Dobzinski, Shaddin Dughmi, Timothy Avelin Roughgarden<BR/><BR/>Title: on the value of multiple read/write streams for approximating frequency moments<BR/>Authors: Paul William Beame, Dang-Trinh Huynh-Ngoc (or Đăng-Trình Huỳnh Ngọc?)<BR/>URL: http://eccc.hpi-web.de/eccc-reports/2008/TR08-024<BR/><BR/>Other ten claimed submissions are unconfirmed as far.Anonymousnoreply@blogger.com