John H. Reif
Proceedings of the 34th Annual ACM Symposium on Theory of Computing
STOC, 2002.

@proceedings{STOC-2002,
	address       = "Québec, Canada",
	editor        = "John H. Reif",
	isbn          = "1-58113-495-9",
	publisher     = "{ACM}",
	title         = "{Proceedings of the 34th Annual ACM Symposium on Theory of Computing}",
	year          = 2002,
}

Contents (92 items)

16 ×#approximate
12 ×#algorithm
8 ×#complexity
8 ×#on the
8 ×#problem
8 ×#random
6 ×#bound
6 ×#graph
6 ×#scheduling
4 ×#multi

STOC-2002-SchaeferSS #graph #string

Recognizing string graphs in NP (MS, ES, DS), pp. 1–6.

STOC-2002-Chan #geometry

Dynamic subgraph connectivity with geometric applications (TMC), pp. 7–13.

STOC-2002-EiterGM #generative

New results on monotone dualization and generating hypergraph transversals (TE, GG, KM), pp. 14–22.

STOC-2002-AdlemanCGHKER #combinator #optimisation #problem #self

Combinatorial optimization problems in self-assembly (LMA, QC, AG, MDAH, DK, PMdE, PWKR), pp. 23–32.

STOC-2002-DinurS

The importance of being biased (ID, SS), pp. 33–42.

STOC-2002-HastadV #on the #random

On the advantage over a random assignment (JH, SV), pp. 43–52.

STOC-2002-GoldbergKP #complexity #random

The complexity of choosing an H-colouring (nearly) uniformly at random (LAG, SK, MP), pp. 53–62.

STOC-2002-KargerL #graph #random

Random sampling in residual graphs (DRK, MSL), pp. 63–66.

STOC-2002-DengPS #complexity #on the

On the complexity of equilibria (XD, CHP, SS), pp. 67–71.

STOC-2002-FiatGHK

Competitive generalized auctions (AF, AVG, JDH, ARK), pp. 72–81.

STOC-2002-DrineasKR #recommendation

Competitive recommendation systems (PD, IK, PR), pp. 82–90.

STOC-2002-Molloy #graph

The Glauber dynamics on colourings of a graph with high girth and maximum degree (MM), pp. 91–98.

STOC-2002-Gacs #random #scheduling

Clairvoyant scheduling of random walks (PG), pp. 99–108.

STOC-2002-BertsimasV #random #source code

Solving convex programs by random walks (DB, SV), pp. 109–115.

STOC-2002-Papadimitriou

The Joy of Theory (CHP), p. 116.

STOC-2002-BaswanaHS #algorithm #maintenance #transitive

Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths (SB, RH, SS), pp. 117–123.

STOC-2002-Kontogiannis #algorithm #bound #online #scheduling

Lower bounds & competitive algorithms for online scheduling of unit-size tasks to related machines (SCK), pp. 124–133.

STOC-2002-Albers #on the #online #random #scheduling

On randomized online scheduling (SA), pp. 134–143.

STOC-2002-Raz #complexity #matrix #on the

On the complexity of matrix product (RR), pp. 144–151.

STOC-2002-GilbertGIMS #fourier

Near-optimal sparse fourier representations via sampling (ACG, SG, PI, SM, MS), pp. 152–161.

STOC-2002-AroraK #algebra #semistructured data

Fitting algebraic curves to noisy data (SA, SK), pp. 162–169.

STOC-2002-ScharbrodtSS #analysis #scheduling

A new average case analysis for completion time scheduling (MS, TS, AS), pp. 170–178.

STOC-2002-ChanLTW #analysis #video

A unified analysis of hot video schedulers (WTC, TWL, HFT, PWHW), pp. 179–188.

STOC-2002-SrinivasanA #multi #scheduling

Optimal rate-based scheduling on multiprocessors (AS, JHA), pp. 189–198.

STOC-2002-AchlioptasM #graph

Almost all graphs with average degree 4 are 3-colorable (DA, CM), pp. 199–208.

STOC-2002-Molloy02a #constraints #modelling #problem #random

Models and thresholds for random constraint satisfaction problems (MM), pp. 209–217.

STOC-2002-Smyth #difference

Reimer’s inequality and tardos’ conjecture (CDS), pp. 218–221.

STOC-2002-ChienRS #algebra #approximate

Clifford algebras and approximating the permanent (SC, LER, AS), pp. 222–231.

