Howard J. Karloff, Toniann Pitassi
Proceedings of the 44th Annual ACM Symposium on Theory of Computing
STOC, 2012.

@proceedings{STOC-2012,
	acmid         = "2213977",
	address       = "New York, New York, USA",
	editor        = "Howard J. Karloff and Toniann Pitassi",
	isbn          = "978-1-4503-1245-5",
	publisher     = "{ACM}",
	title         = "{Proceedings of the 44th Annual ACM Symposium on Theory of Computing}",
	year          = 2012,
}

Contents (89 items)

12 ×#multi
10 ×#algorithm
8 ×#approximate
8 ×#bound
8 ×#problem
6 ×#complexity
6 ×#graph
5 ×#random
4 ×#matrix
4 ×#on the

STOC-2012-KelnerMP #approximate #multi #performance #using

Faster approximate multicommodity flow using quadratically coupled flows (JAK, GLM, RP), pp. 1–18.

STOC-2012-ChakrabartiFW #multi #network #problem

When the cut condition is enough: a complete characterization for multiflow problems in series-parallel networks (AC, LF, CW), pp. 19–26.

STOC-2012-Vegh #algorithm #low cost #polynomial #problem

Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives (LAV), pp. 27–40.

STOC-2012-AaronsonC #quantum

Quantum money from hidden subspaces (SA, PC), pp. 41–60.

STOC-2012-VaziraniV #generative #quantum #random

Certifiable quantum dice: or, true random number generation secure against quantum adversaries (UVV, TV), pp. 61–76.

STOC-2012-Belovs #source code

Span programs for functions with constant-sized 1-certificates: extended abstract (AB), pp. 77–84.

STOC-2012-Larsen #complexity

The cell probe complexity of dynamic range counting (KGL), pp. 85–94.

STOC-2012-FioriniMPTW #bound #exponential #linear

Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds (SF, SM, SP, HRT, RdW), pp. 95–106.

STOC-2012-GoelML

Polyhedral clinching auctions and the adwords polytope (GG, VSM, RPL), pp. 107–122.

STOC-2012-KleinbergW

Matroid prophet inequalities (RK, SMW), pp. 123–136.

STOC-2012-DevanurJ #online

Online matching with concave returns (NRD, KJ), pp. 137–144.

STOC-2012-AroraGKM #matrix

Computing a nonnegative matrix factorization — provably (SA, RG, RK, AM), pp. 145–162.

STOC-2012-ForbesS #on the #rank #testing

On identity testing of tensors, low-rank recovery and compressed sensing (MAF, AS), pp. 163–172.

STOC-2012-GroheM #graph #morphism #theorem

Structure theorem and isomorphism test for graphs with excluded topological subgraphs (MG, DM), pp. 173–192.

STOC-2012-HrubesT #proving

Short proofs for the determinant identities (PH, IT), pp. 193–212.

STOC-2012-BeameBI #bound #trade-off

Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space (PB, CB, RI), pp. 213–232.

STOC-2012-HuynhN #communication #complexity #on the #proving #trade-off

On the virtue of succinct proofs: amplifying communication complexity hardness to time-space trade-offs in proof complexity (TH, JN), pp. 233–248.

STOC-2012-Ajtai #nondeterminism #testing

Determinism versus nondeterminism with arithmetic tests and computation: extended abstract (MA), pp. 249–268.

STOC-2012-HeilmanJN

Solution of the propeller conjecture in R3 (SH, AJ, AN), pp. 269–276.

STOC-2012-KhotPV #preprocessor #problem

2log1-ε n hardness for the closest vector problem with preprocessing (SK, PP, NKV), pp. 277–288.

STOC-2012-ODonnellW #game studies #np-hard

A new point of NP-hardness for unique games (RO, JW), pp. 289–306.

STOC-2012-BarakBHKSZ #proving

Hypercontractivity, sum-of-squares proofs, and their applications (BB, FGSLB, AWH, JAK, DS, YZ), pp. 307–326.

STOC-2012-Efremenko

From irreducible representations to locally decodable codes (KE), pp. 327–338.

STOC-2012-GuruswamiX

Folded codes from function field towers and improved optimal rate list decoding (VG, CX), pp. 339–350.

STOC-2012-DvirL #set

Subspace evasive sets (ZD, SL), pp. 351–358.

STOC-2012-KaufmanL #graph #symmetry #transitive

Edge transitive ramanujan graphs and symmetric LDPC good codes (TK, AL), pp. 359–366.

STOC-2012-MakarychevMV #algorithm #approximate #clustering #problem

