Papers accepted for presentation in STOC 2007, listed in the order in which they were submitted Leslie Ann Goldberg and Mark Jerrum. Inapproximability of the Tutte polynomial Claire Kenyon-Mathieu and Warren Schudy. How to rank with few errors: A PTAS for Weighted Feedback Arc Set on Tournaments Iftach Haitner and Omer Reingold. Statistically-Hiding Commitment from Any One-Way Function Hagit Attiya and Keren Censor. Tight Bounds for Asynchronous Randomized Consensus Ken-ichi Kawarabayashi and Bruce Reed. Computing crossing number in linear time Sergiu Hart and Yishay Mansour. The Communication Complexity of Uncoupled Nash Equilibrium Procedures Adi Shraibman and Nati Linial. Lower Bounds in Communication Complexity Based on Factorization Norms Andreas Björklund, Thore Husfeldt, Petteri Kaski and Mikko Koivisto. Fourier Meets M\"{o}bius: Fast Subset Convolution Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna and Kunal Talwar. Hardness of Routing with Congestion in Directed Graphs (Remark: this is a merged version of two submissions) Fang Wu and Li Zhang. Proportional response dynamics leads to market equilibrium Virginia Vassilevska, Ryan Williams and Raphael Yuster. All-Pairs Bottleneck Paths For General Graphs in Truly Sub-Cubic Time Frederic Magniez, Ashwin Nayak, Jeremie Roland and Miklos Santha. Search via Quantum Walk van vu and Terence Tao. The condition number of a randomly perturbed matrix Amir Shpilka. Interpolation of Depth-3 Arithmetic Circuits with two Multiplication Gates Sudipto Guha and Kamesh Munagala. Approximation Algorithms for Budgeted Learning Problems Christian Borgs, Jennifer T. Chayes, Constantinos Daskalakis and Sebastien Roch. First to Market is not Everything: an Analysis of Preferential Attachment with Fitness Thomas Holenstein. Parallel Repetition: Simplifications and the No-Signaling Case Shahar Dobzinski and Noam Nisan. Limitations of VCG-Based Mechanisms Lap Chi Lau, Joseph (Seffi) Naor, Mohammad Salavatipour and Mohit Singh. Survivable Network Design with Degree or Order Constraints Mohit Singh and Lap Chi Lau. Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal Grant Schoenebeck, Luca Trevisan and Madhur Tulsiani. Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut Alexander Sherstov. Separating AC^0 from Depth-2 Majority Circuits Saugata Basu. Combinatorial Complexity in O-minimal Geometry Vijay Vazirani and Kamal Jain. Eisenberg-Gale Markets: Algorithms and Structural Properties Piotr Indyk. Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1 Ronen Shaltiel and Christopher Umans. Low-end uniform hardness vs. randomness tradeoffs for AM Matthew Andrews, Kyomin Jung and Alexander Stolyar. Stability of the Max-Weight Routing and Scheduling Protocol in Dynamic Networks and at Critical Loads Bo Brinkman, Adriana Karagiozova and James Lee. Vertex cuts, random walks, and dimension reduction in series-parallel graphs Elchanan Mossel and Sebastien Roch. On the Submodularity of Influence in Social Networks Anna Pagh, Rasmus Pagh and Milan Ruzic. Linear Probing with Constant Independence Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz and Ronald de Wolf. Exponential separations for one-way quantum communication complexity, with applications to cryptography Pinar Heggernes, Christophe Paul, Jan Arne Telle and Yngve Villanger. Interval completions with few edges Patrick Donovan, Bruce Shepherd, Adrian Vetta and Gordon Wilfong. Bifurcated Network Flows Gianni Franceschini and S. Muthukrishnan. Optimal Suffix Selection Mohsen Bayati, David Gamarnik, Dimitry Katz, Chandra Nair and Prasad Tetali. Simple deterministic approximation algorithms for counting Peter Hoyer, Troy Lee and Robert Spalek. Negative weights make adversaries stronger Alex Samorodnitsky. Low-degree tests at large distances Gus Gutoski and John Watrous. Toward a general theory of quantum games Per Austrin. Balanced Max 2-Sat might not be the hardest Anand Bhalgat, Ramesh Hariharan, Debmalya Panigrahi and Kavitha Telikepalli. An \tilde{O}(mn) Gomory-Hu tree construction algorithm for unweighted graphs Elliot Anshelevich and Adriana Karagiozova. Terminal Backup, 3D Matching, and Covering Cubic Graphs Nicholas Harvey and John Dunagan. A New Criterion for Variable Metric Solvers of Systems of Linear Equations Matthias Englert, Harald Räcke and Matthias Westermann. Reordering Buffers for General Metric Spaces Stefan Kiefer, Michael Luttenberger and Javier Esparza. On the Convergence of Newton's Method for Monotone Systems of Polynomial Equations Venkatesan Guruswami and Prasad Raghavendra. A 3-Query PCP over Integers Julia Chuzhoy and Sanjeev Khanna. Polynomial Flow-Cut Gaps and Hardness of Directed Cut Problems Timothy M. Chan and Mihai Patrascu. Voronoi Diagrams in $n\cdot 2^{O(\sqrt{\lg\lg n})}$ Time Timothy M. Chan. More Algorithms for All-Pairs Shortest Paths in Weighted Graphs Vojtech Rödl and Mathias Schacht. Property testing in hypergraphs and the removal lemma Ittai Abraham, Yair Bartal and Ofer Neiman. Local Embeddings of Metric Spaces Stefan Dantchev. Rank Complexity Gap for Lovasz-Shrijver and Sherali-Adams Proof Systems Jin-Yi Cai and Pinyan Lu. Holographic Algorithms: From Art to Science Gyula Pap. Some new results on node-capacitated packing of A-paths Mihai Patrascu. Lower Bounds for 2-Dimensional Range Counting Sham Kakade, Adam Tauman Kalai and Katrina Ligett. Approximation Algorithms Going Online Jonathan Katz. On Achieving the ''Best of Both Worlds'' in Secure Multiparty Computation Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky and Amit Sahai. Zero-Knowledge from Secure Multiparty Computation Ishay Haviv and Oded Regev. Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors Amit Agarwal, Noga Alon and Moses Charikar. Improved Approximation for Directed Multicut and Directed Sparsest Cut Anna Gilbert, Martin Strauss, Joel Tropp and Roman Vershynin. One sketch for all: Fast algorithms for Compressed Sensing Paul Beame, T. S. Jayram and Atri Rudra. Lower Bounds for Randomized Read/Write Stream Algorithms Dan Gutfreund, Alexander Healy, Tali Kaufman and Guy Rothblum. Verifying and Decoding in Constant Depth Cynthia Dwork, Frank McSherry and Kunal Talwar. The Price of Privacy and the Limits of LP Decoding Thomas Hayes, Juan C. Vera and Eric Vigoda. Randomly coloring planar graphs with fewer colors than the maximum degree Cristopher Moore, Alexander Russell and Piotr Sniady. On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism Rahul Santhanam. Circuit Lower Bounds for Merlin-Arthur Classes Udi Wieder and Kunal Talwar. Balanced Allocations: The Weighted Case Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld and Ning Xie. Testing k-wise and Almost k-wise Independence Amit Deshpande and Kasturi Varadarajan. Sampling Based Dimension Reduction for Subspace Approximation Arash Asadpour and Amin Saberi. An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods Mark Braverman and Michael Yampolsky. Constructing Non-Computable Julia Sets Sergey Yekhanin. Towards 3-Query Locally Decodable Codes of Subexponential Length Sanjeev Arora and Satyen Kale. A Combinatorial, Primal-Dual approach to Semidefinite Programs Martin Fürer. Faster Integer Multiplication Rafael Pass and Muthuramakrishnan Venkitasubramaniam. An Efficient Parallel Repetition Theorem for Arthur-Merlin Games Chris Peikert and Alon Rosen. Lattices that Admit Logarithmic Worst-Case to Average-Case Connection Factors Kobbi Nissim, Sofya Raskhodnikova and Adam Smith. Smooth Sensitivity and Sampling in Private Data Analysis