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)

13 ×#approximate
11 ×#algorithm
10 ×#on the
8 ×#graph
7 ×#problem
7 ×#random
5 ×#complexity
4 ×#bound
4 ×#metric
4 ×#multi

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.