default search action
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
Regular Expressions with Counting: Weak versus Strong Determinism. 160-190 - Emanuele Viola:
The Complexity of Distributions. 191-218 - Zohar Shay Karnin, Yuval Rabani
Explicit Dimension Reduction and Its Applications. 219-249 - Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani
Local Versus Global Properties of Metric Spaces. 250-271 - Jesper Jansson
The Complexity of Inferring a Minimally Resolved Phylogenetic Supertree. 272-291
Volume 41, Number 2, 2012
- Mikkel Thorup
Tabulation-Based 5-Independent Hashing with Applications to Linear Probing and Second Moment Estimation. 293-331 - Cristopher Moore
Approximating the Permanent via Nonabelian Determinants. 332-355 - Daniel Stefankovic
A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions. 356-366 - Natan Rubin
Improved Bounds for Geometric Permutations. 367-390 - Nikhil Bansal, Niv Buchbinder
Randomized Competitive Algorithms for Generalized Caching. 391-414 - Danny Dolev
An Optimal Self-Stabilizing Firing Squad. 415-435 - Anna C. Gilbert, Yi Li
Approximate Sparse Recovery: Optimizing Time and Measurements. 436-453
Volume 41, Number 3, 2012
- Jen-Yeu Chen
Almost-Optimal Gossip-Based Aggregate Computation. 455-483 - Paul Beame
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
Area-Universal and Constrained Rectangular Layouts. 537-564 - Leah Epstein, Asaf Levin
Universal Sequencing on an Unreliable Machine. 565-586 - T.-H. Hubert Chan, Anupam Gupta:
Approximating TSP on Metrics with Bounded Global Growth. 587-617 - Darin Goldstein, Kojiro Kobayashi:
On Minimal-Time Solutions of Firing Squad Synchronization Problems for Networks. 618-669 - Liam Roditty, Uri Zwick:
Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs. 670-683 - Mordecai J. Golin
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
Online Set Packing. 728-746 - Tobias Friedrich, Martin Gairing, Thomas Sauerwald:
Quasirandom Load Balancing. 747-771 - Moni Naor, Gil Segev:
Public-Key Cryptosystems Resilient to Key Leakage. 772-814 - Marek Cygan
A Polynomial Algorithm for 3-Compatible Coloring and the Stubborn List Partition Problem (The Stubborn Problem Is Stubborn No More). 815-828 - Mark Cieliebak
Distributed Computing by Mobile Robots: Gathering. 829-879 - Eli Ben-Sasson, Swastik Kopparty:
Affine Dispersers from Subspace Polynomials. 880-914 - Anindya De, Christopher Portmann, Thomas Vidick
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
Shooting Permanent Rays among Disjoint Polygons in the Plane. 1005-1027 - Sevag Gharibian, Julia Kempe
Approximation Algorithms for QMA-Complete Problems. 1028-1050 - 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
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 - Jens Groth
Efficient Noninteractive Proof Systems for Bilinear Groups. 1193-1232 - 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
Distributed Verification and Hardness of Distributed Approximation. 1235-1265 - Ankur Moitra, Ryan O'Donnell:
Pareto Optimal Solutions for Smoothed Analysts. 1266-1284 - Nitin Saxena
Blackbox Identity Testing for Bounded Top-Fanin Depth-3 Circuits: The Field Doesn't Matter. 1285-1298 - Amit Chakrabarti
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
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
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
Agnostic Learning of Monomials by Halfspaces Is Hard. 1558-1590
- Nicole Immorlica, Jonathan Katz, Michael Mitzenmacher, Rocco A. Servedio
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 - Erin W. Chambers
Homology Flows, Cohomology Cuts. 1605-1634 - Alexandr Andoni, Krzysztof Onak:
Approximating Edit Distance in Near-Linear Time. 1635-1648 - 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 - Joshua D. Batson, Daniel A. Spielman
Twice-Ramanujan Sparsifiers. 1704-1721 - Russell Impagliazzo
New Direct-Product Testers and 2-Query PCPs. 1722-1768 - Luca Trevisan
Max Cut and the Smallest Eigenvalue. 1769-1786
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-12-26 00:54 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: