## 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)

- 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.

16 ×#algorithm

11 ×#graph

9 ×#bound

8 ×#approximate

7 ×#multi

7 ×#quantum

6 ×#linear

6 ×#problem

4 ×#clustering

4 ×#geometry

11 ×#graph

9 ×#bound

8 ×#approximate

7 ×#multi

7 ×#quantum

6 ×#linear

6 ×#problem

4 ×#clustering

4 ×#geometry