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)

12 ×#bound
10 ×#approximate
9 ×#algorithm
9 ×#graph
7 ×#problem
7 ×#quantum
6 ×#on the
5 ×#constant
5 ×#network
4 ×#metric

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.