science.io - 2010 ACM Symposium on Theory of computing

Conference: 2010 ACM Symposium on Theory of computing

Sort: New & recommended · Active · Top Recommended · New

	Faster approximate multicommodity flow using quadratically coupled flows By Jonathan A. Kelner, Gary L. Miller, Richard Peng 1 · 0 · from STOC 2010 · published 05/2012
	When the cut condition is enough: a complete characterization for multiflow problems in series-parallel networks By Amit Chakrabarti, Lisa Fleischer, Christophe Weibel 1 · 0 · from STOC 2010 · published 05/2012
	Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives By László A. Végh 1 · 0 · from STOC 2010 · published 05/2012
	Quantum money from hidden subspaces By Scott Aaronson, Paul Christiano 1 · 0 · from STOC 2010 · published 05/2012
	Certifiable quantum dice: or, true random number generation secure against quantum adversaries By Umesh Vazirani, Thomas Vidick 1 · 0 · from STOC 2010 · published 05/2012
	Span programs for functions with constant-sized 1-certificates: extended abstract By Aleksandrs Belovs 1 · 0 · from STOC 2010 · published 05/2012
	The cell probe complexity of dynamic range counting By Kasper Green Larsen 1 · 0 · from STOC 2010 · published 05/2012
	Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds By Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf 1 · 0 · from STOC 2010 · published 05/2012
	Polyhedral clinching auctions and the adwords polytope By Gagan Goel, Vahab Mirrokni, Renato Paes Leme 1 · 0 · from STOC 2010 · published 05/2012
	Matroid prophet inequalities By Robert Kleinberg, Seth Matthew Weinberg 1 · 0 · from STOC 2010 · published 05/2012
	Online matching with concave returns By Nikhil R. Devanur, Kamal Jain 1 · 0 · from STOC 2010 · published 05/2012
	Computing a nonnegative matrix factorization -- provably By Sanjeev Arora, Rong Ge, Ravindran Kannan, Ankur Moitra 1 · 0 · from STOC 2010 · published 05/2012
	On identity testing of tensors, low-rank recovery and compressed sensing By Michael A. Forbes, Amir Shpilka 1 · 0 · from STOC 2010 · published 05/2012
	Structure theorem and isomorphism test for graphs with excluded topological subgraphs By Martin Grohe, Dániel Marx 1 · 0 · from STOC 2010 · published 05/2012
	Short proofs for the determinant identities By Pavel Hrubes, Iddo Tzameret 1 · 0 · from STOC 2010 · published 05/2012
	Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space By Paul Beame, Christopher Beck, Russell Impagliazzo 1 · 0 · from STOC 2010 · published 05/2012
	On the virtue of succinct proofs: amplifying communication complexity hardness to time-space trade-offs in proof complexity By Trinh Huynh, Jakob Nordstrom 1 · 0 · from STOC 2010 · published 05/2012
	Determinism versus nondeterminism with arithmetic tests and computation: extended abstract By Miklós Ajtai 1 · 0 · from STOC 2010 · published 05/2012
	Solution of the propeller conjecture in R<sup>3</sup> By Steven Heilman, Aukosh Jagannath, Assaf Naor 1 · 0 · from STOC 2010 · published 05/2012
	2<sup>log1-ε <i>n</i></sup> hardness for the closest vector problem with preprocessing By Subhash A. Khot, Preyas Popat, Nisheeth K. Vishnoi 1 · 0 · from STOC 2010 · published 05/2012
	A new point of NP-hardness for unique games By Ryan O'Donnell, John Wright 1 · 0 · from STOC 2010 · published 05/2012
	Hypercontractivity, sum-of-squares proofs, and their applications By Boaz Barak, Fernando G.S.L. Brandao, Aram W. Harrow, Jonathan Kelner, David Steurer, Yuan Zhou 1 · 0 · from STOC 2010 · published 05/2012
	From irreducible representations to locally decodable codes By Klim Efremenko 1 · 0 · from STOC 2010 · published 05/2012
	Folded codes from function field towers and improved optimal rate list decoding By Venkatesan Guruswami, Chaoping Xing 1 · 0 · from STOC 2010 · published 05/2012
	Subspace evasive sets By Zeev Dvir, Shachar Lovett 1 · 0 · from STOC 2010 · published 05/2012
	Edge transitive ramanujan graphs and symmetric LDPC good codes By Tali Kaufman, Alexander Lubotzky 1 · 0 · from STOC 2010 · published 05/2012
	Approximation algorithms for semi-random partitioning problems By Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan 1 · 0 · from STOC 2010 · published 05/2012
	A near-linear time ε-approximation algorithm for geometric bipartite matching By R. Sharathkumar, Pankaj K. Agarwal 1 · 0 · from STOC 2010 · published 05/2012
	Using petal-decompositions to build a low stretch spanning tree By Ittai Abraham, Ofer Neiman 1 · 0 · from STOC 2010 · published 05/2012
	Improved smoothed analysis of multiobjective optimization By Tobias Brunsch, Heiko Röglin 1 · 0 · from STOC 2010 · published 05/2012

more ->

Features coming soon:

Author profiles -- Claim your papers.
Groups -- Create a group for your department.
Paper revisions and version control.

Comments, suggestions, errors?