STOC-2002-AlonVKK #approximate #problem #random

Random sampling and approximation of MAX-CSP problems (NA, WFdlV, RK, MK), pp. 232–239.

STOC-2002-CryanD #algorithm #approximate #constant #polynomial

A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant (MC, MED), pp. 240–249.

STOC-2002-BadoiuHI #approximate #clustering

Approximate clustering via core-sets (MB, SHP, PI), pp. 250–257.

STOC-2002-AlbersFG #locality #on the

On paging with locality of reference (SA, LMF, OG), pp. 258–267.

STOC-2002-ArgeBDHM #algorithm #graph #queue

Cache-oblivious priority queue and graph algorithm applications (LA, MAB, EDD, BHM, JIM), pp. 268–276.

STOC-2002-Bachmat #analysis #scheduling #sequence

Average case analysis for batched disk scheduling and increasing subsequences (EB), pp. 277–286.

STOC-2002-CzumajKV

Selfish traffic allocation for server farms (AC, PK, BV), pp. 287–296.

STOC-2002-ChekuriK #approximate

Approximation schemes for preemptive weighted flow time (CC, SK), pp. 297–305.

STOC-2002-CheriyanVV #algorithm #approximate #low cost

Approximation algorithms for minimum-cost k-vertex connected subgraphs (JC, SV, AV), pp. 306–312.

STOC-2002-JainV #algorithm

Equitable cost allocations via primal-dual-type algorithms (KJ, VVV), pp. 313–321.

STOC-2002-DworkS #proving

2-round zero knowledge and proof auditors (CD, LJS), pp. 322–331.

STOC-2002-Goldreich #concurrent #revisited

Concurrent zero-knowledge with timing, revisited (OG), pp. 332–340.

STOC-2002-DziembowskiM #bound #proving #security

Tight security proofs for the bounded-storage model (SD, UMM), pp. 341–350.

STOC-2002-Khot #approximate

Hardness results for approximate hypergraph coloring (SK), pp. 351–359.

STOC-2002-SaksS #approximate #bound #data type #distance

Space lower bounds for distance approximation in the data stream model (MES, XS), pp. 360–369.

STOC-2002-AjtaiJKS #approximate #data type

Approximate counting of inversions in a data stream (MA, TSJ, RK, DS), pp. 370–379.

STOC-2002-Charikar #algorithm #estimation #similarity

Similarity estimation techniques from rounding algorithms (MC), pp. 380–388.

STOC-2002-GilbertGIKMS #algorithm #approximate #maintenance #performance

Fast, small-space algorithms for approximate histogram maintenance (ACG, SG, PI, YK, SM, MS), pp. 389–398.

STOC-2002-AnshelevichKK #algorithm

Stability of load balancing algorithms in dynamic adversarial systems (EA, DK, JMK), pp. 399–406.

STOC-2002-Adler #probability #trade-off

Tradeoffs in probabilistic packet marking for IP traceback (MA), pp. 407–418.

STOC-2002-CooperF #crawling #graph #web

Crawling on web graphs (CC, AMF), pp. 419–427.

STOC-2002-Roughgarden #independence #network

The price of anarchy is independent of the network topology (TR), pp. 428–437.

STOC-2002-ElkinK #algorithm #approximate #combinator #problem

Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem (ME, GK), pp. 438–447.

STOC-2002-AlekhnovichJPU #exponential

An exponential separation between regular and general resolution (MA, JJ, TP, AU), pp. 448–456.

STOC-2002-Ben-Sasson #trade-off

Size space tradeoffs for resolution (EBS), pp. 457–464.

STOC-2002-HellersteinR #learning #using

Exact learning of DNF formulas using DNF hypotheses (LH, VR), pp. 465–473.

STOC-2002-FischerLNRRS #testing

Monotonicity testing over general poset domains (EF, EL, IN, SR, RR, AS), pp. 474–483.

STOC-2002-BarakL #polynomial #simulation #strict

Strict polynomial-time in simulation and extraction (BB, YL), pp. 484–493.

STOC-2002-CanettiLOS #composition #multi

Universally composable two-party and multi-party secure computation (RC, YL, RO, AS), pp. 494–503.

STOC-2002-Ajtai #memory management

The invasiveness of off-line memory checking (MA), pp. 504–513.

STOC-2002-LindellLR #authentication #composition #on the

On the composition of authenticated byzantine agreement (YL, AL, TR), pp. 514–523.

