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)

11 ×#algorithm
10 ×#problem
9 ×#approximate
9 ×#bound
8 ×#complexity
7 ×#quantum
5 ×#graph
5 ×#multi
5 ×#polynomial
4 ×#matrix

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.