Approximation algorithms for semi-random partitioning problems (KM, YM, AV), pp. 367–384.

STOC-2012-SharathkumarA #algorithm #approximate #geometry

A near-linear time ε-approximation algorithm for geometric bipartite matching (RS, PKA), pp. 385–394.

STOC-2012-AbrahamN #using

Using petal-decompositions to build a low stretch spanning tree (IA, ON), pp. 395–406.

STOC-2012-BrunschR #analysis #multi #optimisation

Improved smoothed analysis of multiobjective optimization (TB, HR), pp. 407–426.

STOC-2012-LeonardiR #order

Prior-free auctions with ordered bidders (SL, TR), pp. 427–434.

STOC-2012-ChawlaIL #black box #design #on the #reduction

On the limits of black-box reductions in mechanism design (SC, NI, BL), pp. 435–448.

STOC-2012-BeiCGL #design

Budget feasible mechanism design: from prior-free to bayesian (XB, NC, NG, PL), pp. 449–458.

STOC-2012-CaiDW #algorithm #multi

An algorithmic characterization of multi-dimensional mechanisms (YC, CD, SMW), pp. 459–478.

STOC-2012-GalHKPV #bound

Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates (AG, KAH, MK, PP, EV), pp. 479–494.

STOC-2012-ChanP #analysis #bound #fourier #network

Tight bounds for monotone switching networks via fourier analysis (SMC, AP), pp. 495–504.

STOC-2012-Braverman #complexity #interactive

Interactive information complexity (MB), pp. 505–524.

STOC-2012-Sherstov #communication #complexity #multi #set

The multiparty communication complexity of set disjointness (AAS), pp. 525–548.

STOC-2012-CheungKL #algorithm #matrix #performance #rank

Fast matrix rank algorithms and applications (HYC, TCK, LCL), pp. 549–562.

STOC-2012-HassaniehIKP #fourier

Nearly optimal sparse fourier transform (HH, PI, DK, EP), pp. 563–578.

STOC-2012-EtessamiSY #algorithm #branch #context-free grammar #multi #polynomial #probability #process

Polynomial time algorithms for multi-type branching processes and stochastic context-free grammars (KE, AS, MY), pp. 579–588.

STOC-2012-AdamaszekCER #online #scheduling

Optimal online buffer scheduling for block devices (AA, AC, ME, HR), pp. 589–598.

STOC-2012-AgrawalSSS #bound

Jacobian hits circuits: hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits (MA, CS, RS, NS), pp. 599–614.

STOC-2012-DvirMPY #branch #multi #source code

Separating multilinear branching programs and formulas (ZD, GM, SP, AY), pp. 615–624.

STOC-2012-GuptaKL #multi #re-engineering

Reconstruction of depth-4 multilinear circuits with top fan-in 2 (AG, NK, SVL), pp. 625–642.

STOC-2012-Kayal

Affine projections of polynomials: extended abstract (NK), pp. 643–662.

STOC-2012-BartalGK #approximate #polynomial #problem

The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme (YB, LAG, RK), pp. 663–672.

STOC-2012-Chuzhoy #on the

On vertex sparsifiers with Steiner nodes (JC), pp. 673–688.

STOC-2012-ChalermsookCEL #algorithm #approximate #concurrent

Approximation algorithms and hardness of integral concurrent flow (PC, JC, AE, SL), pp. 689–708.

STOC-2012-DaskalakisDS #learning

Learning poisson binomial distributions (CD, ID, RAS), pp. 709–728.

STOC-2012-DeDFS #approximate #parametricity #problem

Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces (AD, ID, VF, RAS), pp. 729–746.

STOC-2012-Sherstov12a #robust

Making polynomials robust to noise (AAS), pp. 747–758.

STOC-2012-GoyalK #network

Competitive contagion in networks (SG, MK), pp. 759–774.

STOC-2012-CebrianCVV #contract #robust

Finding red balloons with split contracts: robustness to individuals’ selfishness (MC, LC, AV, PV), pp. 775–788.

STOC-2012-BrandtIKK #analysis

An analysis of one-dimensional schelling segregation (CB, NI, GK, RK), pp. 789–804.

STOC-2012-Applebaum #generative #locality #pseudo #random

Pseudorandom generators with long stretch and low locality from random local one-way functions (BA), pp. 805–816.

STOC-2012-VadhanZ #generative #pseudo

Characterizing pseudoentropy and simplifying pseudorandom generator constructions (SPV, CJZ), pp. 817–836.

STOC-2012-Li #design #privacy

