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

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

13 ×#algorithm

11 ×#approximate

10 ×#problem

9 ×#on the

8 ×#quantum

7 ×#graph

6 ×#bound

5 ×#complexity

5 ×#proving

5 ×#query

11 ×#approximate

10 ×#problem

9 ×#on the

8 ×#quantum

7 ×#graph

6 ×#bound

5 ×#complexity

5 ×#proving

5 ×#query