Leonard J. Schulman (Ed.):
Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010.
ACM 2010, ISBN 978-1-4503-0050-6
42. STOC 2010:
Cambridge, Massachusetts, USA
: Message passing algorithms: a success looking for theoreticians.
: A strong direct product theorem for disjointness.
: The maximum multiflow problems with bounded fractionality.
: Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms.
: Oblivious RAMs without cryptogrpahic assumptions.
: Improving exhaustive search implies superpolynomial lower bounds.
James B. Orlin
: Improved algorithms for computing fisher's market clearing prices: computing fisher's market clearing prices.
, Qin Zhang
: The limits of buffering: a tight lower bound for dynamic membership in the external memory model.
, Felipe Cucker
: Solving polynomial equations in smoothed polynomial time and a near solution to smale's 17th problem.
Alexander A. Sherstov
: Optimal bounds for sign-representing the intersection of two halfspaces by polynomials.
László A. Végh
: Augmenting undirected node-connectivity by one.
: Towards polynomial lower bounds for dynamic problems.
: Tensor-rank and lower bounds for arithmetic formulas.
: Tractable hypergraph properties for constraint satisfaction and conjunctive queries.
: Conditional hardness of precedence constrained scheduling on identical machines.