László Babai
Proceedings of the 36th Annual ACM Symposium on Theory of Computing
STOC, 2004.

@proceedings{STOC-2004,
	address       = "Chicago, Illinois, USA",
	editor        = "László Babai",
	isbn          = "1-58113-852-0",
	publisher     = "{ACM}",
	title         = "{Proceedings of the 36th Annual ACM Symposium on Theory of Computing}",
	year          = 2004,
}

Contents (73 items)

16 ×#algorithm
11 ×#graph
9 ×#bound
8 ×#approximate
7 ×#multi
7 ×#quantum
6 ×#linear
6 ×#problem
4 ×#clustering
4 ×#geometry

STOC-2004-Ben-SassonGHSV #proximity #robust

Robust pcps of proximity, shorter pcps and applications to coding (EBS, OG, PH, MS, SPV), pp. 1–10.

STOC-2004-HolmerinK #equation #linear #verification

A new PCP outer verifier with applications to homogeneous linear equations and max-bisection (JH, SK), pp. 11–20.

STOC-2004-ChuzhoyGHKKN #approximate #symmetry

Asymmetric k-center is log* n-hard to approximate (JC, SG, EH, SK, GK, JN), pp. 21–27.

STOC-2004-ChuzhoyN #scheduling

New hardness results for congestion minimization and machine scheduling (JC, JN), pp. 28–34.

STOC-2004-AlbersS #algorithm #on the #performance

On the performance of greedy algorithms in packet buffering (SA, MS), pp. 35–44.

STOC-2004-AwerbuchK #adaptation #distributed #feedback #geometry #learning

Adaptive routing with end-to-end feedback: distributed learning and geometric approaches (BA, RDK), pp. 45–53.

STOC-2004-MankuNW #lookahead #network #power of #random

Know thy neighbor’s neighbor: the power of lookahead in randomized P2P networks (GSM, MN, UW), pp. 54–63.

STOC-2004-AzarR #network

The zero-one principle for switching networks (YA, YR), pp. 64–71.

STOC-2004-AlonN #approximate #difference

Approximating the cut-norm via Grothendieck’s inequality (NA, AN), pp. 72–80.

STOC-2004-SpielmanT #algorithm #clustering #graph #linear

Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems (DAS, SHT), pp. 81–90.

STOC-2004-ColeGL #fault #taxonomy

Dictionary matching and indexing with errors and don’t cares (RC, LAG, ML), pp. 91–100.

STOC-2004-FinocchiI #fault #memory management #sorting

Sorting and searching in the presence of memory faults (without redundancy) (IF, GFI), pp. 101–110.

STOC-2004-Ambainis #algorithm #quantum

Quantum algorithms a decade after shor (AA), p. 111.

STOC-2004-Yao #graph #problem #quantum #sorting

Graph entropy and quantum sorting problems (ACCY), pp. 112–117.

STOC-2004-Aaronson #multi #quantum

Multilinear formulas and skepticism of quantum computing (SA), pp. 118–127.

STOC-2004-Bar-YossefJK #communication #complexity #exponential #quantum

Exponential separation of quantum and classical one-way communication complexity (ZBY, TSJ, IK), pp. 128–137.

STOC-2004-KortsarzN #algorithm #approximate #graph

Approximation algorithm for k-node connected subgraphs via critical graphs (GK, ZN), pp. 138–145.

STOC-2004-BienstockI #problem

Solving fractional packing problems in Oast(1/?) iterations (DB, GI), pp. 146–155.

STOC-2004-ChekuriKS #multi #problem

The all-or-nothing multicommodity flow problem (CC, SK, FBS), pp. 156–165.

STOC-2004-BansalBCM #algorithm #approximate

Approximation algorithms for deadline-TSP and vehicle routing with time-windows (NB, AB, SC, AM), pp. 166–174.

STOC-2004-CzumajS #metric

Estimating the weight of metric minimum spanning trees in sublinear-time (AC, CS), pp. 175–183.

STOC-2004-RodittyZ #algorithm #graph #linear #reachability

A fully dynamic reachability algorithm for directed graphs with an almost linear update time (LR, UZ), pp. 184–191.

STOC-2004-HealyVV #nondeterminism #using

Using nondeterminism to amplify hardness (AH, SPV, EV), pp. 192–201.

STOC-2004-AlurM #automaton

Visibly pushdown languages (RA, PM), pp. 202–211.

STOC-2004-ChenHKX #bound #linear #reduction

Linear FPT reductions and computational lower bounds (JC, XH, IAK, GX), pp. 212–221.

STOC-2004-AroraRV #clustering #geometry #graph

Expander flows, geometric embeddings and graph partitioning (SA, SR, UVV), pp. 222–231.

STOC-2004-Pass #bound #multi

Bounded-concurrent secure multi-party computation with a dishonest majority (RP), pp. 232–241.

STOC-2004-PrabhakaranS #security

New notions of security: achieving universal composability without trusted setup (MP, AS), pp. 242–251.

STOC-2004-HarnikNRR #perspective

Completeness in two-party secure computation: a computational view (DH, MN, OR, AR), pp. 252–261.

STOC-2004-IshaiKOS

Batch codes and their applications (YI, EK, RO, AS), pp. 262–271.

STOC-2004-KenyonRS #set

Low distortion maps between point sets (CK, YR, AS), pp. 272–280.

STOC-2004-Talwar #algorithm #metric

Bypassing the embedding: algorithms for low dimensional metrics (KT), pp. 281–290.

STOC-2004-Har-PeledM #clustering #on the

On coresets for k-means and k-median clustering (SHP, SM), pp. 291–300.

STOC-2004-BoissonnatCV #topic