Design extractors, non-malleable condensers and privacy amplification (XL), pp. 837–854.

STOC-2012-Chuzhoy12a #constant #graph

Routing in undirected graphs with constant congestion (JC), pp. 855–874.

STOC-2012-AnKS #algorithm

Improving christofides’ algorithm for the s-t path TSP (HCA, RK, DBS), pp. 875–886.

STOC-2012-Williams #matrix #multi #performance

Multiplying matrices faster than coppersmith-winograd (VVW), pp. 887–898.

STOC-2012-Coja-OghlanP #satisfiability

Catching the k-NAESAT threshold (ACO, KP), pp. 899–908.

STOC-2012-CaiC #complexity #csp

Complexity of counting CSP with complex weights (JYC, XC), pp. 909–920.

STOC-2012-Molloy #graph #random

The freezing threshold for k-colourings of a random graph (MM), pp. 921–930.

STOC-2012-BartoK #constraints #problem #robust #satisfiability

Robust satisfiability of constraint satisfaction problems (LB, MK), pp. 931–940.

STOC-2012-WoodruffZ #bound #distributed #functional #monitoring

Tight bounds for distributed functional monitoring (DPW, QZ), pp. 941–960.

STOC-2012-Censor-HillelHKM #dependence #performance

Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance (KCH, BH, JAK, PM), pp. 961–970.

STOC-2012-BansalBJK #trade-off

Tight time-space tradeoff for mutual exclusion (NB, VB, PJ, RK), pp. 971–982.

STOC-2012-GiakkoupisW #bound #random

A tight RMR lower bound for randomized mutual exclusion (GG, PW), pp. 983–1002.

STOC-2012-GargMSV #algorithm

A complementary pivot algorithm for markets under separable, piecewise-linear concave utilities (JG, RM, MAS, VVV), pp. 1003–1016.

STOC-2012-AzarM #proving

Rational proofs (PDA, SM), pp. 1017–1028.

STOC-2012-AbernethyFW

Minimax option pricing meets black-scholes in the limit (JA, RMF, AW), pp. 1029–1040.

STOC-2012-MosselR #theorem

A quantitative gibbard-satterthwaite theorem without neutrality (EM, MZR), pp. 1041–1060.

STOC-2012-BourgainY

Monotone expansion (JB, AY), pp. 1061–1078.

STOC-2012-AlonMS #graph #scalability

Nearly complete graphs decomposable into large induced matchings and their applications (NA, AM, BS), pp. 1079–1090.

STOC-2012-KuperbergLP #combinator #probability

Probabilistic existence of rigid combinatorial structures (GK, SL, RP), pp. 1091–1106.

STOC-2012-DobzinskiV #complexity #query

From query complexity to computational complexity (SD, JV), pp. 1107–1116.

STOC-2012-LeeGT #clustering #higher-order #multi

Multi-way spectral partitioning and higher-order cheeger inequalities (JRL, SOG, LT), pp. 1117–1130.

STOC-2012-LouisRTV

Many sparse cuts via higher eigenvalues (AL, PR, PT, SV), pp. 1131–1140.

STOC-2012-OrecchiaSV #algorithm #approximate #exponential

Approximating the exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced separator (LO, SS, NKV), pp. 1141–1160.

STOC-2012-GoemansORZ

Matroids and integrality gaps for hypergraphic steiner tree relaxations (MXG, NO, TR, RZ), pp. 1161–1176.

STOC-2012-BrodalLT #fibonacci #strict

Strict fibonacci heaps (GSB, GL, RET), pp. 1177–1184.

STOC-2012-BulanekKS #bound #online #problem

Tight lower bounds for the online labeling problem (JB, MK, MES), pp. 1185–1198.

STOC-2012-AbrahamCG #approximate #distance #graph

Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels (IA, SC, CG), pp. 1199–1218.

STOC-2012-Lopez-AltTV #encryption #multi #on the fly

On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption (ALA, ET, VV), pp. 1219–1234.

STOC-2012-BoyleGJK #memory management #multi

Multiparty computation secure against continual memory leakage (EB, SG, AJ, YTK), pp. 1235–1254.

STOC-2012-HardtR #matrix #random

Beating randomized response on incoherent matrices (MH, AR), pp. 1255–1268.

STOC-2012-BhaskaraDKT #linear #query

Unconditional differentially private mechanisms for linear queries (AB, DD, RK, KT), pp. 1269–1284.

STOC-2012-MuthukrishnanN

Optimal private halfspace counting via discrepancy (SM, AN), pp. 1285–1292.