SIAM Journal on Computing, Volume 39

Volume 39, Number 1, 2009

• Scott Aaronson, Sudipto Guha, Jon M. Kleinberg, Frank McSherry, Dieter van Melkebeek, Amit Sahai:
  Special Issue On The Thirty-Eighth Annual ACM Symposium On Theory Of Computing (STOC 2006).
  
• Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf:
  Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity. 1-24
  
• John Watrous:
  Zero-Knowledge against Quantum Attacks. 25-58
  
• Jakob Nordström:
  Narrow Proofs May Be Spacious: Separating Space and Width in Resolution. 59-121
  
• Uriel Feige:
  On Maximizing Welfare When Utility Functions Are Subadditive. 122-142
  
• Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira:
  A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity. 143-167
  
• Anup Rao:
  Extractors for a Constant Number of Polynomially Small Min-Entropy Independent Sources. 168-194
  
• Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou:
  The Complexity of Computing a Nash Equilibrium. 195-259
  
• Dimitris Achlioptas, Federico Ricci-Tersenghi:
  Random Formulas Have Frozen Variables. 260-280
  
• Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd:
  Edge-Disjoint Paths in Planar Graphs with Constant Congestion. 281-301
  
• Nir Ailon, Bernard Chazelle:
  The Fast Johnson--Lindenstrauss Transform and Approximate Nearest Neighbors. 302-322
  
• Alex Samorodnitsky, Luca Trevisan:
  Gowers Uniformity, Influence of Variables, and PCPs. 323-360
  

Volume 39, Number 2, 2009

• Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph Naor:
  The Online Set Cover Problem. 361-370
  
• Howard J. Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani:
  On Earthmover Distance, Metric Labeling, and 0-Extension. 371-387
  
• Igor Semaev:
  Sparse Algebraic Equations over Finite Fields. 388-409
  
• Andreas Maletti, Jonathan Graehl, Mark Hopkins, Kevin Knight:
  The Power of Extended Top-Down Tree Transducers. 410-430
  
• Artur Czumaj, Andrzej Lingas:
  Finding a Heaviest Vertex-Weighted Triangle Is not Harder than Matrix Multiplication. 431-444
  
• Zvi Lotker, Boaz Patt-Shamir, Adi Rosén:
  Distributed Approximate Matching. 445-460
  
• Sven Koenig, Joseph S. B. Mitchell, Apurva Mudgal, Craig A. Tovey:
  A Near-Tight Approximation Algorithm for the Robot Localization Problem. 461-490
  
• Or Meir:
  Combinatorial Construction of Locally Testable Codes. 491-544
  
• Matthew Andrew, Ashwin Nayak, Rajmohan Rajaraman:
  Special Section on Foundations of Computer Science. 545
  
• Andreas Björklund, Thore Husfeldt, Mikko Koivisto:
  Set Partitioning via Inclusion-Exclusion. 546-563
  
• Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets:
  Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification. 564-605
  
• Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami:
  On Agnostic Learning of Parities, Monomials, and Halfspaces. 606-645
  
• Roman Vershynin:
  Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method. 646-678
  
• Nicholas J. A. Harvey:
  Algebraic Algorithms for Matching and Matroid Problems. 679-702
  
• Timothy M. Chan, Mihai Patrascu:
  Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time. 703-729
  
• Mihai Patrascu, Mikkel Thorup:
  Higher Lower Bounds for Near-Neighbor and Further Rich Problems. 730-741
  
• Venkatesan Guruswami, Prasad Raghavendra:
  Hardness of Learning Halfspaces with Noise. 742-765
  
• David Arthur, Sergei Vassilvitskii:
  Worst-Case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-Means Method. 766-782
  

Volume 39, Number 3, 2009

• Kevin L. Chang, Ravi Kannan:
  Pass-Efficient Algorithms for Learning Mixtures of Uniform Distributions. 783-812
  
• Sofya Raskhodnikova, Dana Ron, Amir Shpilka, Adam Smith:
  Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem. 813-842
  
• Irit Dinur, Elchanan Mossel, Oded Regev:
  Conditional Hardness for Approximate Coloring. 843-873
  
