## Lawrence L. Larmore, Michel X. Goemans

*Proceedings of the 35th Annual ACM Symposium on Theory of Computing*

STOC, 2003.

@proceedings{STOC-2003, address = "San Diego, California, USA", editor = "Lawrence L. Larmore and Michel X. Goemans", isbn = "1-58113-674-9", publisher = "{ACM}", title = "{Proceedings of the 35th Annual ACM Symposium on Theory of Computing}", year = 2003, }

### Contents (80 items)

- STOC-2003-FriedlIMSS #quantum
- Hidden translation and orbit coset in quantum computing (KF, GI, FM, MS, PS), pp. 1–9.
- STOC-2003-Gurvits #complexity #problem #quantum
- Classical deterministic complexity of Edmonds’ Problem and quantum entanglement (LG), pp. 10–19.
- STOC-2003-AharonovT #generative #quantum #statistics
- Adiabatic quantum state generation and statistical zero knowledge (DA, ATS), pp. 20–29.
- STOC-2003-CharikarOP #algorithm #clustering #problem #streaming
- Better streaming algorithms for clustering problems (MC, LO, RP), pp. 30–39.
- STOC-2003-Plaxton #algorithm #approximate #problem
- Approximation algorithms for hierarchical location problems (CGP), pp. 40–49.
- STOC-2003-VegaKKR #approximate #clustering #problem
- Approximation schemes for clustering problems (WFdlV, MK, CK, YR), pp. 50–58.
- STOC-2003-ChildsCDFGS #algorithm #exponential #quantum
- Exponential algorithmic speedup by a quantum walk (AMC, RC, ED, EF, SG, DAS), pp. 59–68.
- STOC-2003-Klauck #quantum #sorting #trade-off
- Quantum time-space tradeoffs for sorting (HK), pp. 69–76.
- STOC-2003-Ya #on the #power of #quantum
- On the power of quantum fingerprinting (ACCY), pp. 77–81.
- STOC-2003-AzarR #multi #network
- Management of multi-queue switches in QoS networks (YA, YR), pp. 82–89.
- STOC-2003-AmirKR #approximate #constant #graph
- Constant factor approximation of vertex-cuts in planar graphs (EA, RK, SR), pp. 90–99.
- STOC-2003-AlonAA #online #problem #set
- The online set cover problem (NA, BA, YA, NB, JN), pp. 100–105.
- STOC-2003-KerenidisW #bound #exponential #quantum
- Exponential lower bound for 2-query locally decodable codes via a quantum argument (IK, RdW), pp. 106–115.
- STOC-2003-Tardo #probability
- Optimal probabilistic fingerprint codes (GT), pp. 116–125.
- STOC-2003-GuruswamiI #linear
- Linear time encodable and list decodable codes (VG, PI), pp. 126–135.
- STOC-2003-CoppersmithS #higher-order #semistructured data
- Reconstructing curves in three (and higher) dimensional space from noisy data (DC, MS), pp. 136–142.
- STOC-2003-KowalikK #constant #graph #query
- Short path queries in planar graphs in constant time (LK, MK), pp. 143–148.
- STOC-2003-Thorup #constant #integer #problem
- Integer priority queues with decrease key in constant time and the single source shortest paths problem (MT), pp. 149–158.
- STOC-2003-DemetrescuI #approach
- A new approach to dynamic all pairs shortest paths (CD, GFI), pp. 159–166.
- STOC-2003-ColeH #algorithm #performance
- A fast algorithm for computing steiner edge connectivity (RC, RH), pp. 167–176.
- STOC-2003-RettingerW #complexity #set
- The computational complexity of some julia sets (RR, KW), pp. 177–185.
- STOC-2003-SauerhoffW #bound #graph #integer #multi #trade-off
- Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions (MS, PW), pp. 186–195.
- STOC-2003-KalaiS
- Boosting in the presence of noise (AK, RAS), pp. 195–205.
- STOC-2003-MosselOS #learning
- Learning juntas (EM, RO, RAS), pp. 206–212.
- STOC-2003-KimV #generative #graph #random
- Generating random regular graphs (JHK, VHV), pp. 213–222.
- STOC-2003-AchlioptasP #random #satisfiability
- The threshold for random k-SAT is 2k (ln 2 — O(k)) (DA, YP), pp. 223–231.
- STOC-2003-BeierV #polynomial #random
- Random knapsack in expected polynomial time (RB, BV), pp. 232–241.
- STOC-2003-BansalP #scheduling
- Server scheduling in the Lp norm: a rising tide lifts all boat (NB, KP), pp. 242–250.
- STOC-2003-GeorgiouRS #scheduling
- Work-competitive scheduling for cooperative computing with dynamic groups (CG, AR, AAS), pp. 251–258.
- STOC-2003-FatourouFR #bound #implementation #multi
- A tight time lower bound for space-optimal implementations of multi-writer snapshots (PF, FEF, ER), pp. 259–268.
- STOC-2003-Hayes #graph
- Randomly coloring graphs of girth at least five (TPH), pp. 269–278.
- STOC-2003-MorrisP #evolution #mixin #set
- Evolving sets and mixin (BM, YP), pp. 279–286.
- STOC-2003-BobkovT
- Modified log-sobolev inequalities, mixing and hypercontractivity (SB, PT), pp. 287–296.
- STOC-2003-GilbertK #behaviour #on the
- On the fractal behavior of TCP (ACG, HJK), pp. 297–306.
- STOC-2003-BrodalF #on the
- On the limits of cache-obliviousness (GSB, RF), pp. 307–315.
- STOC-2003-BatuEKMRRS #algorithm #approximate #distance #edit distance #sublinear
- A sublinear algorithm for weakly approximating edit distance (TB, FE, JK, AM, SR, RR, RS), pp. 316–324.
- STOC-2003-ODonnellS #bound #polynomial
- New degree bounds for polynomial threshold functions (RO, RAS), pp. 325–334.
- STOC-2003-Bar-Yossef #bound
- Sampling lower bounds via information theory (ZBY), pp. 335–344.
- STOC-2003-Ben-SassonHR
- Some 3CNF properties are hard to test (EBS, PH, SR), pp. 345–354.
- STOC-2003-KabanetsI #bound #polynomial #proving #testing
- Derandomizing polynomial identity tests means proving circuit lower bounds (VK, RI), pp. 355–364.
- STOC-2003-GuptaKR #algorithm #approximate #design #network
- Simpler and better approximation algorithms for network design (AG, AK, TR), pp. 365–372.
- STOC-2003-ChenRS #algorithm #approximate #confluence
- Meet and merge: approximation algorithms for confluent flows (JC, RR, RS), pp. 373–382.
- STOC-2003-AzarCFKR #polynomial
- Optimal oblivious routing in polynomial time (YA, EC, AF, HK, HR), pp. 383–388.
- STOC-2003-KonemannR #approximate #bound
- Primal-dual meets local search: approximating MST’s with nonuniform degree bounds (JK, RR), pp. 389–395.
- STOC-2003-Ajtai #algorithm #approximate #behaviour #worst-case
- The worst-case behavior of schnorr’s algorithm approximating the shortest nonzero vector in a lattice (MA), pp. 396–406.
- STOC-2003-Regev #encryption
- New lattice based cryptographic constructions (OR), pp. 407–416.
- STOC-2003-GennaroGK #bound #encryption #performance
- Lower bounds on the efficiency of encryption and digital signature schemes (RG, YG, JK), pp. 417–425.
- STOC-2003-DamgardG #reuse
- Non-interactive and reusable non-malleable commitment schemes (ID, JG), pp. 426–437.
- STOC-2003-KrauthgamerL #graph
- The intrinsic dimensionality of graphs (RK, JRL), pp. 438–447.
- STOC-2003-FakcharoenpholRT #approximate #bound #metric
- A tight bound on approximating arbitrary metrics by tree metrics (JF, SR, KT), pp. 448–455.
- STOC-2003-Rabinovich #metric #on the
- On average distortion of embedding metrics into the line and into L1 (YR), pp. 456–462.
- STOC-2003-BartalLMN #metric #on the
- On metric ramsey-type phenomena (YB, NL, MM, AN), pp. 463–472.
- STOC-2003-DrorELM #sequence
- Touring a sequence of polygons (MD, AE, AL, JSBM), pp. 473–482.
- STOC-2003-GaoZ #composition #graph #metric
- Well-separated pair decomposition for the unit-disk graph metric and its applications (JG, LZ), pp. 483–492.
- STOC-2003-DeyGJ
- Alpha-shapes and flow shapes are homotopy equivalent (TKD, JG, MJ), pp. 493–502.
- STOC-2003-AwerbuchAM #online #optimisation
- Reducing truth-telling online mechanisms to online optimization (BA, YA, AM), pp. 503–510.
- STOC-2003-AnshelevichDTW #design #network
- Near-optimal network design with selfish agents (EA, AD, ÉT, TW), pp. 511–520.
- STOC-2003-ColeDR #network
- Pricing network edges for heterogeneous selfish users (RC, YD, TR), pp. 521–530.
- STOC-2003-ChazelleLM #algorithm #geometry #sublinear
- Sublinear geometric algorithms (BC, DL, AM), pp. 531–540.
- STOC-2003-AronovPST
- Distinct distances in three and higher dimensions (BA, JP, MS, GT), pp. 541–546.
- STOC-2003-AronovKS
- Cutting triangular cycles of lines in space (BA, VK, MS), pp. 547–555.
- STOC-2003-BuchsbaumKKRT
- OPT versus LOAD in dynamic storage allocation (ALB, HJK, CK, NR, MT), pp. 556–564.
- STOC-2003-KleinbergL #consistency
- Consistent load balancing via spread minimization (RDK, FTL), pp. 565–574.
- STOC-2003-AdlerHKV #network #peer-to-peer #probability #process
- A stochastic process on the hypercube with applications to peer-to-peer networks (MA, EH, RMK, VVV), pp. 575–584.
- STOC-2003-HalperinK
- Polylogarithmic inapproximability (EH, RK), pp. 585–594.
- STOC-2003-DinurGKR #multi
- A new multilayered PCP and the hardness of hypergraph vertex cover (ID, VG, SK, OR), pp. 595–601.
- STOC-2003-LuRVW #constant #named
- Extractors: optimal up to constant factors (CJL, OR, SPV, AW), pp. 602–611.
- STOC-2003-Ben-SassonSVW #testing
- Randomness-efficient low degree tests and short PCPs via epsilon-biased sets (EBS, MS, SPV, AW), pp. 612–621.
- STOC-2003-OstlinP #constant #linear
- Uniform hashing in constant time and linear space (AÖ, RP), pp. 622–628.
- STOC-2003-DietzfelbingerW #graph #random
- Almost random graphs with simple hash functions (MD, PW), pp. 629–638.
- STOC-2003-KaplanMT
- Dynamic rectangular intersection with priorities (HK, EM, RET), pp. 639–648.
- STOC-2003-Thorup03a #performance #query
- Space efficient dynamic stabbing with fast queries (MT), pp. 649–658.
- STOC-2003-GalR #bound
- Lower bounds on the amount of randomness in private computation (AG, AR), pp. 659–666.
- STOC-2003-JayramKKR #bound #problem
- Cell-probe lower bounds for the partial match problem (TSJ, SK, RK, YR), pp. 667–672.
- STOC-2003-JayramKS #complexity
- Two applications of information complexity (TSJ, RK, DS), pp. 673–682.
- STOC-2003-Lindell #bound
- Bounded-concurrent secure two-party computation without setup assumptions (YL), pp. 683–692.
- STOC-2003-Dyer #approximate #programming
- Approximate counting by dynamic programming (MED), pp. 693–699.
- STOC-2003-AlonS #graph #testing
- Testing subgraphs in directed graphs (NA, AS), pp. 700–709.
- STOC-2003-ItohTT #independence #on the #permutation #strict
- On the sample size of k-restricted min-wise independent permutations and other k-wise distributions (TI, YT, JT), pp. 710–719.
- STOC-2003-Friedman #proving
- A proof of Alon’s second eigenvalue conjecture (JF), pp. 720–724.

12 ×#bound

10 ×#approximate

9 ×#algorithm

9 ×#graph

7 ×#problem

7 ×#quantum

6 ×#on the

5 ×#constant

5 ×#network

4 ×#metric

10 ×#approximate

9 ×#algorithm

9 ×#graph

7 ×#problem

7 ×#quantum

6 ×#on the

5 ×#constant

5 ×#network

4 ×#metric