{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:38:16Z","timestamp":1787341096325,"version":"build-2736575974"},"reference-count":0,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>This issue of SICOMP contains nine specially selected papers from the Forty-first Annual ACM Symposium on the Theory of Computing, otherwise known as STOC 2009, held May 31 to June 2 in Bethesda, Maryland. The papers here were chosen to represent both the excellence and the broad range of the STOC program. The papers have been revised and extended by the authors, and subjected to the standard thorough reviewing process of SICOMP.<\/jats:p>\n                  <jats:p>The program committee consisted of Susanne Albers, Andris Ambainis, Nikhil Bansal, Paul Beame, Andrej Bogdanov, Ran Canetti, David Eppstein, Dmitry Gavinsky, Shafi Goldwasser, Nicole Immorlica, Anna Karlin, Jonathan Katz, Jonathan Kelner, Subhash Khot, Ravi Kumar, Leslie Ann Goldberg, Michael Mitzenmacher (Chair), Kamesh Munagala, Rasmus Pagh, Anup Rao, Rocco Servedio, Mikkel Thorup, Chris Umans, and Lisa Zhang. They accepted 77 papers out of 321 submissions.<\/jats:p>\n                  <jats:p>We briefly describe the papers that appear here.<\/jats:p>\n                  <jats:p>In \u201cBit-Probe Lower Bounds for Succinct Data Structures\u201d Emanuele Viola considers lower bounds for representing lists of values where one also wants to be able to probe the structure that maintains the values in order to for example determine the $i$th value in the list efficiently. In \u201cHomology Flows, Cohomology Cuts\u201d Jeff Erickson, Erin Chambers, and Amir Nayyeri provide an algorithm to compute maximum flows in surface-embedded graphs in near-linear time. In \u201cApproximating Edit Distance in Near-Linear Time\u201d Alexandr Andoni and Krzysztof Onak give the first sub-polynomial approximation of the edit distance that runs in near-linear time. In \u201cOnline and Stochastic Survivable Network Design\u201d Anupam Gupta, Ravishankar Krishnaswamy, and R. Ravi examine approximation algorithms for finding a subgraph of minimum cost that maintain given connectivity constraints, in a number of online and stochastic settings. In \u201cUniversally Utility-Maximizing Privacy Mechanisms\u201d Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan study differential privacy mechanisms, giving an approach that is simultaneously expected loss-minimizing in terms of utility for all users subject to a differential privacy constraint. In \u201c3-Query Locally Decodable Codes of Subexponential Length\u201d Klim Efremenko provides the first unconditional construction for 3-query locally decodable codes with subexponential codeword length. In \u201cTwice-Ramanujan Sparsifiers\u201d Joshua Batson, Daniel Spielman, and Nikhil Srivastava provide a deterministic, polynomial time algorithm for determining a spectral sparsifier of a graph---that is, a graph with a linear number of edges that approximates the graph in terms of its Laplacian matrix. In \u201cNew Direct-Product Testers and 2-Query PCPs\u201d Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson present several new results for probabilistically checkable proofs (PCPs), including new 3-query tests and 2-query tests leading to novel 2-query PCPs. In \u201cMax Cut and the Smallest Eigenvalue\u201d Luca Trevisan develops an elegant new approximation algorithm for Max Cut based on spectral partitioning methods, where the approximation ratio is 0.531 generally, but it also performs particularly well when the optimal solution cuts a large fraction of the edges.<\/jats:p>\n                  <jats:p>We thank the authors and the program committee for their hard work, and especially thank the reviewers for their work in evaluating and improving the submitted papers.<\/jats:p>","DOI":"10.1137\/120973305","type":"journal-article","created":{"date-parts":[[2012,12,18]],"date-time":"2012-12-18T13:36:29Z","timestamp":1355837789000},"page":"1591-1592","source":"Crossref","is-referenced-by-count":0,"title":["Special Section on the Forty-First Annual ACM Symposium on Theory of Computing (STOC 2009)"],"prefix":"10.1137","volume":"41","author":[{"given":"Nicole","family":"Immorlica","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jonathan","family":"Katz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Mitzenmacher","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rocco","family":"Servedio","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chris","family":"Umans","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,12,18]]},"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/120973305","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:05:31Z","timestamp":1787339131000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/120973305"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":0,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1137\/120973305"],"URL":"https:\/\/doi.org\/10.1137\/120973305","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}