STOC-2002-AspnesSS #infinity

Wait-free consensus with infinite arrivals (JA, GS, JS), pp. 524–533.

STOC-2002-Feige #approximate #complexity

Relations between average case complexity and approximation complexity (UF), pp. 534–543.

STOC-2002-Holmerin #approximate

Vertex cover on 4-regular hyper-graphs is hard to approximate within 2-epsilon (JH), pp. 544–552.

STOC-2002-Raz02a #bound #principle

Resolution lower bounds for the weak pigeonhole principle (RR), pp. 553–562.

STOC-2002-Ben-Sasson02a #bound

Hard examples for bounded depth frege (EBS), pp. 563–572.

STOC-2002-KaplanST

Meldable heaps and boolean union-find (HK, NS, RET), pp. 573–582.

STOC-2002-BrodalLMTT #pointer

Optimal finger search trees in the pointer machine (GSB, GL, CM, AKT, KT), pp. 583–591.

STOC-2002-ColeH #verification

Verifying candidate matches in sparse and wildcard matching (RC, RH), pp. 592–601.

STOC-2002-Han #linear #sorting

Deterministic sorting in O(nlog log n) time and linear space (YH), pp. 602–608.

STOC-2002-Micciancio #encryption #worst-case

Improved cryptographic hash functions with worst-case/average-case connection (DM), pp. 609–618.

STOC-2002-Sivakumar #algorithm #complexity

Algorithmic derandomization via complexity theory (DS), pp. 619–626.

STOC-2002-Umans #generative #pseudo

Pseudo-random generators for all hardnesses (CU), pp. 627–634.

STOC-2002-Aaronson #bound #problem #quantum

Quantum lower bound for the collision problem (SA), pp. 635–642.

STOC-2002-CrepeauGS #multi #quantum

Secure multi-party quantum computation (CC, DG, AS), pp. 643–652.

STOC-2002-Hallgren #algorithm #equation #polynomial #problem #quantum

Polynomial-time quantum algorithms for Pell’s equation and the principal ideal problem (SH), pp. 653–658.

STOC-2002-CapalboRVW

Randomness conductors and constant-degree lossless expanders (MRC, OR, SPV, AW), pp. 659–668.

STOC-2002-MeshulamW #symmetry

Expanders from symmetric codes (RM, AW), pp. 669–677.

STOC-2002-BatuDKR #approximate #complexity

The complexity of approximating entropy (TB, SD, RK, RR), pp. 678–687.

STOC-2002-BeameV #communication #complexity #multi #nearest neighbour #problem #trade-off

Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems (PB, EV), pp. 688–697.

STOC-2002-NayakS #communication #on the #quantum

On communication over an entanglement-assisted quantum channel (AN, JS), pp. 698–704.

STOC-2002-LinialMN

Girth and euclidean distortion (NL, AM, AN), pp. 705–711.

STOC-2002-Bas

Computing the betti numbers of arrangements (SB), pp. 712–720.

STOC-2002-AryaMM #approximate #diagrams

Space-efficient approximate Voronoi diagrams (SA, TM, DMM), pp. 721–730.

STOC-2002-JainMS #approach #problem

A new greedy approach for facility location problems (KJ, MM, AS), pp. 731–740.

STOC-2002-KargerR #metric #nearest neighbour #strict

Finding nearest neighbors in growth-restricted metrics (DRK, MR), pp. 741–750.

STOC-2002-ODonnell

Hardness amplification within NP (RO), pp. 751–760.

STOC-2002-AgolHT

3-manifold knot genus is NP-complet (IA, JH, WPT), pp. 761–766.

STOC-2002-Khot02a #game studies #on the #power of

On the power of unique 2-prover 1-round games (SK), pp. 767–775.

STOC-2002-JacksonKS

Learnability beyond AC0 (JCJ, AK, RAS), pp. 776–784.

STOC-2002-GolinKY

Huffman coding with unequal letter costs (MJG, CK, NEY), pp. 785–791.

STOC-2002-CharikarLLPPRSS #approximate #complexity #modelling

Approximating the smallest grammar: Kolmogorov complexity in natural models (MC, EL, DL, RP, MP, AR, AS, AS), pp. 792–801.

STOC-2002-Guruswami #linear

Limits to list decodability of linear codes (VG), pp. 802–811.

STOC-2002-GuruswamiI #linear

Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets (VG, PI), pp. 812–821.