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

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

12 ×#bound

10 ×#algorithm

9 ×#graph

9 ×#problem

6 ×#complexity

5 ×#communication

5 ×#learning

5 ×#network

4 ×#approximate

4 ×#design

10 ×#algorithm

9 ×#graph

9 ×#problem

6 ×#complexity

5 ×#communication

5 ×#learning

5 ×#network

4 ×#approximate

4 ×#design