SIAM Journal on Computing, Volume 41
Volume 41, Number 1, 2012
Luc Devroye: Simulating Size-constrained Galton-Watson Trees. 1-11- Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan, Svetlana Olonetsky: Envy-Free Makespan Approximation. 12-25
- Taisuke Izumi, Samia Souissi, Yoshiaki Katayama, Nobuhiro Inuzuka, Xavier Défago, Koichi Wada, Masafumi Yamashita: The Gathering Problem for Two Oblivious Robots with Unreliable Compasses. 26-46
- Matt Gibson, Gaurav Kanade, Erik Krohn, Imran A. Pirwani, Kasturi R. Varadarajan: On Clustering to Minimize the Sum of Radii. 47-60
- Harold N. Gabow, Suzanne Gallagher: Iterated Rounding Algorithms for the Smallest k-Edge Connected Spanning Subgraph. 61-103
- Pankaj K. Agarwal, Lars Arge, Haim Kaplan, Eyal Molad, Robert Endre Tarjan, Ke Yi: An Optimal Dynamic Data Structure for Stabbing-Semigroup Queries. 104-127
- Toniann Pitassi, Nathan Segerlind: Exponential Lower Bounds and Integrality Gaps for Tree-Like Lovász-Schrijver Procedures. 128-159
- Wouter Gelade, Marc Gyssens, Wim Martens: Regular Expressions with Counting: Weak versus Strong Determinism. 160-190
- Emanuele Viola: The Complexity of Distributions. 191-218
- Zohar Shay Karnin, Yuval Rabani, Amir Shpilka: Explicit Dimension Reduction and Its Applications. 219-249
- Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh Vempala: Local Versus Global Properties of Metric Spaces. 250-271
- Jesper Jansson, Richard S. Lemence, Andrzej Lingas: The Complexity of Inferring a Minimally Resolved Phylogenetic Supertree. 272-291
Volume 41, Number 2, 2012
- Mikkel Thorup, Yin Zhang: Tabulation-Based 5-Independent Hashing with Applications to Linear Probing and Second Moment Estimation. 293-331
- Cristopher Moore, Alexander Russell: Approximating the Permanent via Nonabelian Determinants. 332-355
- Daniel Stefankovic, Santosh Vempala, Eric Vigoda: A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions. 356-366
- Nikhil Bansal, Niv Buchbinder, Joseph Naor: Randomized Competitive Algorithms for Generalized Caching. 391-414
- Anna C. Gilbert, Yi Li, Ely Porat, Martin J. Strauss: Approximate Sparse Recovery: Optimizing Time and Measurements. 436-453
Volume 41, Number 3, 2012
- Paul Beame, Trinh Huynh: Multiparty Communication Complexity and Threshold Circuit Size of sfAC0. 484-518
- Faith Ellen, Danny Hendler, Nir Shavit: On the Inherent Sequentiality of Concurrent Objects. 519-536
- David Eppstein, Elena Mumford, Bettina Speckmann, Kevin Verbeek: Area-Universal and Constrained Rectangular Layouts. 537-564
- Leah Epstein, Asaf Levin, Alberto Marchetti-Spaccamela, Nicole Megow, Julián Mestre, Martin Skutella, Leen Stougie: Universal Sequencing on an Unreliable Machine. 565-586
- Darin Goldstein, Kojiro Kobayashi: On Minimal-Time Solutions of Firing Squad Synchronization Problems for Networks. 618-669
- Mordecai J. Golin, Claire Mathieu, Neal E. Young: Huffman Coding with Letter Costs: A Linear-Time Approximation Scheme. 684-713
- Markus Kirschmer, John Voight: Corrigendum: Algorithmic Enumeration of Ideal Classes for Quaternion Orders. 714
Volume 41, Number 4, 2012
- Victor Chepoi: Nice Labeling Problem for Event Structures: A Counterexample. 715-727
- Yuval Emek, Magnús M. Halldórsson, Yishay Mansour, Boaz Patt-Shamir, Jaikumar Radhakrishnan, Dror Rawitz: Online Set Packing. 728-746
- Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: A Polynomial Algorithm for 3-Compatible Coloring and the Stubborn List Partition Problem (The Stubborn Problem Is Stubborn No More). 815-828
- Mark Cieliebak, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro: Distributed Computing by Mobile Robots: Gathering. 829-879
- Anindya De, Christopher Portmann, Thomas Vidick, Renato Renner: Trevisan's Extractor in the Presence of Quantum Side Information. 915-940
- Maarten Löffler, Wolfgang Mulzer: Triangulating the Square and Squaring the Triangle: Quadtrees and Delaunay Triangulations are Equivalent. 941-974
- Chaitanya Swamy, David B. Shmoys: Sampling-Based Approximation Algorithms for Multistage Stochastic Optimization. 975-1004
- Mashhood Ishaque, Bettina Speckmann, Csaba D. Tóth: Shooting Permanent Rays among Disjoint Polygons in the Plane. 1005-1027
- Harish Chandran, Nikhil Gopalkrishnan, John H. Reif: Tile Complexity of Linear Assemblies. 1051-1073
- Yuichi Yoshida, Masaki Yamamoto, Hiro Ito: Improved Constant-Time Approximation Algorithms for Maximum Matchings and Other Optimization Problems. 1074-1093
Volume 41, Number 5, 2012
- Jittat Fakcharoenphol, Bundit Laekhanukit: An O(log2k)-Approximation Algorithm for the k-Vertex Connected Spanning Subgraph Problem. 1095-1109
- Nir Ailon, Noa Avigdor-Elgrabli, Edo Liberty, Anke van Zuylen: Improved Approximation Algorithms for Bipartite Correlation Clustering. 1110-1121
- Alexander A. Sherstov: Strong Direct Product Theorems for Quantum Communication and Query Complexity. 1122-1165
- Matthias Englert, Matthias Westermann: Considering Suppressed Packets Improves Buffer Management in Quality of Service Switches. 1166-1192
- Kousha Etessami, Dieter van Melkebeek, Seth Pettie, John Watrous, Salil P. Vadhan: Special Section on the Forty-Third Annual ACM Symposium on Theory of Computing (STOC 2011). 1233-1234
- Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, Roger Wattenhofer: Distributed Verification and Hardness of Distributed Approximation. 1235-1265
- Nitin Saxena, C. Seshadhri: Blackbox Identity Testing for Bounded Top-Fanin Depth-3 Circuits: The Field Doesn't Matter. 1285-1298
- Amit Chakrabarti, Oded Regev: An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance. 1299-1317
- Ola Svensson: Santa Claus Schedules Jobs on Unrelated Machines. 1318-1341
Volume 41, Number 6, 2012
- Rachid Guerraoui, Vassos Hadzilacos, Petr Kuznetsov, Sam Toueg: The Weakest Failure Detectors to Solve Quittable Consensus and Nonblocking Atomic Commit. 1343-1379
- Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff: Transitive-Closure Spanners. 1380-1425
- Andrew M. Childs, Robin Kothari: Quantum Query Complexity of Minor-Closed Graph Properties. 1426-1450
- Keren Censor-Hillel, Hadas Shachnai: Fast Information Spreading in Graphs with Large Weak Conductance. 1451-1465
- Sagi Snir, Raphael Yuster: Reconstructing Approximate Phylogenetic Trees from Quartet Samples. 1466-1480
- Matthew Anderson, Dieter van Melkebeek, Nicole Schweikardt, Luc Segoufin: Locality from Circuit Lower Bounds. 1481-1523
- Jean Bourgain, Moubariz Z. Garaev, Sergei Konyagin, Igor E. Shparlinski: On the Hidden Shifted Power Problem. 1524-1557
- Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu: Agnostic Learning of Monomials by Halfspaces Is Hard. 1558-1590
- Nicole Immorlica, Jonathan Katz, Michael Mitzenmacher, Rocco A. Servedio, Chris Umans: Special Section on the Forty-First Annual ACM Symposium on Theory of Computing (STOC 2009). 1591-1592
- Emanuele Viola: Bit-Probe Lower Bounds for Succinct Data Structures. 1593-1604
- Anupam Gupta, Ravishankar Krishnaswamy, R. Ravi: Online and Stochastic Survivable Network Design. 1649-1672
- Arpita Ghosh, Tim Roughgarden, Mukund Sundararajan: Universally Utility-maximizing Privacy Mechanisms. 1673-1693
- Klim Efremenko: 3-Query Locally Decodable Codes of Subexponential Length. 1694-1703
- Russell Impagliazzo, Valentine Kabanets, Avi Wigderson: New Direct-Product Testers and 2-Query PCPs. 1722-1768
- Luca Trevisan: Max Cut and the Smallest Eigenvalue. 1769-1786
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-18T211851 by the dblp team