Cynthia Dwork
Proceedings of the 40th Annual ACM Symposium on Theory of Computing
STOC, 2008.

@proceedings{STOC-2008,
	address       = "Victoria, British Columbia, Canada",
	editor        = "Cynthia Dwork",
	isbn          = "978-1-60558-047-0",
	publisher     = "{ACM}",
	title         = "{Proceedings of the 40th Annual ACM Symposium on Theory of Computing}",
	year          = 2008,
}

Contents (85 items)

12 ×#bound
10 ×#algorithm
9 ×#graph
9 ×#problem
6 ×#complexity
5 ×#communication
5 ×#learning
5 ×#network
4 ×#approximate
4 ×#design

STOC-2008-Rao #bound #game studies #parallel

Parallel repetition in projection games and a concentration bound (AR), pp. 1–10.

STOC-2008-ManokaranNRS #metric #multi

Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling (RM, JN, PR, RS), pp. 11–20.

STOC-2008-AroraKKSTV #constraints #game studies #graph

Unique games on expanding constraint graphs are easy: extended abstract (SA, SK, AK, DS, MT, NKV), pp. 21–28.

STOC-2008-BodirskyK #complexity #constraints #problem

The complexity of temporal constraint satisfaction problems (MB, JK), pp. 29–38.

STOC-2008-Nandakumar #effectiveness #theorem

An effective ergodic theorem and some applications (SN), pp. 39–44.

STOC-2008-DasK #algorithm #linear #set

Algorithms for subset selection in linear regression (AD, DK), pp. 45–54.

STOC-2008-Rexford #internet

Rethinking internet routing (JR), pp. 55–56.

STOC-2008-LevinSZ #game studies

Interdomain routing and games (HL, MS, AZ), pp. 57–66.

STOC-2008-Vondrak #approximate #problem

Optimal approximation for the submodular welfare problem in the value oracle model (JV), pp. 67–74.

STOC-2008-HartlineR #design

Optimal mechanism design and money burning (JDH, TR), pp. 75–84.

STOC-2008-Sherstov #bound #communication #matrix #quantum

The pattern matrix method for lower bounds on quantum communication (AAS), pp. 85–94.

STOC-2008-Gavinsky #interactive #quantum

Classical interaction cannot replace a quantum message (DG), pp. 95–102.

STOC-2008-ReichardtS #algorithm #quantum

Span-program-based quantum algorithm for evaluating formulas (BR, RS), pp. 103–112.

STOC-2008-GoldwasserKR #interactive #proving

Delegating computation: interactive proofs for muggles (SG, YTK, GNR), pp. 113–122.

STOC-2008-JubaS #communication #semantics

Universal semantic communication I (BJ, MS), pp. 123–132.

STOC-2008-FortnowS

Infeasibility of instance compression and succinct PCPs for NP (LF, RS), pp. 133–142.

STOC-2008-GoldwasserGHKR #approach

A (de)constructive approach to program checking (SG, DG, AH, TK, GNR), pp. 143–152.

STOC-2008-FakcharoenpholL #algorithm #approximate #problem

An o(log2 k)-approximation algorithm for the k-vertex connected spanning subgraph problem (JF, BL), pp. 153–158.

STOC-2008-Thorup

Minimum k-way cuts via deterministic greedy tree packing (MT), pp. 159–166.

STOC-2008-ChakrabortyCK #design #network

Network design for vertex connectivity (TC, JC, SK), pp. 167–176.

STOC-2008-ChenLL #algorithm #feedback #parametricity #problem #set

A fixed-parameter algorithm for the directed feedback vertex set problem (JC, YL, SL, BO, IR), pp. 177–186.

STOC-2008-PeikertW

Lossy trapdoor functions and their applications (CP, BW), pp. 187–196.

STOC-2008-GentryPV #encryption

Trapdoors for hard lattices and new cryptographic constructions (CG, CP, VV), pp. 197–206.

STOC-2008-GamaN #difference

Finding short lattice vectors within mordell’s inequality (NG, PQN), pp. 207–216.

STOC-2008-AttiyaHW #bound #problem

Tight rmr lower bounds for mutual exclusion and other problems (HA, DH, PW), pp. 217–226.

