{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:35:47Z","timestamp":1787340947340,"version":"build-2736575974"},"reference-count":0,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2016,1]]},"abstract":"<jats:p>This issue of SICOMP contains seven specially selected papers from the Forty-Fourth Annual ACM Symposium on Theory of Computing, otherwise known as STOC 2012, held May 19 to 22 in New York, New York. 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. The program committee consisted of Richard Cleve, Parikshit Gopalan, Jason Hartline, Tom Hayes, Anna Karlin, Sanjeev Khanna, Andrew McGregor, Rina Panigrahy, Toniann Pitassi, Ran Raz, Charles Rackoff, Satish Rao, Oded Regev, Dana Ron, Guy Rothblum, Amin Saberi, Rahul Santhanam, Shubhangi Saraf, Daniel Spielman, Madhur Tulsiani, Suresh Venkatasubramanian, Avi Wigderson, and David Williamson. They selected 90 papers out of 303 submissions. We briefly describe the papers that appear here.<\/jats:p>\n                  <jats:p>In \u201cThe Multiparty Communication Complexity of Set Disjointness,\u201d Alexander Sherstov presents an $\\Omega(n\/4^k)^{1\/4}$ lower bound on the communication complexity of the $k$-party set disjointness problem. Previously, no polynomial lower bounds were known for $k=\\omega(1)$ players. In \u201cRouting in Undirected Graphs with Constant Congestion,\u201d Julia Chuzhoy presents an efficient randomized algorithm that, given a set of demand pairs, routes a polylogarithmic fraction of the maximum number of demand pairs that could be routed on edge-disjoint paths. The routing returned uses each edge at most a constant number of times, whereas the best previous best algorithm guaranteed only polylogarithmic reuse of a single edge. In \u201cJacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-$3$ Transcendence Degree-$k$ Circuits,\u201d Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, and Nitin Saxena study the black box identity testing problem in arithmetic complexity. They present an approach using the Jacobian that unifies and generalizes several previous results on polynomial time black box identity testing and is also useful for proving circuit lower bounds. In \u201cThe Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme,\u201d Yair Bartal, Lee-Ad Gottlieb, and Robert Krauthgamer present an efficient randomized $(1+\\epsilon)$-approximation algorithm for the traveling salesman problem when the distances correspond to an arbitrary metric space with bounded intrinsic dimension. In \u201cComputing a Nonnegative Matrix Factorization---Provably,\u201d Sanjeev Arora, Rong Ge, Ravi Kannan, and Ankur Moitra investigate the problem of factorizing a matrix into two nonnegative matrices, an important problem in machine learning, among other areas. They present efficient algorithms for certain natural families of matrices, along with a complementary hardness result. In \u201cTime-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space,\u201d Paul Beame, Chris Beck, and Russell Impagliazzo give the first size-space tradeoffs for resolution proofs that apply to superlinear space. In \u201cRobustly Solvable Constraint Satisfaction Problems,\u201d Libor Barto and Marcin Kozik characterize constraint satisfaction problems that are robustly satisfiable. Guruswami and Zhou conjectured that a constraint satisfaction problem is robustly satisfiable if and only if it has bounded width. Barto and Kozik confirm this conjecture.<\/jats:p>\n                  <jats:p>We thank the authors and the program committee for their hard work, and we especially thank the reviewers for their work in evaluating and improving the submitted papers.<\/jats:p>","DOI":"10.1137\/16n974127","type":"journal-article","created":{"date-parts":[[2016,8,30]],"date-time":"2016-08-30T13:23:26Z","timestamp":1472563406000},"page":"1448-1449","source":"Crossref","is-referenced-by-count":0,"title":["Special Section on the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC 2012)"],"prefix":"10.1137","volume":"45","author":[{"given":"Andrew","family":"McGregor","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rahul","family":"Santhanam","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2016,8,30]]},"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16N974127","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:57:34Z","timestamp":1787338654000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16N974127"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1]]},"references-count":0,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["10.1137\/16N974127"],"URL":"https:\/\/doi.org\/10.1137\/16n974127","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1]]}}}