## 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)

- 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.

12 ×#multi

10 ×#algorithm

8 ×#approximate

8 ×#bound

8 ×#problem

6 ×#complexity

6 ×#graph

5 ×#random

4 ×#matrix

4 ×#on the

10 ×#algorithm

8 ×#approximate

8 ×#bound

8 ×#problem

6 ×#complexity

6 ×#graph

5 ×#random

4 ×#matrix

4 ×#on the