{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:28:51Z","timestamp":1787340531386,"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":[[2013,1]]},"abstract":"<jats:p>This section of SIAM Journal on Computing contains extended versions of selected papers from the 50th Annual Symposium on Foundations of Computer Science, sponsored by the IEEE Computer Society Technical Committee on Mathematical Foundations of Computing. The conference was held in Atlanta, Georgia, October 24--27, 2009, at the Renaissance Atlanta Hotel Downtown.<\/jats:p>\n                  <jats:p>The program committee consisted of Sanjeev Arora, Maria Florina Balcan, Boaz Barak, Mark Braverman, Amit Chakrabarti, Ken Clarkson, Alon Efrat, Martin F\u00fcrer, Anna Gilbert, Phil Klein, Ming Li, Mihai P\u0103tra\u015fcu, Dana Ron, Tim Roughgarden, Daniel Spielman, Mario Szegedy, Kunal Talwar, Eli Upfal, Umesh Vazirani, Vijay Vazirani, and Berthold V\u00f6cking. They accepted 75 papers from 249 submissions.<\/jats:p>\n                  <jats:p>We briefly describe the papers that appear here. In \u201cOn the Power of Randomization in Algorithmic Mechanism Design,\u201d Shahar Dobzinski and Shaddin Dughmi analyze multi-unit auctions to show that truthfulness in expectation is more powerful than universal truthfulness. In \u201cExtensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers,\u201d Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, and Madhu Sudan strengthen Dvir's proof of the Kakeya conjecture for finite fields. In \u201cThe Intersection of Two Halfspaces Has High Threshold Degree,\u201d Alexander Sherstov proves a lower bound on the degree of polynomials whose signs agree with the conjunction of two threshold functions. This implies a lower bound on the complexity of using perceptron-type algorithms to learn such functions. In \u201cKKL, Kruskal--Katona, and Monotone Nets,\u201d Ryan O'Donnell and Karl Wimmer prove isoperimetric theorems for Cayley and Schreier graphs and give applications of their results to combinatorics and learning theory. In \u201cVertex Sparsification and Oblivious Reductions,\u201d Ankur Moitra proves that one can approximate the values of all flows between a small number of terminals in a large graph by constructing a much smaller graph and measuring the values of flows in the smaller graph. In \u201cDynamic and Nonuniform Pricing Strategies for Revenue Maximization,\u201d Tanmoy Chakraborty, Zhiyi Huang, and Sanjeev Khanna show that dynamic nonuniform pricing strategies can achieve significantly higher expected revenue than does static uniform pricing. In \u201cComposition of Low-Error 2-Query PCPs Using Decodable PCPs,\u201d Irit Dinur and Prahladh Harsha simplify Moshkovitz and Raz's construction of low-error 2-query probabilistically checkable proofs. In \u201cA Parallel Repetition Theorem for Any Interactive Argument,\u201d Iftach Haitner shows that, after a slight modification, the soundness error of any interactive argument can be decreased through parallel repetition.<\/jats:p>","DOI":"10.1137\/130973545","type":"journal-article","created":{"date-parts":[[2013,12,17]],"date-time":"2013-12-17T11:45:59Z","timestamp":1387280759000},"page":"2286-2286","source":"Crossref","is-referenced-by-count":0,"title":["Special Section on the Fiftieth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009)"],"prefix":"10.1137","volume":"42","author":[{"given":"Maria Florina","family":"Balcan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mark","family":"Braverman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel A.","family":"Spielman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,12,17]]},"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130973545","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:25Z","timestamp":1787337505000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130973545"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":0,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/130973545"],"URL":"https:\/\/doi.org\/10.1137\/130973545","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}