Proceedings of the 32nd Annual ACM Symposium on Theory of Computing
BibSLEIGH corpus
BibSLEIGH tags
BibSLEIGH bundles
BibSLEIGH people
EDIT!
CC-BY
Open Knowledge
XHTML 1.0 W3C Rec
CSS 2.1 W3C CanRec
email twitter

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

TCS
DBLP
Scholar
Full names Links ISxN
@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, , 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.

Bibliography of Software Language Engineering in Generated Hypertext (BibSLEIGH) is created and maintained by Dr. Vadim Zaytsev.
Hosted as a part of SLEBOK on GitHub.