STOC-2008-CoteMP #random

Randomized k-server on hierarchical binary trees (AC, AM, LJP), pp. 227–234.

STOC-2008-BansalBN #algorithm #random

Randomized competitive algorithms for generalized caching (NB, NB, JN), pp. 235–244.

STOC-2008-Raghavendra #algorithm #csp #question

Optimal algorithms and inapproximability results for every CSP? (PR), pp. 245–254.

STOC-2008-Racke #network

Optimal hierarchical decompositions for congestion minimization in networks (HR), pp. 255–264.

STOC-2008-GopalanKZ

List-decoding reed-muller codes over small fields (PG, ARK, DZ), pp. 265–274.

STOC-2008-DinurGKS #bound #morphism

Decodability of group homomorphisms beyond the johnson bound (ID, EG, SK, MS), pp. 275–284.

STOC-2008-Meir #combinator

Combinatorial construction of locally testable codes (OM), pp. 285–294.

STOC-2008-KleinbergT #network #social

Balanced outcomes in social exchange networks (JMK, ÉT), pp. 295–304.

STOC-2008-ChenGP #combinator

Pricing combinatorial markets for tournaments (YC, SG, DMP), pp. 305–314.

STOC-2008-ColeF #algorithm #problem

Fast-converging tatonnement algorithms for one-time and ongoing market problems (RC, LF), pp. 315–324.

STOC-2008-Ben-AroyaT #combinator #graph #using

A combinatorial construction of almost-ramanujan graphs using the zig-zag product (ABA, ATS), pp. 325–334.

STOC-2008-ODonnellW #algorithm #testing

An optimal sdp algorithm for max-cut, and equally optimal long code tests (RO, YW), pp. 335–344.

STOC-2008-KhotS #learning #on the

On hardness of learning intersection of two halfspaces (SK, RS), pp. 345–354.

STOC-2008-SkopalikV #nash

Inapproximability of pure nash equilibria (AS, BV), pp. 355–364.

STOC-2008-BorgsCIKMP #theorem

The myth of the folk theorem (CB, JTC, NI, ATK, VSM, CHP), pp. 365–372.

STOC-2008-BlumHLR

Regret minimization and the price of total anarchy (AB, MH, KL, AR), pp. 373–382.

STOC-2008-Valiant #symmetry #testing

Testing symmetric properties of distributions (PV), pp. 383–392.

STOC-2008-BenjaminiSS #graph

Every minor-closed property of sparse graphs is testable (IB, OS, AS), pp. 393–402.

STOC-2008-KaufmanS #algebra #testing

Algebraic property testing: the role of invariance (TK, MS), pp. 403–412.

STOC-2008-GordonHKL

Complete fairness in secure two-party computation (SDG, CH, JK, YL), pp. 413–422.

STOC-2008-KolN #game studies

Games for exchanging information (GK, MN), pp. 423–432.

STOC-2008-IshaiKOS #constant #encryption

Cryptography with constant computational overhead (YI, EK, RO, AS), pp. 433–442.

STOC-2008-GoyalOS

The vpn conjecture is true (NG, NO, FBS), pp. 443–450.

STOC-2008-DaitchS #algorithm #approximate #performance

Faster approximate lossy generalized flow via interior point algorithms (SID, DAS), pp. 451–460.

STOC-2008-OrecchiaSVV #clustering #graph #on the

On partitioning graphs via single commodity flows (LO, LJS, UVV, NKV), pp. 461–470.

STOC-2008-KawarabayashiM #graph #linear #morphism

Graph and map isomorphism and all polyhedral embeddings in linear time (KiK, BM), pp. 471–480.

STOC-2008-Umans #composition #performance #polynomial

Fast polynomial factorization and modular composition in small characteristic (CU), pp. 481–490.

STOC-2008-CaiCL #bound #exclamation #polynomial #problem

A quadratic lower bound for the permanent and determinant problem over any characteristic != 2 (JyC, XC, DL), pp. 491–498.

STOC-2008-DeKSS #composition #integer #multi #performance #using

Fast integer multiplication using modular arithmetic (AD, PPK, CS, RS), pp. 499–506.

STOC-2008-ShpilkaV #polynomial #testing