• Phong Q. Nguyen, Damien Stehlé:
  An LLL Algorithm with Quadratic Complexity. 874-903
  
• Artur Czumaj, Christian Sohler:
  Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time. 904-922
  
• Ke Chen:
  On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications. 923-947
  
• Shengyu Zhang:
  Tight Bounds for Randomized and Quantum Local Search. 948-977
  
• Eric Allender, Vladlen Koltun, Maxim Sviridenko:
  Special Section On The Thirty-Ninth Annual ACM Symposium On Theory Of Computing (STOC 2007). 978
  
• Martin Fürer:
  Faster Integer Multiplication. 979-1005
  
• Ronen Shaltiel, Christopher Umans:
  Low-End Uniform Hardness versus Randomness Tradeoffs for AM. 1006-1037
  
• Rahul Santhanam:
  Circuit Lower Bounds for Merlin--Arthur Classes. 1038-1061
  
• Lap Chi Lau, Joseph Naor, Mohammad R. Salavatipour, Mohit Singh:
  Survivable Network Design with Degree or Order Constraints. 1062-1087
  
• Sham M. Kakade, Adam Tauman Kalai, Katrina Ligett:
  Playing Games with Approximation Algorithms. 1088-1106
  
• Anna Pagh, Rasmus Pagh, Milan Ruzic:
  Linear Probing with Constant Independence. 1107-1120
  
• Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai:
  Zero-Knowledge Proofs from Secure Multiparty Computation. 1121-1152
  
• Iftach Haitner, Minh-Huyen Nguyen, Shien Jin Ong, Omer Reingold, Salil P. Vadhan:
  Statistically Hiding Commitments and Statistical Zero-Knowledge Arguments from Any One-Way Function. 1153-1218
  

Volume 39, Number 4, 2009

• Mohammad Ali Abam, Mark de Berg, Bettina Speckmann:
  Kinetic kd-Trees and Longest-Side kd-Trees. 1219-1232
  
• Andrei Z. Broder, Adam Kirsch, Ravi Kumar, Michael Mitzenmacher, Eli Upfal, Sergei Vassilvitskii:
  The Hiring Problem and Lake Wobegon Strategies. 1233-1255
  
• Nikhil Bansal, Alberto Caprara, Maxim Sviridenko:
  A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing. 1256-1278
  
• Zeev Dvir, Amir Shpilka, Amir Yehudayoff:
  Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits. 1279-1293
  
• Nikhil Bansal, Kirk Pruhs, Clifford Stein:
  Speed Scaling for Weighted Flow Time. 1294-1308
  
• Graham Cormode, Srikanta Tirthapura, Bojian Xu:
  Time-decaying Sketches for Robust Aggregation of Sensor Data. 1309-1339
  
• Ilias Diakonikolas, Mihalis Yannakakis:
  Small Approximate Pareto Sets for Biobjective Shortest Paths and Other Problems. 1340-1371
  
• Liad Blumrosen, Noam Nisan:
  On the Computational Power of Demand Queries. 1372-1391
  
• Klaus Jansen:
  Parameterized Approximation Scheme for the Multiple Knapsack Problem. 1392-1412
  
• Nikhil Bansal, Rohit Khandekar, Viswanath Nagarajan:
  Additive Guarantees for Degree-Bounded Directed Network Design. 1413-1431
  
• Bin Ma, Xiaoming Sun:
  More Efficient Algorithms for Closest String and Substring Problems. 1432-1443
  
• Amihood Amir, Tzvika Hartman, Oren Kapah, Avivit Levy, Ely Porat:
  On the Cost of Interchange Rearrangement in Strings. 1444-1461
  
• Sergey Bravyi, Barbara M. Terhal:
  Complexity of Stoquastic Frustration-Free Hamiltonians. 1462-1485
  
• Wim Martens, Frank Neven, Thomas Schwentick:
  Complexity of Decision Problems for XML Schemas and Chain Regular Expressions. 1486-1530
  
