Special Section on the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC 2012)

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. In “The Multiparty Communication Complexity of Set Disjointness,” Alexander Sherstov presents an $\Ome...