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

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

16 ×#approximate

12 ×#algorithm

8 ×#complexity

8 ×#on the

8 ×#problem

8 ×#random

6 ×#bound

6 ×#graph

6 ×#scheduling

4 ×#multi

12 ×#algorithm

8 ×#complexity

8 ×#on the

8 ×#problem

8 ×#random

6 ×#bound

6 ×#graph

6 ×#scheduling

4 ×#multi