@article{Devroye/12,
AUTHOR = {Devroye, Luc},
TITLE = {Simulating size-constrained Galton-Watson trees},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {1},
PAGES = {1-11},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/090766632},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Cohen-Feldman-Fiat-Kaplan-Olonetsky/12,
AUTHOR = {Cohen, Edith and Feldman, Michal and Fiat, Amos and Kaplan, Haim and Olonetsky, Svetlana},
TITLE = {Envy-free makespan approximation},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {1},
PAGES = {12-25},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/100801597},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Izumi-Souissi-Katayama-Inuzuka-Defago-Wada-Yamashita/12,
AUTHOR = {Izumi, Taisuke and Souissi, Samia and Katayama, Yoshiaki and Inuzuka, Nobuhiro and D{\'e}fago, Xavier and Wada, Koichi and Yamashita, Masafumi},
TITLE = {The gathering problem for two oblivious robots with unreliable compasses},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {1},
PAGES = {26-46},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/100797916},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Gibson-Kanade-Krohn-Pirwani-Varadarajan/12,
AUTHOR = {Gibson, Matt and Kanade, Gaurav and Krohn, Erik and Pirwani, Imran A. and Varadarajan, Kasturi},
TITLE = {On clustering to minimize the sum of radii},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {1},
PAGES = {47-60},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/100798144},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Gabow-Gallagher/12,
AUTHOR = {Gabow, Harold N. and Gallagher, Suzanne R.},
TITLE = {Iterated rounding algorithms for the smallest $k$-edge connected spanning subgraph},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {1},
PAGES = {61-103},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/080732572},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Agarwal-Arge-Kaplan-Molad-Tarjan-Yi/12,
AUTHOR = {Agarwal, Pankaj K. and Arge, Lars and Kaplan, Haim and Molad, Eyal and Tarjan, Robert Robert E. and Yi, Ke},
TITLE = {An optimal dynamic data structure for stabbing-semigroup queries},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {1},
PAGES = {104-127},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/10078791X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Pitassi-Segerlind/12,
AUTHOR = {Pitassi, Toniann and Segerlind, Nathan},
TITLE = {Exponential lower bounds and integrality gaps for tree-like Lov{\'a}sz-Schrijver procedures},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {1},
PAGES = {128-159},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/100816833},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Gelade-Gyssens-Martens/12,
AUTHOR = {Gelade, Wouter and Gyssens, Marc and Martens, Wim},
TITLE = {Regular expressions with counting: Weak versus strong determinism},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {1},
PAGES = {160-190},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/100814196},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Viola/12,
AUTHOR = {Viola, Emanuelle},
TITLE = {The complexity of distributions},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {1},
PAGES = {191-218},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/100814998},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Karnin-Rabani-Shpilka/12,
AUTHOR = {Karnin, Zohar S. and Rabani, Yuval and Shpilka, Amir},
TITLE = {Explicit dimension reduction and its applications},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {1},
PAGES = {219-249},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/110828812},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Arora-Lovasz-Newman-Rabani-Rabinovich-Vempala/12,
AUTHOR = {Arora, Sanjeev and Lov{\'a}sz, L{\'a}szl{\'o} and Newman, Ilan and Rabani, Yuval and Rabinovich, Yuri and Vempala, Santosch},
TITLE = {Local versus global properties of metric spaces},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {1},
PAGES = {250-271},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/090780304},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Jansson-Lemence-Lingas/12,
AUTHOR = {Jansson, Jesper and Lemence, Richard L. and Lingas, Andrzej},
TITLE = {The complexity of inferring a minimally resolved phylogenetic supertree},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {1},
PAGES = {272-291},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/100811489},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Thorup-Zhang/12,
AUTHOR = {Thorup, Mikkel and Zhang, Yin},
TITLE = {Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {2},
PAGES = {293-331},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/100800774},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Moore-Russell/12,
AUTHOR = {Moore, Cristopher and Russell, Alexander},
TITLE = {Approximating the permanent via Nonabelian determinants},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {2},
PAGES = {332-355},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/100806709},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Stefankovic-Vempala-Vigoda/12,
AUTHOR = {{\v{S}}tefankovi{\v{c}}, Daniel and Vempala, Santosh and Vigoda, Eric},
TITLE = {A deterministic polynomial-time approximation scheme for counting knapsack solutions},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {2},
PAGES = {356-366},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/11083976X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Rubin-Kaplan-Sharir/12,
AUTHOR = {Rubin, Natan and Kaplan, Haim and Sharir, Micha},
TITLE = {Improved bounds for geometric permutations},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {2},
PAGES = {367-390},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/110835918},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bansal-Buchbinder-Naor/12a,
AUTHOR = {Bansal, Nikhil and Buchbinder, Niv and Naor, Joseph (Seffi)},
TITLE = {Randomized competitive algorithms for generalized caching},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {2},
PAGES = {391-414},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/090779000},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Dolev-Hoch-Moses/12,
AUTHOR = {Dolev, Danny and Hoch, Ezra N. and Moses, Yoram},
TITLE = {An optimal self-stabilizing firing squad},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {2},
PAGES = {415-435},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/090776512},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Gilbert-Li-Porat-Strauss/12,
AUTHOR = {Gilbert, Anna C. and Li, Yi and Porat, Ely and Strauss, Martin J.},
TITLE = {Approximate sparse recovery: Optimizing time and measurements},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {2},
PAGES = {436-453},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/100816705},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chen-Pandurangan/12,
AUTHOR = {Chen, Jen-yeu and Pandurangan, Gopal},
TITLE = {Almost-optimal gossip-based aggregate computation},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {3},
PAGES = {455-483},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/100793104},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Beame-Huynh/12,
AUTHOR = {Beame, Paul and Huynh, Trinh},
TITLE = {Multiparty communication complexity and threshold circuit size of $\mathbf{AC}^0$},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {3},
PAGES = {484-518},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/100792779},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Ellen-Hendler-Shavit/12,
AUTHOR = {Ellen, Faith and Hendler, Danny and Shavit, Nir},
TITLE = {On the inherent sequentiality of concurrent objects},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {3},
PAGES = {519-536},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/08072646X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Eppstein-Mumford-Speckmann-Verbeek/12,
AUTHOR = {Eppstein, David and Mumford, Elena and Speckmann, Bettina and Verbeek, Kevin},
TITLE = {Area-universal and constrained rectangular layouts},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {3},
PAGES = {537-564},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/110834032},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Epstein-Levin-Marchetti-Spaccamela-Megow-Mestre-Skutella-Stougie/12,
AUTHOR = {Epstein, Leah and Levin, Asaf and Marchetti-Spaccamela, Alberto and Megow, Nicole and Mestre, Juli{\'a}n and Skutella, Martin and Stougie, Leen},
TITLE = {Universal sequencing on an unreliable machine},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {3},
PAGES = {565-586},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/110844210},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chan-Gupta/12,
AUTHOR = {Chan, T.-H. Hubert and Gupta, Anupam},
TITLE = {Approximating TSP on metrics with bounded global growth},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {3},
PAGES = {587-617},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/090749396},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Goldstein-Kobayashi/12,
AUTHOR = {Goldstein, Darin and Kobayashi, Kojiro},
TITLE = {On minimal-time solutions of firing squad synchronization problems for networks},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {3},
PAGES = {618-669},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/110821019},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Roditty-Zwick/12,
AUTHOR = {Roditty, Liam and Zwick, Uri},
TITLE = {Dynamic approximate all-pairs shortest paths in undirected graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {3},
PAGES = {670-683},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/090776573},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Golin-Mathieu-Young/12,
AUTHOR = {Golin, Mordecai J. and Mathieu, Claire and Young, Neal E.},
TITLE = {Huffman coding with letter costs: A linear-time approximation scheme},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {3},
PAGES = {684-713},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/100794092},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kirschmer-Voight/12,
AUTHOR = {Kirschmer, Markus and Voight, John},
TITLE = {Corrigendum to: ``Algorithmic enumeration of ideal classes for quaternion orders''},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {3},
PAGES = {714-714},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/120866063},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chepoi/12,
AUTHOR = {Chepoi, Victor},
TITLE = {Nice labeling problem for event structures: A counterexample},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {4},
PAGES = {715-727},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/110837760},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Emek-Halldorsson-Mansour-Patt-Shamir-Radhakrishnan-Rawitz/12,
AUTHOR = {Emek, Yuval and Halld{\'o}rsson, Magn{\'u}s M. and Mansour, Yishay and Patt-Shamir, Boaz and Radhakrishnan, Jaikumar and Rawitz, Dror},
TITLE = {Online set packing},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {4},
PAGES = {728-746},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/110820774},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Friedrich-Gairing-Sauerwald/12,
AUTHOR = {Friedrich, Tobias and Gairing, Martin and Sauerwald, Thomas},
TITLE = {Quasirandom load balancing},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {4},
PAGES = {747-771},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/100799216},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Naor-Segev/12,
AUTHOR = {Naor, Moni and Segev, Gil},
TITLE = {Public-key cryptosystems resilient to key leakage},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {4},
PAGES = {772-814},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/100813464},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Cygan-Pilipczuk-Pilipczuk-Wojtaszczyk/12b,
AUTHOR = {Cygan, Marek and Pilipczuk, Marcin and Pilipczuk, Michal and Wojtaszczyk, Jakub},
TITLE = {A polynomial algorithm for 3-compatible coloring and the stubborn list partition problem (the stubborn problem is stubborn no more)},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {4},
PAGES = {815-828},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/110826813},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Cieliebak-Flocchini-Prencipe-Santoro/12,
AUTHOR = {Cieliebak, Mark and Flocchini, Paola and Prencipe, Giuseppe and Santoro, Nicola},
TITLE = {Distributed computing by mobile robots: Gathering},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {4},
PAGES = {829-879},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/100796534},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Ben-Sasson-Kopparty/12,
AUTHOR = {Ben-Sasson, Eli and Kopparty, Swastik},
TITLE = {Affine dispersers from subspace polynomials},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {4},
PAGES = {880-914},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/110826254},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{De-Portmann-Vidick-Renner/12,
AUTHOR = {De, Anindya and Portmann, Christopher and Vidick, Thomas and Renner, Renato},
TITLE = {Trevisan's extractor in the presence of quantum side information},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {4},
PAGES = {915-940},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/100813683},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Loffler-Mulzer/12,
AUTHOR = {L{\"o}ffler, Maarten and Mulzer, Wolfgang},
TITLE = {Triangulating the square and squaring the triangle: Quadtrees and Delaunay triangulations are equivalent},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {4},
PAGES = {941-974},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/110825698},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Swamy-Shmoys/12,
AUTHOR = {Swamy, Chaitanya and Shmoys, David B.},
TITLE = {Sampling-based approximation algorithms for multistage stochastic optimization},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {4},
PAGES = {975-1004},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/100789269},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Ishaque-Speckmann-Toth/12,
AUTHOR = {Ishaque, Mashhood and Speckmann, Bettina and T{\'o}th, Csaba D.},
TITLE = {Shooting permanent rays among disjoint polygons in the plane},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {4},
PAGES = {1005-1027},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/100804310},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Gharibian-Kempe/12a,
AUTHOR = {Gharibian, Sevag and Kempe, Julia},
TITLE = {Approximation algorithms for QMA-complete problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {4},
PAGES = {1028-1050},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/110842272},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chandran-Gopalkrishnan-Reif/12,
AUTHOR = {Chandran, Harish and Gopalkrishnan, Nikhil and Reif, John},
TITLE = {Tile complexity of linear assemblies},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {4},
PAGES = {1051-1073},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/110822487},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Yoshida-Yamamoto-Ito/12,
AUTHOR = {Yoshida, Yuichi and Yamamoto, Masaki and Ito, Hiro},
TITLE = {Improved constant-time approximation algorithms for maximum matchings and other optimization problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {4},
PAGES = {1074-1093},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/110828691},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Fakcharoenphol-Laekhanukit/12,
AUTHOR = {Fakcharoenphol, Jittat and Laekhanukit, Bundit},
TITLE = {An $O(\log^2k)$-approximation algorithm for the $k$-vertex connected spanning subgraph problem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {5},
PAGES = {1095-1109},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/110855910},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Ailon-Avigdor-Elgrabli-Liberty-van_Zuylen/12,
AUTHOR = {Ailon, Nir and Avigdor-Elgrabli, Noa and Liberty, Edo and van Zuylen, Anke},
TITLE = {Improved approximation algorithms for bipartite correlation clustering},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {5},
PAGES = {1110-1121},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/110848712},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Sherstov/12,
AUTHOR = {Sherstov, Alexander A.},
TITLE = {Strong direct product theorems for quantum communication and query complexity},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {5},
PAGES = {1122-1165},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/110842661},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Englert-Westermann/12,
AUTHOR = {Englert, Matthias and Westermann, Matthias},
TITLE = {Considering suppressed packets improves buffer management in quality of service switches},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {5},
PAGES = {1166-1192},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/110856745},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Groth-Sahai/12,
AUTHOR = {Groth, Jens and Sahai, Amit},
TITLE = {Efficient noninteractive proof systems for bilinear groups},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {5},
PAGES = {1193-1232},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/080725386},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Sarma-Holzer-Kor-Korman-Nanongkai-Pandurangan-Peleg-Wattenhofer/12,
AUTHOR = {Sarma, Atish Das and Holzer, Stephan and Kor, Liah and Korman, Amos and Nanongkai, Danupon and Pandurangan, Gopal and Peleg, David and Wattenhofer, Roger},
TITLE = {Distributed verification and hardness of distributed approximation},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {5},
PAGES = {1235-1265},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/11085178X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Moitra-ODonnell/12,
AUTHOR = {Moitra, Aankur and O'Donnell, Ryan},
TITLE = {Pareto optimal solutions for smoothed analysts},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {5},
PAGES = {1266-1284},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/110851833},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Saxena-Seshadhri/12,
AUTHOR = {Saxena, Nitin and Seshadhri, C.},
TITLE = {Blackbox identity testing for bounded top-fanin depth-3 circuits: The field doesn't matter},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {5},
PAGES = {1285-1298},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/10848232},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chakrabarti-Regev/12,
AUTHOR = {Chakrabarti, Amit and Regev, Oded},
TITLE = {An optimal lower bound on the communication complexity of Gap-Hamming-Distance},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {5},
PAGES = {1299-1317},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/120861072},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Svensson/12,
AUTHOR = {Svensson, Ola},
TITLE = {Santa Claus schedules jobs on unrelated machines},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {5},
PAGES = {1318-1341},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/110851201},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Guerraoui-Hadzilacos-Kuznetsov-Toueg/12,
AUTHOR = {Guerraoui, Rachid and Hadzilacos, Vassos and Kuznetsov, Petr and Toueg, Sam},
TITLE = {The weakest failure detectors to solve quittable consensus and nonblocking atomic commit},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {6},
PAGES = {1343-1379},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/070698877},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bhattacharyya-Grigorescu-Jung-Raskhodnikova-Woodruff/12,
AUTHOR = {Bhattacharyya, Arnab and Grigorescu, Elena and Jung, Kyomin and Raskhodnikova, Sofya and Woodruff, David P.},
TITLE = {Transitive-closure spanners},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {6},
PAGES = {1380-1425},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/110826655},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Childs-Kothari/12,
AUTHOR = {Childs, Andrew M. and Kothari, Robin},
TITLE = {Quantum query complexity of minor-closed graph properties},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {6},
PAGES = {1426-1450},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/110833026},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Censor-Hillel-Shachnai/12,
AUTHOR = {Censor-Hillel, Keren and Shachnai, Hadas},
TITLE = {Fast information spreading in graphs with large weak conductance},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {6},
PAGES = {1451-1465},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/110845380},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Snir-Yuster/12,
AUTHOR = {Snir, Sagi and Yuster, Raphael},
TITLE = {Reconstructing approximate phylogenetic trees from quartet samples},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {6},
PAGES = {1466-1480},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/11086964X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Anderson-van_Melkebeek-Schweikardt-Segoufin/12,
AUTHOR = {Anderson, Matthew and van Melkebeek, Dieter and Schweikardt, Nicile and Segoufin, Luc},
TITLE = {Locality from circuit lower bounds},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {6},
PAGES = {1481-1523},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/110856873},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bourgain-Garaev-Konyagin-Shparlinski/12,
AUTHOR = {Bourgain, Jean and Garaev, Moubariz Z. and Konyagin, Sergei V. and Shparlinski, Igor E.},
TITLE = {On the hidden shifted power problem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {6},
PAGES = {1524-1557},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/110850414},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Feldman-Guruswami-Raghavendra-Wu/12,
AUTHOR = {Feldman, Vitaly and Guruswami, Venkatesan and Raghavendra, Prasad and Wu, Yi},
TITLE = {Agnostic learning of monomials by halfspaces is hard},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {6},
PAGES = {1558-1590},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/120865094},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Viola/12a,
AUTHOR = {Viola, Emanuele},
TITLE = {Bit-probe lower bounds for succinct data structures},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {6},
PAGES = {1593-1604},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/090766619},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chambers-Erickson-Nayyeri/12,
AUTHOR = {Chambers, Erin W. and Erickson, Jeff and Nayyeri, Amir},
TITLE = {Homology flows, cohomology cuts},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {6},
PAGES = {1605-1634},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/090766863},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Andoni-Onak/12,
AUTHOR = {Andoni, Alexandr and Onak, Krzysztof},
TITLE = {Approximating edit distance in near-linear time},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {6},
PAGES = {1635-1648},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/090767182},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Gupta-Krishnaswamy-Ravi/12,
AUTHOR = {Gupta, Aanupam and Krishnaswamy, Ravishankar and Ravi, R.},
TITLE = {Online and stochastic survivable network design},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {6},
PAGES = {1649-1672},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/09076725X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Ghosh-Roughgarden-Sundararajan/12,
AUTHOR = {Ghosh, Arpita and Roughgarden, Tim and Sundararajan, Mukund},
TITLE = {Universally utility-maximizing privacy mechanisms},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {6},
PAGES = {1673-1693},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/09076828X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Efremenko/12,
AUTHOR = {Efremenko, Klim},
TITLE = {3-query locally decodable codes of subexponential length},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {6},
PAGES = {1694-1703},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/090772721},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Batson-Spielman-Srivastava/12,
AUTHOR = {Batson, Joshua and Spielman, Daniel A. and Srivastava, Nikhil},
TITLE = {Twice-Ramanujan sparsifiers},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {6},
PAGES = {1704-1721},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/090772873},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Impagliazzo-Kabanets-Wigderson/12,
AUTHOR = {Impagliazzo, Russell and Kabanets, Valentine and Wigderson, Avi},
TITLE = {New direct-product testers and 2-query PCPs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {6},
PAGES = {1722-1768},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/09077299X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Trevisan/12,
AUTHOR = {Trevisan, Luca},
TITLE = {Max cut and the smallest eigenvalue},
JOURNAL = {SIAM J. Comput.},
VOLUME = {41},
NUMBER = {6},
PAGES = {1769-1786},
YEAR = {2012},
EDITOR = {Sudan, M.},
URL = {http://dx.doi.org/10.1137/090773714},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}