Proceedings of the 36th 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

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

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

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.

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.