Isotopic implicit surface meshing (JDB, DCS, GV), pp. 301–309.

STOC-2004-LovaszV

Hit-and-run from a corner (LL, SV), pp. 310–314.

STOC-2004-DunaganV #algorithm #linear #polynomial #source code

A simple polynomial-time rescaling algorithm for solving linear programs (JD, SV), pp. 315–320.

STOC-2004-ChlebusKS #worst-case

Collective asynchronous reading with polylogarithmic worst-case overhead (BSC, DRK, AAS), pp. 321–330.

STOC-2004-Elkin #approximate #bound #distributed #problem #trade-off

Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem (ME), pp. 331–340.

STOC-2004-Tardos #game studies #network

Network games (ÉT), pp. 341–342.

STOC-2004-BeierV #optimisation

Typical properties of winners and losers in discrete optimization (RB, BV), pp. 343–352.

STOC-2004-LeviRS #algorithm #problem

Primal-dual algorithms for deterministic inventory problems (RL, RR, DBS), pp. 353–362.

STOC-2004-ChekuriGKK #multi #scheduling

Multi-processor scheduling to minimize flow time with epsilon resource augmentation (CC, AG, SK, AK), pp. 363–372.

STOC-2004-Indyk #algorithm #data type #geometry #problem

Algorithms for dynamic geometric problems over data streams (PI), pp. 373–380.

STOC-2004-BatuKR #algorithm #sublinear #testing

Sublinear algorithms for testing monotone and unimodal distributions (TB, RK, RR), pp. 381–390.

STOC-2004-Fischer #graph #morphism #testing

The difficulty of testing for isomorphism against a graph that is given in advance (EF), pp. 391–397.

STOC-2004-CorreaG #approximate #graph #theorem

An approximate König’s theorem for edge-coloring weighted bipartite graphs (JRC, MXG), pp. 398–406.

STOC-2004-Gabow

Finding paths and cycles of superpolylogarithmic length (HNG), pp. 407–416.

STOC-2004-GuptaPRS #algorithm #approximate #optimisation #probability

Boosted sampling: approximation algorithms for stochastic optimization (AG, MP, RR, AS), pp. 417–426.

STOC-2004-ShpilkaW #morphism #testing

Derandomizing homomorphism testing in general groups (AS, AW), pp. 427–435.

STOC-2004-Guruswami #question

Better extractors for better codes? (VG), pp. 436–444.

STOC-2004-RozenmanSW #product line

A new family of Cayley expanders (?) (ER, AS, AW), pp. 445–454.

STOC-2004-Kelner #bound #clustering #graph

Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus (JAK), pp. 455–464.

STOC-2004-Aaronson04a #bound #quantum

Lower bounds for local search by quantum arguments (SA), pp. 465–474.

STOC-2004-BurgisserC #algebra #complexity #set

Counting complexity classes for numeric computations II: algebraic and semialgebraic sets (PB, FC), pp. 475–485.

STOC-2004-Ajtai #polynomial

A conjecture about polynomial time computable lattice-lattice functions (MA), pp. 486–493.

STOC-2004-SanthaS #quantum #query

Quantum and classical query complexities of local search are polynomially related (MS, MS), pp. 494–501.

STOC-2004-Reichardt #algorithm #optimisation #quantum

The quantum adiabatic optimization algorithm and local minima (BR), pp. 502–510.

STOC-2004-GargK #algorithm #equilibrium

Auction algorithms for market equilibrium (RG, SK), pp. 511–518.

STOC-2004-Devanur #algorithm #constraints #equilibrium

The spending constraint model for market equilibrium: algorithmic, existence and uniqueness results (NRD), pp. 519–528.

STOC-2004-ChenKLRSV #bound #confluence #theorem

(Almost) tight bounds and existence theorems for confluent flows (JC, RDK, LL, RR, RS, AV), pp. 529–538.

STOC-2004-Obata #approximate #multi #theorem

Approximate max-integral-flow/min-multicut theorems (KO), pp. 539–545.

STOC-2004-PatrascuD #bound

Lower bounds for dynamic connectivity (MP, EDD), pp. 546–553.

STOC-2004-AilonC #bound #linear #testing

Lower bounds for linear degeneracy testing (NA, BC), pp. 554–560.

STOC-2004-KempeM #algorithm #analysis #distributed

A decentralized algorithm for spectral analysis (DK, FM), pp. 561–568.

STOC-2004-KleinbergS #collaboration #modelling #using

Using mixture models for collaborative filtering (JMK, MS), pp. 569–578.

STOC-2004-Wigderson #question #why

Depth through breadth, or why should we attend talks in other areas? (AW), p. 579.

STOC-2004-GoelRK #geometry #graph #random

Sharp thresholds For monotone properties in random geometric graphs (AG, SR, BK), pp. 580–586.

STOC-2004-AchlioptasN #graph #random

The two possible values of the chromatic number of a random graph (DA, AN), pp. 587–593.

STOC-2004-Feige #bound #graph #independence #on the #random

On sums of independent random variables with unbounded variance, and estimating the average degree in a graph (UF), pp. 594–603.

STOC-2004-FabrikantPT #complexity #nash

The complexity of pure Nash equilibria (AF, CHP, KT), pp. 604–612.

STOC-2004-GairingLMM #nash #parallel #scheduling #strict

Computing Nash equilibria for scheduling on restricted parallel links (MG, TL, MM, BM), pp. 613–622.

STOC-2004-HalpernT #multi

Rational secret sharing and multiparty computation: extended abstract (JYH, VT), pp. 623–632.

STOC-2004-Raz #multi

Multi-linear formulas for permanent and determinant are of super-polynomial size (RR), pp. 633–641.