F. Frances Yao, Eugene M. Luks
Proceedings of the 32nd Annual ACM Symposium on Theory of Computing
STOC, 2000.

@proceedings{STOC-2000,
	address       = "Portland, Oregon, USA",
	editor        = "F. Frances Yao and Eugene M. Luks",
	isbn          = "1-58113-184-4",
	publisher     = "{ACM}",
	title         = "{Proceedings of the 32nd Annual ACM Symposium on Theory of Computing}",
	year          = 2000,
}

Contents (85 items)

13 ×#algorithm
11 ×#approximate
10 ×#problem
9 ×#on the
8 ×#quantum
7 ×#graph
6 ×#bound
5 ×#complexity
5 ×#proving
5 ×#query

STOC-2000-ImpagliazzoSW #generative #pseudo

Extractors and pseudo-random generators with optimal seed length (RI, RS, AW), pp. 1–10.

STOC-2000-NaorRR #pseudo

Pseudo-random functions and factoring (MN, OR, AR), pp. 11–20.

STOC-2000-Gutierrez #equation #satisfiability

Satisfiability of equations in free groups is in PSPACE (CG), pp. 21–27.

STOC-2000-Achlioptas #bound #random #satisfiability

Setting 2 variables at a time yields a new lower bound for random 3-SAT (DA), pp. 28–37.

STOC-2000-CzumajS #algorithm #approach #problem #satisfiability #scheduling

A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems (AC, CS), pp. 38–47.

STOC-2000-GurvitsS #algorithm #approximate #polynomial

A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume (LG, AS), pp. 48–57.

STOC-2000-CarrV #random

Randomized metarounding (RDC, SV), pp. 58–62.

STOC-2000-Grohe #graph #morphism #testing

Isomorphism testing for embeddable graphs through definability (MG), pp. 63–72.

STOC-2000-KabanetsC #problem

Circuit minimization problem (VK, JyC), pp. 73–79.

STOC-2000-KatzT #on the #performance

On the efficiency of local decoding procedures for error-correcting codes (JK, LT), pp. 80–86.

STOC-2000-Istrail #3d #statistics

Statistical mechanics, three-dimensionality and NP-completeness: I. Universality of intracatability for the partition function of the Ising model across non-planar surfaces (SI), pp. 87–96.

STOC-2000-IwataFF #algorithm #combinator #polynomial

A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions (SI, LF, SF), pp. 97–106.

STOC-2000-FleischerI #algorithm

Improved algorithms for submodular function minimization and submodular flow (LF, SI), pp. 107–116.

STOC-2000-Vygen #algorithm #on the

On dual minimum cost flow algorithms (JV), pp. 117–125.

STOC-2000-PapadimitriouV #on the #problem

On the approximability of the traveling salesman problem (CHP, SV), pp. 126–133.

STOC-2000-FeigeHK #approximate

Approximating the domatic number (UF, MMH, GK), pp. 134–143.

STOC-2000-Srinivasan #clique

The value of strong inapproximability results for clique (AS), pp. 144–152.

STOC-2000-AdlerL #multi #performance #using

Compression using efficient multicasting (MA, FTL), pp. 153–162.

STOC-2000-Kleinberg #algorithm #perspective

The small-world phenomenon: an algorithmic perspective (JMK), pp. 163–170.

STOC-2000-AielloCL #graph #random

A random graph model for massive graphs (WA, FRKC, LL), pp. 171–180.

STOC-2000-GuruswamiS #algorithm

List decoding algorithms for certain concatenated codes (VG, MS), pp. 181–190.

STOC-2000-SamorodnitskyT #complexity #query

A PCP characterization of NP with optimal amortized query complexity (AS, LT), pp. 191–199.

STOC-2000-Vadhan #complexity #interactive #on the #proving

On transformation of interactive proofs that preserve the prover’s complexity (SPV), pp. 200–207.

STOC-2000-CsirikJKOSW #algorithm #on the

On the sum-of-squares algorithm for bin packing (JC, DSJ, CK, JBO, PWS, RRW), pp. 208–217.

STOC-2000-FeigenbaumPS #cost analysis #low cost

Sharing the cost of muliticast transmissions (JF, CHP, SS), pp. 218–227.

STOC-2000-KaoNT #optimisation #problem

The risk profile problem for stock portfolio optimization (MYK, AN, SRT), pp. 228–234.

