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