## Harold N. Gabow, Ronald Fagin

*Proceedings of the 37th Annual ACM Symposium on Theory of Computing*

STOC, 2005.

@proceedings{STOC-2005, address = "Baltimore, Maryland, USA", editor = "Harold N. Gabow and Ronald Fagin", isbn = "1-58113-960-8", publisher = "{ACM}", title = "{Proceedings of the 37th Annual ACM Symposium on Theory of Computing}", year = 2005, }

### Contents (85 items)

- STOC-2005-BarakKSSW #graph #independence #simulation
- Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors (BB, GK, RS, BS, AW), pp. 1–10.
- STOC-2005-Raz #random
- Extractors with weak random seeds (RR), pp. 11–20.
- STOC-2005-Bogdanov #generative #pseudo
- Pseudorandom generators for low degree polynomials (AB), pp. 21–30.
- STOC-2005-Trevisan #on the
- On uniform amplification of hardness in NP (LT), pp. 31–38.
- STOC-2005-BriestKV #approximate #design
- Approximation techniques for utilitarian mechanism design (PB, PK, BV), pp. 39–48.
- STOC-2005-Papadimitriou #correlation #game studies #multi
- Computing correlated equilibria in multi-player games (CHP), pp. 49–56.
- STOC-2005-AwerbuchAE #scalability
- Large the price of routing unsplittable flow (BA, YA, AE), pp. 57–66.
- STOC-2005-ChristodoulouK #finite #game studies
- The price of anarchy of finite congestion games (GC, EK), pp. 67–73.
- STOC-2005-CodenottiMV #equilibrium
- Market equilibrium via the excess demand function (BC, BM, KRV), pp. 74–83.
- STOC-2005-Regev #encryption #fault #learning #linear #on the #random
- On lattices, learning with errors, random linear codes, and cryptography (OR), pp. 84–93.
- STOC-2005-Ajtai #representation
- Representing hard lattices with O(n log n) bits (MA), pp. 94–103.
- STOC-2005-MortensenPP #on the
- On dynamic range reporting in one dimension (CWM, RP, MP), pp. 104–111.
- STOC-2005-Thorup #worst-case
- Worst-case update times for fully-dynamic all-pairs shortest paths (MT), pp. 112–119.
- STOC-2005-Fortnow #legacy
- Beyond NP: the work and legacy of Larry Stockmeyer (LF), pp. 120–127.
- STOC-2005-AlonS #graph
- Every monotone graph property is testable (NA, AS), pp. 128–137.
- STOC-2005-FischerN #estimation #graph #testing
- Testing versus estimation of graph properties (EF, IN), pp. 138–146.
- STOC-2005-RubinfeldS #testing
- Testing monotone high-dimensional distributions (RR, RAS), pp. 147–156.
- STOC-2005-FriedlIS #performance #testing
- Efficient testing of groups (KF, GI, MS), pp. 157–166.
- STOC-2005-CheriyanV #algorithm #approximate #design #metric #network
- Approximation algorithms for network design with metric costs (JC, AV), pp. 167–175.
- STOC-2005-CharikarK #design #multi #network #on the
- On non-uniform multicommodity buy-at-bulk network design (MC, AK), pp. 176–182.
- STOC-2005-ChekuriKS #multi #problem
- Multicommodity flow, well-linked terminals, and routing problems (CC, SK, FBS), pp. 183–192.
- STOC-2005-HajiaghayiKLR #graph #random
- Oblivious routing in directed graphs with random demands (MTH, JHK, TL, HR), pp. 193–201.
- STOC-2005-IndykW #approximate #data type
- Optimal approximations of the frequency moments of data streams (PI, DPW), pp. 202–208.
- STOC-2005-FrahlingS #data type #geometry
- Coresets in dynamic geometric data streams (GF, CS), pp. 209–217.
- STOC-2005-OstrovskyR #distance #edit distance
- Low distortion embeddings for edit distance (RO, YR), pp. 218–224.
- STOC-2005-BadoiuCIS #metric
- Low-distortion embeddings of general metrics into the line (MB, JC, PI, AS), pp. 225–233.
- STOC-2005-BojanczykC #automaton #regular expression
- Tree-walking automata do not recognize all regular languages (MB, TC), pp. 234–243.
- STOC-2005-BenjaminiSW
- Balanced boolean functions that can be evaluated so that every input bit is unlikely to be read (IB, OS, DBW), pp. 244–250.
- STOC-2005-Alekhnovich #bound #random
- Lower bounds for k-DNF resolution on random 3-CNFs (MA), pp. 251–256.
- STOC-2005-KouckyPT #bound
- Bounded-depth circuits: separating wires from gates (MK, PP, DT), pp. 257–265.
- STOC-2005-Ben-SassonS #complexity #query
- Simple PCPs with poly-log rate and query complexity (EBS, MS), pp. 266–275.
- STOC-2005-AndrewsZ #problem
- Hardness of the undirected edge-disjoint paths problem (MA, LZ), pp. 276–283.
- STOC-2005-AndrewsZ05a #problem
- Hardness of the undirected congestion minimization problem (MA, LZ), pp. 284–293.
- STOC-2005-AlekhnovichAT #towards
- Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy (MA, SA, IT), pp. 294–303.
- STOC-2005-BasuPR #algebra #component #set
- Computing the first Betti number and the connected components of semi-algebraic sets (SB, RP, MFR), pp. 304–312.
- STOC-2005-Basu #algebra #algorithm #polynomial #set
- Polynomial time algorithm for computing the top Betti numbers of semi-algebraic sets defined by quadratic inequalities (SB), pp. 313–322.
- STOC-2005-ChenD #algorithm #approximate #fixpoint #on the
- On algorithms for discrete and approximate brouwer fixed points (XC, XD), pp. 323–330.
- STOC-2005-AzarE #parallel #programming #scheduling
- Convex programming for scheduling unrelated parallel machines (YA, AE), pp. 331–337.
- STOC-2005-SanghviV #complexity #random
- The round complexity of two-party random selection (SS, SPV), pp. 338–347.
- STOC-2005-FortnowST #semantics
- Hierarchies for semantic classes (LF, RS, LT), pp. 348–355.
- STOC-2005-KaplanKM #learning
- Learning with attribute costs (HK, EK, YM), pp. 356–365.
- STOC-2005-MosselR #learning #markov #modelling
- Learning nonsingular phylogenies and hidden Markov models (EM, SR), pp. 366–375.
- STOC-2005-Reingold
- Undirected ST-connectivity in log-space (OR), pp. 376–385.
- STOC-2005-JiaLNRS #approximate #set
- Universal approximations for TSP, Steiner tree, and set cover (LJ, GL, GN, RR, RS), pp. 386–395.
- STOC-2005-Garg #approximate #graph #problem
- Saving an epsilon: a 2-approximation for the k-MST problem in graphs (NG), pp. 396–402.
- STOC-2005-Morris
- The mixing time of the Thorp shuffle (BM), pp. 403–412.
- STOC-2005-CryanDR #approximate #bound
- Approximately counting integral flows and cell-bounded contingency tables (MC, MED, DR), pp. 413–422.
- STOC-2005-Vu #matrix #random
- Spectral norm of random matrices (VHV), pp. 423–430.
- STOC-2005-TaoV #matrix #on the #random
- On random pm 1 matrices: singularity and determinant (TT, VHV), pp. 431–440.
- STOC-2005-FlaxmanFV #algorithm #approximate #on the #performance #problem
- On the average case performance of some greedy approximation algorithms for the uncapacitated facility location problem (AF, AMF, JCV), pp. 441–449.
- STOC-2005-AdlerEM #probability #towards
- Towards asymptotic optimality in probabilistic packet marking (MA, JE, JM), pp. 450–459.
- STOC-2005-Shi #communication #complexity #metric #quantum
- Tensor norms and the classical communication complexity of nonlocal quantum measurement (YS), pp. 460–467.
- STOC-2005-Hallgren #algorithm #performance #quantum
- Fast quantum algorithms for computing the unit group and class group of a number field (SH), pp. 468–474.
- STOC-2005-SchmidtV #algorithm #polynomial #quantum
- Polynomial time quantum algorithm for the computation of the unit group of a number field (AS, UV), pp. 475–480.
- STOC-2005-Ben-OrH #performance #quantum
- Fast quantum byzantine agreement (MBO, AH), pp. 481–485.
- STOC-2005-AlonMMN #graph #polynomial
- Quadratic forms on graphs (NA, KM, YM, AN), pp. 486–493.
- STOC-2005-ElkinEST
- Lower-stretch spanning trees (ME, YE, DAS, SHT), pp. 494–503.
- STOC-2005-Goncalves #graph
- Edge partition of planar sraphs into two outerplanar graphs (DG0), pp. 504–512.
- STOC-2005-AhnHL
- Covert two-party computation (LvA, NJH, JL), pp. 513–522.
- STOC-2005-Wee #obfuscation #on the
- On obfuscating point functions (HW), pp. 523–532.
- STOC-2005-PassR #encryption #protocol
- New and improved constructions of non-malleable cryptographic protocols (RP, AR), pp. 533–542.
- STOC-2005-LepinksiMS #protocol
- Collusion-free protocols (ML, SM, AS), pp. 543–552.
- STOC-2005-AroraLN
- Euclidean distortion and the sparsest cut (SA, JRL, AN), pp. 553–562.
- STOC-2005-FeigeHL #algorithm #approximate
- Improved approximation algorithms for minimum-weight vertex separators (UF, MTH, JRL), pp. 563–572.
- STOC-2005-AgarwalCMM #algorithm #approximate #problem
- O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems (AA, MC, KM, YM), pp. 573–581.
- STOC-2005-NaorS #metric
- Balanced metric labeling (JN, RS), pp. 582–591.
- STOC-2005-DvirS #polynomial #query #testing
- Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits (ZD, AS), pp. 592–601.
- STOC-2005-GuruswamiR
- Limits to list decoding Reed-Solomon codes (VG, AR), pp. 602–609.
- STOC-2005-DobzinskiNS #algorithm #approximate #combinator
- Approximation algorithms for combinatorial auctions with complement-free bidders (SD, NN, MS), pp. 610–618.
- STOC-2005-AggarwalFGHIS
- Derandomization of auctions (GA, AF, AVG, JDH, NI, MS), pp. 619–625.
- STOC-2005-Trifonov #algorithm
- An O(log n log log n) space algorithm for undirected st-connectivity (VT), pp. 626–633.
- STOC-2005-Aaronson #complexity
- The complexity of agreement (SA), pp. 634–643.
- STOC-2005-KalaiLP #composition #concurrent #protocol
- Concurrent general composition of secure protocols in the timing model (YTK, YL, MP), pp. 644–653.
- STOC-2005-DodisS #fault
- Correcting errors without leaking partial information (YD, AS), pp. 654–663.
- STOC-2005-Holenstein
- Key agreement from weak bit agreement (TH), pp. 664–673.
- STOC-2005-CicaleseL #query
- A new strategy for querying priced information (FC, ESL), pp. 674–683.
- STOC-2005-AilonCN #clustering #consistency #ranking
- Aggregating inconsistent information: ranking and clustering (NA, MC, AN), pp. 684–693.
- STOC-2005-AchlioptasCKM #bias #graph #on the
- On the bias of traceroute sampling: or, power-law degree distributions in regular graphs (DA, AC, DK, CM), pp. 694–703.
- STOC-2005-Scheideler #exclamation #how
- How to spread adversarial nodes?: rotate! (CS), pp. 704–713.
- STOC-2005-GafniGP #adaptation #bound #complexity #set
- From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement (EG, RG, BP), pp. 714–722.
- STOC-2005-Jayanti #algorithm #multi
- An optimal multi-writer snapshot algorithm (PJ), pp. 723–732.
- STOC-2005-ChlebusK #memory management
- Cooperative asynchronous update of shared memory (BSC, DRK), pp. 733–739.
- STOC-2005-Hastad #approximate
- Every 2-CSP allows nontrivial approximation (JH), pp. 740–746.
- STOC-2005-VegaKKV #approximate #composition #constraints #problem
- Tensor decomposition and approximation schemes for constraint satisfaction problems (WFdlV, MK, RK, SV), pp. 747–754.
- STOC-2005-JansenS #on the
- On strip packing With rotations (KJ, RvS), pp. 755–761.

13 ×#approximate

11 ×#algorithm

10 ×#on the

8 ×#graph

7 ×#problem

7 ×#random

5 ×#complexity

4 ×#bound

4 ×#metric

4 ×#multi

11 ×#algorithm

10 ×#on the

8 ×#graph

7 ×#problem

7 ×#random

5 ×#complexity

4 ×#bound

4 ×#metric

4 ×#multi