Read-once polynomial identity testing (AS, IV), pp. 507–516.

STOC-2008-ODonnellS #parametricity #problem

The chow parameters problem (RO, RAS), pp. 517–526.

STOC-2008-GopalanKK #learning

Agnostically learning decision trees (PG, ATK, ARK), pp. 527–536.

STOC-2008-DasguptaF #random

Random projection trees and low dimensional manifolds (SD, YF), pp. 537–546.

STOC-2008-LovettMS

Inverse conjecture for the gowers norm is false (SL, RM, AS), pp. 547–556.

STOC-2008-Lovett #generative #pseudo

Unconditional pseudorandom generators for low degree polynomials (SL), pp. 557–562.

STOC-2008-SpielmanS #effectiveness #graph

Graph sparsification by effective resistances (DAS, NS), pp. 563–568.

STOC-2008-ODonnell #analysis #topic

Some topics in analysis of boolean functions (RO), pp. 569–578.

STOC-2008-ImpagliazzoJKW #theorem

Uniform direct product theorems: simplified, optimized, and derandomized (RI, RJ, VK, AW), pp. 579–588.

STOC-2008-ShaltielV #proving

Hardness amplification proofs require majority (RS, EV), pp. 589–598.

STOC-2008-JainKN #bound #communication #complexity #theorem

Direct product theorems for classical communication complexity via subdistribution bounds: extended abstract (RJ, HK, AN), pp. 599–608.

STOC-2008-BlumLR #approach #database #learning #privacy

A learning theory approach to non-interactive database privacy (AB, KL, AR), pp. 609–618.

STOC-2008-Feldman #algorithm #learning

Evolvability from learning algorithms (VF), pp. 619–628.

STOC-2008-KalaiMV #learning #on the

On agnostic boosting and parity learning (ATK, YM, EV), pp. 629–638.

STOC-2008-Haussler #how

Computing how we became human (DH), pp. 639–640.

STOC-2008-ChakrabartiCM #bound #communication #robust

Robust lower bounds for communication and stream computation (AC, GC, AM), pp. 641–650.

STOC-2008-MironovNS #sketching

Sketching in adversarial environments (IM, MN, GS), pp. 651–660.

STOC-2008-BarkolIW #communication #replication

Communication in the presence of replication (OB, YI, EW), pp. 661–670.

STOC-2008-BalcanBV #clustering #framework #similarity

A discriminative framework for clustering via similarity functions (MFB, AB, SV), pp. 671–680.

STOC-2008-KleinbergSU #metric #multi

Multi-armed bandits in metric spaces (RK, AS, EU), pp. 681–690.

STOC-2008-AwerbuchK #distributed #linear #source code

Stateless distributed gradient descent for positive linear programs (BA, RK), pp. 691–700.

STOC-2008-NordstromH #towards

Towards an optimal separation of space and length in resolution (JN, JH), pp. 701–710.

STOC-2008-Raz #bound

Elusive functions and lower bounds for arithmetic circuits (RR), pp. 711–720.

STOC-2008-Rossman #clique #complexity #on the

On the constant-depth complexity of k-clique (BR), pp. 721–730.

STOC-2008-AaronsonW #complexity #named

Algebrization: a new barrier in complexity theory (SA, AW), pp. 731–740.

STOC-2008-DvirSY #bound #trade-off

Hardness-randomness tradeoffs for bounded depth arithmetic circuits (ZD, AS, AY), pp. 741–748.

STOC-2008-ChoiK #bound #complexity #graph #query

Optimal query complexity bounds for finding graphs (SSC, JHK), pp. 749–758.

STOC-2008-LauS #approximate #bound #design #network

Additive approximation for bounded degree survivable network design (LCL, MS), pp. 759–768.

STOC-2008-BansalKN #bound #design #network

Additive guarantees for degree bounded directed network design (NB, RK, VN), pp. 769–778.

STOC-2008-FriezeVV #graph #random

Logconcave random graphs (AMF, SV, JV), pp. 779–788.

STOC-2008-BartoKN #complexity #graph #morphism #problem

Graphs, polymorphisms and the complexity of homomorphism problems (LB, MK, TN), pp. 789–796.