## Jeffrey Scott Vitter, Paul G. Spirakis, Mihalis Yannakakis

*Proceedings of the 33rd Annual ACM Symposium on Theory of Computing*

STOC, 2001.

@proceedings{STOC-2001, address = "Crete, Greece", editor = "Jeffrey Scott Vitter and Paul G. Spirakis and Mihalis Yannakakis", isbn = "1-58113-349-9", publisher = "{ACM}", title = "{Proceedings of the 33rd Annual ACM Symposium on Theory of Computing}", year = 2001, }

### Contents (86 items)

- STOC-2001-CharikarP #clustering
- Clustering to minimize the sum of cluster diameters (MC, RP), pp. 1–10.
- STOC-2001-BartalCR #approximate #clustering #metric
- Approximating min-sum k-clustering in metric spaces (YB, MC, DR), pp. 11–20.
- STOC-2001-AryaGKMP #heuristic #problem
- Local search heuristic for k-median and facility location problems (VA, NG, RK, AM, KM, VP), pp. 21–29.
- STOC-2001-Meyerson
- Profit-earning facility location (AM), pp. 30–36.
- STOC-2001-AmbainisBNVW #quantum
- One-dimensional quantum walks (AA, EB, AN, AV, JW), pp. 37–49.
- STOC-2001-AmbainisKV #graph #quantum
- Quantum walks on graphs (DA, AA, JK, UVV), pp. 50–59.
- STOC-2001-Watrous #algorithm #quantum
- Quantum algorithms for solvable groups (JW), pp. 60–67.
- STOC-2001-GrigniSVV #algorithm #problem #quantum
- Quantum mechanical algorithms for the nonabelian hidden subgroup problem (MG, LJS, MV, UVV), pp. 68–74.
- STOC-2001-Tokuyama #multi #optimisation #parametricity #problem
- Minimax parametric optimization problems and multi-dimensional parametric searching (TT), pp. 75–83.
- STOC-2001-ChekuriKZ #algorithm
- Algorithms for minimizing weighted flow time (CC, SK, AZ), pp. 84–93.
- STOC-2001-BecchettiL #parallel #scheduling
- Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines (LB, SL), pp. 94–103.
- STOC-2001-Roughgarden #scheduling
- Stackelberg scheduling strategies (TR), pp. 104–113.
- STOC-2001-Valiant #polynomial #quantum
- Quantum computers that can be simulated classically in polynomial time (LGV), pp. 114–123.
- STOC-2001-KlauckNTZ #communication #complexity #interactive #quantum #set
- Interaction in quantum communication and the complexity of set disjointness (HK, AN, ATS, DZ), pp. 124–133.
- STOC-2001-Ambainis #bound #protocol #quantum
- A new protocol and lower bounds for quantum coin flipping (AA), pp. 134–142.
- STOC-2001-Ta-ShmaUZ
- Loss-less condensers, unbalanced expanders, and extractors (ATS, CU, DZ), pp. 143–152.
- STOC-2001-MostefaouiRR #distributed
- Conditions on input vectors for consensus solvability in asynchronous distributed systems (AM, SR, MR), pp. 153–162.
- STOC-2001-KempeKD #protocol
- Spatial gossip and resource location protocols (DK, JMK, AJD), pp. 163–172.
- STOC-2001-ElkinP #graph
- (1+ε,β)-Spanner Constructions for General Graphs (ME, DP), pp. 173–182.
- STOC-2001-ThorupZ #approximate #distance
- Approximate distance oracles (MT, UZ), pp. 183–192.
- STOC-2001-Ta-ShmaZ
- Extractor codes (ATS, DZ), pp. 193–199.
- STOC-2001-Elkies #composition
- Excellent codes from modular curves (NDE), pp. 200–208.
- STOC-2001-Shparlinski #approximate #finite #polynomial
- Sparse polynomial approximation in finite fields (IS), pp. 209–215.
- STOC-2001-KlivansS #multi #performance #testing
- Randomness efficient identity testing of multivariate polynomials (AK, DAS), pp. 216–223.
- STOC-2001-Thorup
- Fully-dynamic min-cut (MT), pp. 224–230.
- STOC-2001-Grohe #polynomial
- Computing crossing numbers in quadratic time (MG), pp. 231–236.
- STOC-2001-Kosaraju #graph #parallel
- Euler paths in series parallel graphs (SRK), pp. 237–240.
- STOC-2001-SchaeferS #decidability #graph #string
- Decidability of string graphs (MS, DS), pp. 241–246.
- STOC-2001-SanjeevK #learning
- Learning mixtures of arbitrary gaussians (SA, RK), pp. 247–257.
- STOC-2001-KlivansS01a #learning
- Learning DNF in time 2Õ(n1/3) (AK, RAS), pp. 258–265.
- STOC-2001-Bar-YossefKS #algorithm #bound
- Sampling algorithms: lower bounds and applications (ZBY, RK, DS), pp. 266–275.
- STOC-2001-ParnasR #metric #testing
- Testing metric properties (MP, DR), pp. 276–285.
- STOC-2001-FischerN #matrix #testing
- Testing of matrix properties (EF, IN), pp. 286–295.
- STOC-2001-SpielmanT #algorithm #analysis #polynomial #why
- Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time (DAS, SHT), pp. 296–305.
- STOC-2001-GartnerSTWV
- One line and n points (BG, JS, FT, EW, PV), pp. 306–315.
- STOC-2001-IckingM #3d #bound #complexity #diagrams #distance
- A tight bound for the complexity of voroni diagrams under polyhedral convex distance functions in 3D (CI, LM), pp. 316–321.
- STOC-2001-ChazelleL #bound
- Lower bounds for intersection searching and fractional cascading in higher dimension (BC, DL), pp. 322–329.
- STOC-2001-BorgsCP #clustering #integer #problem #scalability
- Sharp threshold and scaling window for the integer partitioning problem (CB, JTC, BP), pp. 330–336.
- STOC-2001-AchlioptasBM #complexity #proving
- A sharp threshold in proof complexity (DA, PB, MSOM), pp. 337–346.
- STOC-2001-PitassiR #bound #principle
- Regular resolution lower bounds for the weak pigeonhole principle (TP, RR), pp. 347–355.
- STOC-2001-AraiPU #complexity
- The complexity of analytic tableaux (NHA, TP, AU), pp. 356–363.
- STOC-2001-JainV #algorithm #approximate #game studies
- Applications of approximation algorithms to cooperative games (KJ, VVV), pp. 364–372.
- STOC-2001-MossR #algorithm #approximate #problem
- Approximation algorithms for constrained for constrained node weighted steiner tree problems (AM, YR), pp. 373–382.
- STOC-2001-GuhaMM #approximate #constant #problem
- A constant factor approximation for the single sink edge installation problems (SG, AM, KM), pp. 383–388.
- STOC-2001-GuptaKKRY #design #multi #network #problem
- Provisioning a virtual private network: a network design problem for multicommodity flow (AG, JMK, AK, RR, BY), pp. 389–398.
- STOC-2001-LachishR #bound
- Explicit lower bound of 4.5n — o(n) for boolena circuits (OL, RR), pp. 399–408.
- STOC-2001-RazS #bound #matrix
- Lower bounds for matrix product, in bounded depth circuits with arbitrary gates (RR, AS), pp. 409–418.
- STOC-2001-BolligW #bound #branch #integer #multi #using
- A read-once branching program lower bound of Ω(2n/4) for integer multiplication using universal (BB, PW), pp. 419–424.
- STOC-2001-Pagh #complexity #on the
- On the cell probe complexity of membership and perfect hashing (RP), pp. 425–432.
- STOC-2001-FeigeS #on the
- On the integrality ratio of semidefinite relaxations of MAX CUT (UF, GS), pp. 433–442.
- STOC-2001-GoemansW #algorithm #approximate #problem #programming
- Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming (MXG, DPW), pp. 443–452.
- STOC-2001-Trevisan #bound #optimisation #problem
- Non-approximability results for optimization problems on bounded degree instances (LT), pp. 453–461.
- STOC-2001-MolloyR #graph
- Colouring graphs when the number of colours is nearly the maximum degree (MM, BAR), pp. 462–470.
- STOC-2001-GuhaKS
- Data-streams and histograms (SG, NK, KS), pp. 471–475.
- STOC-2001-AlstrupBR
- Optimal static range reporting in one dimension (SA, GSB, TR), pp. 476–482.
- STOC-2001-ErgunSSS #performance
- Biased dictionaries with fast insert/deletes (FE, SCS, JS, RKS), pp. 483–491.
- STOC-2001-NaorT #data type #independence #named
- Anti-presistence: history independent data structures (MN, VT), pp. 492–501.
- STOC-2001-KarlinKR
- Dynamic TCP acknowledgement and other stories about e/(e-1) (ARK, CK, DR), pp. 502–509.
- STOC-2001-MavronicolasS
- The price of selfish routing (MM, PGS), pp. 510–519.
- STOC-2001-KesselmanLMPSS
- Buffer overflow management in QoS switches (AK, ZL, YM, BPS, BS, MS), pp. 520–529.
- STOC-2001-Vocking #permutation
- Almost optimal permutation routing on hypercubes (BV), pp. 530–539.
- STOC-2001-JayramKKSS #online
- Online server allocation in a server farm via benefit task systems (TSJ, TK, RK, BS, MS), pp. 540–549.
- STOC-2001-HaleviKKN #approximate #np-hard
- Private approximation of NP-hard functions (SH, RK, EK, KN), pp. 550–559.
- STOC-2001-KilianP #concurrent
- Concurrent and resettable zero-knowledge in poly-loalgorithm rounds (JK, EP), pp. 560–569.
- STOC-2001-CanettiKPR #black box #concurrent
- Black-box concurrent zero-knowledge requires Ω(log n) rounds (RC, JK, EP, AR), pp. 570–579.
- STOC-2001-GennaroIKR #complexity #multi
- The round complexity of verifiable secret sharing and secure multicast (RG, YI, EK, TR), pp. 580–589.
- STOC-2001-NaorN #communication #evaluation #protocol
- Communication preserving protocols for secure function evaluation (MN, KN), pp. 590–599.
- STOC-2001-Yao #complexity
- Some perspective on computational complexity (ACCY), p. 600.
- STOC-2001-AjtaiKS #algorithm #problem
- A sieve algorithm for the shortest lattice vector problem (MA, RK, DS), pp. 601–610.
- STOC-2001-AchlioptasM #matrix #performance #rank
- Fast computation of low rank matrix (DA, FM), pp. 611–618.
- STOC-2001-AzarFKMS #analysis
- Spectral analysis of data (YA, AF, ARK, FM, JS), pp. 619–626.
- STOC-2001-DunaganV
- Optimal outlier removal in high-dimensional (JD, SV), pp. 627–636.
- STOC-2001-WangW
- Estimating true evolutionary distances between genomes (LSW, TW), pp. 637–646.
- STOC-2001-Muller-OlmS #on the #parallel #slicing #source code
- On optimal slicing of parallel programs (MMO, HS), pp. 647–656.
- STOC-2001-GroheSS #evaluation #query #question
- When is the evaluation of conjunctive queries tractable? (MG, TS, LS), pp. 657–666.
- STOC-2001-BulatovKJ #complexity #constraints
- The complexity of maximal constraint languages (AAB, AAK, PJ), pp. 667–674.
- STOC-2001-AlfaroM #game studies
- Quantitative solution of ω-regular games (LdA, RM), pp. 675–683.
- STOC-2001-Vatan #automaton #probability
- Distribution functions of probabilistic automata (FV), pp. 684–693.
- STOC-2001-Gacs #sequence
- Compatible sequences and a slow Winkler percolation (PG), pp. 694–703.
- STOC-2001-MontenegroS #agile #geometry #markov
- Edge isoperimetry and rapid mixing on matroids and geometric Markov chains (RM, JBS), pp. 704–711.
- STOC-2001-JerrumSV #algorithm #approximate #matrix #polynomial
- A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries (MJ, AS, EV), pp. 712–721.
- STOC-2001-SimaO
- Computing with continuous-time Liapunov systems (JS, PO), pp. 722–731.
- STOC-2001-DurandLS
- Complex tilings (BD, LAL, AS), pp. 732–739.
- STOC-2001-AdlemanCGH #self
- Running time and program size for self-assembled squares (LMA, QC, AG, MDAH), pp. 740–748.
- STOC-2001-Papadimitriou #algorithm #game studies #internet
- Algorithms, games, and the internet (CHP), pp. 749–753.
- STOC-2001-Trakhtenbrot #automaton
- Automata, circuits and hybrids: facets of continuous time (BAT), pp. 754–755.

11 ×#algorithm

10 ×#problem

9 ×#approximate

9 ×#bound

8 ×#complexity

7 ×#quantum

5 ×#graph

5 ×#multi

5 ×#polynomial

4 ×#matrix

10 ×#problem

9 ×#approximate

9 ×#bound

8 ×#complexity

7 ×#quantum

5 ×#graph

5 ×#multi

5 ×#polynomial

4 ×#matrix