• Libor Barto, Marcin Kozik:
  Congruence Distributivity Implies Bounded Width. 1531-1542
  
• Adam Kirsch, Michael Mitzenmacher, Udi Wieder:
  More Robust Hashing: Cuckoo Hashing with a Stash. 1543-1561
  
• Oded Regev, Ben Toner:
  Simulating Quantum Correlations with Finite Communication. 1562-1580
  
• Rebecca Schulman, Erik Winfree:
  Programmable Control of Nucleation for Algorithmic Self-Assembly. 1581-1616
  
• Claire Kenyon, Yuval Rabani, Alistair Sinclair:
  Low Distortion Maps Between Point Sets. 1617-1636
  

Volume 39, Number 4, 2010

• Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson:
  Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized. 1637-1665
  

Volume 39, Number 5, 2010

• Danny Harnik, Moni Naor:
  On the Compressibility of NP Instances and Cryptographic Applications. 1667-1713
  
• Markus Kirschmer, John Voight:
  Algorithmic Enumeration of Ideal Classes for Quaternion Orders. 1714-1747
  
• Sanjeev Arora, Elad Hazan, Satyen Kale:
  O(sqrt(log(n)) Approximation to SPARSEST CUT in Õ(n²) Time. 1748-1771
  
• Chandra Chekuri, Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour:
  Approximation Algorithms for Nonuniform Buy-at-Bulk Network Design. 1772-1798
  
• Ho-Lin Chen, Tim Roughgarden, Gregory Valiant:
  Designing Network Protocols for Good Equilibria. 1799-1832
  
• Alexander A. Razborov, Alexander A. Sherstov:
  The Sign-Rank of AC⁰. 1833-1855
  
• Satish Rao, Shuheng Zhou:
  Edge Disjoint Paths in Moderately Connected Graphs. 1856-1887
  
• Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, Yajun Wang:
  Querying Approximate Shortest Paths in Anisotropic Regions. 1888-1918
  
• Amit Chakrabarti, Oded Regev:
  An Optimal Randomized Cell Probe Lower Bound for Approximate Nearest Neighbor Searching. 1919-1940
  
• Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh:
  Intractability of Clique-Width Parameterizations. 1941-1956
  
• Artur Czumaj, Piotr Krysta, Berthold Vöcking:
  Selfish Traffic Allocation for Server Farms. 1957-1987
  
• Tali Kaufman, Simon Litsyn, Ning Xie:
  Breaking the Epsilon-Soundness Bound of the Linearity Test over GF(2). 1988-2003
  
• Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio:
  Testing Halfspaces. 2004-2047
  
• Edith Cohen, Haim Kaplan, Tova Milo:
  Labeling Dynamic XML Trees. 2048-2074
  
• Timothy M. Chan:
  More Algorithms for All-Pairs Shortest Paths in Weighted Graphs. 2075-2089
  
• Eyal Kushilevitz, Yehuda Lindell, Tal Rabin:
  Information-Theoretically Secure Protocols and Security under Composition. 2090-2112
  

Volume 39, Number 6, 2010

• Vladimir Braverman, Rafail Ostrovsky:
  Effective Computations on Sliding Windows. 2113-2131
  
• Iyad A. Kanj, Ljubomir Perkovic, Ge Xia:
  On Spanners and Lightweight Spanners of Geometric Graphs. 2132-2161
  
• Gianluca De Marco:
  Distributed Broadcast in Unknown Radio Networks. 2162-2175
  
• Elchanan Mossel, Sébastien Roch:
  Submodularity of Influence in Social Networks: From Local to Global. 2176-2188
  
• Deeparnab Chakrabarty, Gagan Goel:
  On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP. 2189-2211
  
• Jaroslaw Byrka, Karen Aardal:
  An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem. 2212-2231
  
• Flavio Chierichetti, Andrea Vattani:
  The Local Nature of List Colorings for Graphs of High Girth. 2232-2250
  
• Eldar Fischer, Frédéric Magniez, Michel de Rougemont:
  Approximate Satisfiability and Equivalence. 2251-2281
  
• Javier Esparza, Stefan Kiefer, Michael Luttenberger:
  Computing the Least Fixed Point of Positive Polynomial Systems. 2282-2335
  
• Noga Alon, Amin Coja-Oghlan, Hiêp Hàn, Mihyun Kang, Vojtech Rödl, Mathias Schacht:
  Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions. 2336-2362
  
• Liam Roditty:
  On the k Shortest Simple Paths Problem in Weighted Directed Graphs. 2363-2376
  
• Cristopher Moore, Alexander Russell, Piotr Sniady:
  On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism. 2377-2396
  
• James R. Lee, Christopher Umans:
  Special Section On Foundations of Computer Science. 2397
  
• Alexandr Andoni, Robert Krauthgamer:
  The Computational Hardness of Estimating Edit Distance. 2398-2429
  
• Per Austrin:
  Towards Sharp Inapproximability for Any 2-CSP. 2430-2463
  
• Andrej Bogdanov, Emanuele Viola:
  Pseudorandom Bits for Polynomials. 2464-2486
  
• Moses Charikar, Konstantin Makarychev, Yury Makarychev:
  Local Global Tradeoffs in Metric Embeddings. 2487-2512
  
• Andris Ambainis, Andrew M. Childs, Ben Reichardt, Robert Spalek, Shengyu Zhang:
  Any AND-OR Formula of Size N Can Be Evaluated in Time N^1/2+o(1) on a Quantum Computer. 2513-2530
  
• Kousha Etessami, Mihalis Yannakakis:
  On the Complexity of Nash Equilibria and Other Fixed Points. 2531-2597
  
• Parikshit Gopalan, Subhash Khot, Rishi Saket:
  Hardness of Reconstructing Multivariate Polynomials over Finite Fields. 2598-2621
  
• Philipp Hertel, Toniann Pitassi:
  The PSPACE-Completeness of Black-White Pebbling. 2622-2682
  

Volume 39, Number 7, 2010

• Mary Cryan, Martin E. Dyer, Dana Randall:
  Approximately Counting Integral Flows and Cell-Bounded Contingency Tables. 2683-2703
  
• Boris Aronov, Micha Sharir:
  Approximate Halfspace Range Counting. 2704-2725
  
• Wojciech M. Golab, Danny Hendler, Philipp Woelfel:
  An O(1) RMRs Leader Election Algorithm. 2726-2760
  
• Oded Goldreich, Shafi Goldwasser, Asaf Nussboim:
  On the Implementation of Huge Random Objects. 2761-2822
  
• Amin Coja-Oghlan:
  A Better Algorithm for Random k-SAT. 2823-2864
  
• Surender Baswana, Telikepalli Kavitha:
  Faster Algorithms for All-pairs Approximate Shortest Paths in Undirected Graphs. 2865-2896
  
• Michael E. Saks, C. Seshadhri:
  Local Monotonicity Reconstruction. 2897-2926
  
• Jean Cardinal, Samuel Fiorini, Gwenaël Joret, Raphaël M. Jungers, J. Ian Munro:
  An Efficient Algorithm for Partial Order Production. 2927-2940
  
• Akinori Kawachi, Tomoyuki Yamakami:
  Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding. 2941-2969
  
• Arash Asadpour, Amin Saberi:
  An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods. 2970-2989
  
• Marc J. van Kreveld, Maarten Löffler, Joseph S. B. Mitchell:
  Preprocessing Imprecise Points and Splitting Triangulations. 2990-3000
  
• Zeev Nutov:
  Approximating Steiner Networks with Node-Weights. 3001-3022
  
• Pawel M. Idziak, Petar Markovic, Ralph McKenzie, Matthew Valeriote, Ross Willard:
  Tractability and Learnability Arising from Algebras with Few Subpowers. 3023-3037
  
• Julián Mestre:
  Adaptive Local Ratio. 3038-3057
  
• Alon Rosen, Gil Segev:
  Chosen-Ciphertext Security via Correlated Products. 3058-3088
  
• Itai Arad, Zeph Landau:
  Quantum Computation and the Evaluation of Tensor Networks. 3089-3121
  
• Ronen Shaltiel, Emanuele Viola:
  Hardness Amplification Proofs Require Majority. 3122-3154
  
• Eldar Fischer, Arie Matsliah, Asaf Shapira:
  Approximate Hypergraph Partitioning and Applications. 3155-3185
  
• Pierre McKenzie, Michael Thomas, Heribert Vollmer:
  Extensional Uniformity for Boolean Circuits. 3186-3206
  
• Julia Kempe, Oded Regev, Ben Toner:
  Unique Games with Entangled Provers Are Easy. 3207-3229
  
• Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman:
  Locally Testable Codes Require Redundant Testers. 3230-3247
  
• Boris Aronov, Esther Ezra, Micha Sharir:
  Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes. 3248-3282
  
• Haim Kaplan, Natan Rubin, Micha Sharir:
  Line Transversals of Convex Polyhedra in R³. 3283-3310
  
• Nikhil Bansal, Kirk Pruhs:
  Server Scheduling to Balance Priorities, Fairness, and Average Quality of Service. 3311-3335
  
• Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, Marc Thurley:
  A Complexity Dichotomy for Partition Functions with Mixed Signs. 3336-3402
  
• Shiri Chechik, Michael Langberg, David Peleg, Liam Roditty:
  Fault Tolerant Spanners for General Graphs. 3403-3423
  
• Endre Boros, Khaled M. Elbassioni, Kazuhisa Makino:
  Left-to-Right Multiplication for Monotone Boolean Dualization. 3424-3439
  

Volume 39, Number 8, 2010

• Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, Emanuele Viola:
  Bounded Independence Fools Halfspaces. 3441-3462
  
• Anna Gál, Parikshit Gopalan:
  Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence. 3463-3479
  
• Robert M. Hierons:
  Reaching and Distinguishing States of Distributed Systems. 3480-3500
  
• Yuval Rabani, Amir Shpilka:
  Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions. 3501-3520
  
• David Doty:
  Randomized Self-Assembly for Exact Shapes. 3521-3552
  
• Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis:
  Integrality Gaps of 2-o(1) for Vertex Cover SDPs in the Lov[a-acute]sz--Schrijver Hierarchy. 3553-3570
  
• Klaus Jansen, Ralf Thöle:
  Approximation Algorithms for Scheduling Parallel Jobs. 3571-3615
  
• Lisa Fleischer, Jochen Könemann, Stefano Leonardi, Guido Schäfer:
  Strict Cost Sharing Schemes for Steiner Forest. 3616-3632
  
• Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman, David P. Williamson:
  A General Approach for Incremental Approximation and Hierarchical Clustering. 3633-3669
  
• David Duris:
  Extension Preservation Theorems on Classes of Acyclic Finite Structures. 3670-3681
  
• Manuel Bodirsky, Hubie Chen:
  Quantified Equality Constraints. 3682-3699
  
• Simon Fischer, Harald Räcke, Berthold Vöcking:
  Fast Convergence to Wardrop Equilibria by Adaptive Sampling Methods. 3700-3735
  
• Gábor Ivanyos, Marek Karpinski, Nitin Saxena:
  Deterministic Polynomial Time Algorithms for Matrix Completion Problems. 3736-3751
  
• Partha Dutta, Rachid Guerraoui, Ron R. Levy, Marko Vukolic:
  Fast Access to Distributed Atomic Memory. 3752-3783
  
• Éric Colin de Verdière, Jeff Erickson:
  Tightening Nonsimple Paths and Cycles on Surfaces. 3784-3813
  
• David Eppstein, Michael T. Goodrich, Darren Strash:
  Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Edge Crossings. 3814-3829
  
• Maxim Gurevich, Idit Keidar:
  Correctness of Gossip-Based Membership under Message Loss. 3830-3859
  
• Julia Lipman, Quentin F. Stout:
  Analysis of Delays Caused by Local Synchronization. 3860-3884
  
• Hagit Attiya, Keren Censor-Hillel:
  Lower Bounds for Randomized Consensus under a Weak Adversary. 3885-3904
  

Last update Mon May 20 18:23:49 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page