STOC-2000-CanettiGGM

Resettable zero-knowledge (RC, OG, SG, SM), pp. 235–244.

STOC-2000-KatzY #encryption #probability #security

Complete characterization of security notions for probabilistic private-key encryption (JK, MY), pp. 245–254.

STOC-2000-CrescenzoSY #on the #proving

On zero-knowledge proofs (extended abstract): “from membership to decision” (GDC, KS, MY), pp. 255–264.

STOC-2000-Boneh #integer #using

Finding smooth integers in short intervals using CRT decoding (DB), pp. 265–272.

STOC-2000-EdelsbrunnerLMSTTUW

Smoothing and cleaning up slivers (HE, XYL, GLM, AS, DT, SHT, AÜ, NW), pp. 273–277.

STOC-2000-BuschHW

Hard-Potato routing (CB, MH, RW), pp. 278–285.

STOC-2000-AleksandrovMS #algorithm #approximate #geometry #problem

Approximation algorithms for geometric shortest path problems (LA, AM, JRS), pp. 286–295.

STOC-2000-EvenGS #approximate #graph

Improved approximations of crossings in graph drawings (GE, SG, BS), pp. 296–305.

STOC-2000-MotwaniPSV #decidability #on the #problem

On the decidability of accessibility problems (RM, RP, VAS, SV), pp. 306–315.

STOC-2000-Kilian #theorem

More general completeness theorems for secure two-party computation (JK), pp. 316–324.

STOC-2000-CramerDD #complexity #multi #on the

On the complexity of verifiable secret sharing and multiparty computation (RC, ID, SD), pp. 325–334.

STOC-2000-AnderssonT #bound #worst-case

Tight(er) worst-case bounds on dynamic searching and priority queues (AA, MT), pp. 335–342.

STOC-2000-Thorup #graph

Near-optimal fully-dynamic graph connectivity (MT), pp. 343–350.

STOC-2000-MahajanV #graph

A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (MM, KRV), pp. 351–357.

STOC-2000-AlekhnovichBRW #calculus #complexity

Space complexity in propositional calculus (MA, EBS, AAR, AW), pp. 358–367.

STOC-2000-MacielPW #principle #proving

A new proof of the weak pigeonhole principle (AM, TP, ARW), pp. 368–377.

STOC-2000-HarnikR #bound

Higher lower bounds on monotone size (DH, RR), pp. 378–387.

STOC-2000-BarkolR #bound #nearest neighbour #problem

Tighter bounds for nearest neighbor search and related problems in the cell probe model (OB, YR), pp. 388–396.

STOC-2000-GrossiV #array #string

Compressed suffix arrays and suffix trees with applications to text indexing and string matching (RG, JSV), pp. 397–406.

STOC-2000-ColeH #performance

Faster suffix tree construction with missing suffix links (RC, RH), pp. 407–415.

STOC-2000-MuthukrishnanS #approximate #comparison #nearest neighbour #sequence

Approximate nearest neighbors and sequence comparison with block operations (SM, SCS), pp. 416–424.

STOC-2000-LiMW #multi #polynomial

Near optimal multiple alignment within a band in polynomial time (ML, BM, LW), pp. 425–434.

STOC-2000-BlumKW #learning #problem #query #statistics

Noise-tolerant learning, the parity problem, and the statistical query model (AB, AK, HW), pp. 435–440.

STOC-2000-GoldsmithS #query

More theory revision with queries (JG, RHS), pp. 441–448.

STOC-2000-BuhrmanMRV #question

Are bitvectors optimal? (HB, PBM, JR, SV), pp. 449–458.

STOC-2000-RothemundW #complexity #self

The program-size complexity of self-assembled squares (PWKR, EW), pp. 459–468.

STOC-2000-ChenX #graph #query

Shortest path queries in planar graphs (DZC, JX), pp. 469–478.

STOC-2000-Reed #how #question

How tall is a tree? (BAR), pp. 479–483.

STOC-2000-FaginKKRRRST #random

Random walks with “back buttons” (RF, ARK, JMK, PR, SR, RR, MS, AT), pp. 484–493.

STOC-2000-FitziM #consistency

From partial consistency to global broadcast (MF, UMM), pp. 494–503.

STOC-2000-KempeKK #network #problem

Connectivity and inference problems for temporal networks (DK, JMK, AK), pp. 504–513.

STOC-2000-RasalaW #network #strict

Strictly non-blocking WDM cross-connects for heterogeneous networks (AR, GTW), pp. 514–523.

STOC-2000-FederMS #graph

Finding long paths and cycles in sparse Hamiltonian graphs (TF, RM, CSS), pp. 524–529.

STOC-2000-FeigeKN #approximate

Approximating the minimum bisection size (UF, RK, KN), pp. 530–536.

STOC-2000-KonemannR #algorithm #approximate #bound #matter

A matter of degree: improved approximation algorithms for degree-bounded minimum spanning trees (JK, RR), pp. 537–546.

STOC-2000-Schulman #clustering

Clustering for edge-cost minimization (LJS), pp. 547–555.

STOC-2000-Fortune #integer #matrix #symmetry

Exact computations of the inertia symmetric integer matrices (SF), pp. 556–564.

STOC-2000-OrlinSS #combinator #optimisation #precise

epsilon-optimization schemes and L-bit precision: alternative perspectives in combinatorial optimization (JBO, ASS, SS), pp. 565–572.

STOC-2000-OlshevskyS #confluence #matrix

Matrix-vector product for confluent Cauchy-like matrices with application to confluent rational interpolation (VO, MAS), pp. 573–581.

STOC-2000-CharikarFGKRS #query

Query strategies for priced information (MC, RF, VG, JMK, PR, AS), pp. 582–591.

STOC-2000-Seiden #algorithm #game studies #online #random

A guessing game and randomized online algorithms (SSS), pp. 592–601.

STOC-2000-FederMPOW #nondeterminism

Computing the median with uncertainty (TF, RM, RP, CO, JW), pp. 602–607.

STOC-2000-KitaevW #exponential #interactive #parallel #proving #quantum #simulation

Parallelization, amplification, and exponential time simulation of quantum interactive proof systems (AK, JW), pp. 608–617.

STOC-2000-Grover #agile #quantum

Rapid sampling though quantum computing (LKG), pp. 618–626.

STOC-2000-HallgrenRT #quantum #re-engineering #using

Normal subgroup reconstruction and quantum computation using group representations (SH, AR, ATS), pp. 627–635.

STOC-2000-Ambainis #bound #quantum

Quantum lower bounds by quantum arguments (AA), pp. 636–643.

STOC-2000-Klauck #communication #on the #probability #protocol #quantum

On quantum and probabilistic communication: Las Vegas and one-way protocols (HK), pp. 644–651.

STOC-2000-GuptaT #algorithm #approximate #classification #constant #problem

A constant factor approximation algorithm for a class of classification problems (AG, ÉT), pp. 652–658.

STOC-2000-KenyonSY #approximate #polynomial

Polynomial-time approximation scheme for data broadcast (CK, NS, NEY), pp. 659–666.

STOC-2000-Furer #approximate #matrix

Approximating permanents of complex matrices (MF), pp. 667–669.

STOC-2000-GoelMP #multi #online #throughput

Combining fairness with throughput: online routing with multiple objectives (AG, AM, SAP), pp. 670–679.

STOC-2000-BermanD #realtime #scheduling

Improvements in throughout maximization for real-time scheduling (PB, BD), pp. 680–687.

STOC-2000-DamMMS #fault tolerance #quantum #self #set

Self-testing of universal and fault-tolerant sets of quantum gates (WvD, FM, MM, MS), pp. 688–696.

STOC-2000-AmbainisSV

Computing with highly mixed states (AA, LJS, UVV), pp. 697–704.

STOC-2000-AharonovTVY #quantum

Quantum bit escrow (DA, ATS, UVV, ACCY), pp. 705–714.

STOC-2000-BihamBBMR #proving #quantum #security

A proof of the security of quantum key distribution (EB, MB, POB, TM, VPR), pp. 715–724.

STOC-2000-FiatM #algorithm

Better algorithms for unfair metrical task systems and applications (AF, MM), pp. 725–734.

STOC-2000-Bar-NoyBFNS #approach #approximate #resource management #scheduling

A unified approach to approximating resource allocation and scheduling (ABN, RBY, AF, JN, BS), pp. 735–744.

STOC-2000-BerenbrinkCSV

Balanced allocations: the heavily loaded case (PB, AC, AS, BV), pp. 745–754.